Number Theory Fundamentals

📋 Course Outline

1. Division Algorithm
2. Divisibility and Linear Combinations
3. Quotients and Remainders
4. Modular Arithmetic
5. Prime Factorization
6. Prime Numbers and Theorems
7. Greatest Common Divisor
8. Euclid's Algorithm
9. Extended Euclidean Algorithm
10. Multiplicative Inverse

📖 1. Division Algorithm

🔑 Key Concepts & Definitions

• Division Algorithm:
  The theorem stating that for any integer $a$ and positive integer $d$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:
  $a = dq + r \quad \text{with} \quad 0 \leq r < d$
  This guarantees the existence and uniqueness of the quotient and remainder when dividing integers.

• Quotients and Remainders:
  The results of division, where the quotient $q$ is the integer part of the division, and the remainder $r$ is what is left over, satisfying $0 \leq r < d$.

• Integer Division Definitions:
  In the context of the Division Algorithm, the quotient $q$ and remainder $r$ are defined such that:
  $a = dq + r$ with the specified bounds on $r$. The quotient and remainder are uniquely determined by this relation.

• Procedural Version of the Division Algorithm:
  A step-by-step method to compute $q$ and $r$ for given integers $a$ and positive integer $d$. It involves iterative subtraction or division steps to find the unique $q$ and $r$ satisfying the relation, ensuring $0 \leq r < d$.

📝 Essential Points