Number Theory (Integers and Division)

Tags: #◇Problem Solving #◇Number Theory #◇Discrete Math #◇CCDSTRU #◇M9 #◇Cryptography

---

◇Important Formulas & Core Concepts

Number theory investigates the properties of integers $\mathbb{Z}$, with fundamental applications across cryptography (RSA, Diffie-Hellman), hashing algorithms, and pseudo-random number generation.

1. Division & Modular Arithmetic

• Divisibility ($a \mid b$): For $a, b \in \mathbb{Z}$ with $a \ne 0$, $a$ divides $b$ if and only if there exists an integer $c$ such that $b = a \cdot c$.
• The Division Algorithm: For integer $a$ and positive integer $d$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that:
  $a = d \cdot q + r, \quad \text{where } 0 \le r < d$
• Modular Congruence: Integers $a$ and $b$ are congruent modulo $m$ ($m \in \mathbb{Z}^+$), written $a \equiv b \pmod m$, if and only if $m \mid (a - b)$.
  • Equivalently: $a \bmod m = b \bmod m$, or $a = b + k \cdot m$ for some $k \in \mathbb{Z}$.

2. Primes, GCD, & Fundamental Theorem of Arithmetic

• Prime Number: An integer $p > 1$ whose only positive divisors are $1$ and $p$.
• Fundamental Theorem of Arithmetic: Every integer $n > 1$ can be expressed uniquely as a product of prime numbers in non-decreasing order:
  $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$
• Greatest Common Divisor ($\gcd(a, b)$): The largest positive integer dividing both $a$ and $b$. If $\gcd(a, b) = 1$, $a$ and $b$ are relatively prime (coprime).
• Least Common Multiple ($\operatorname{lcm}(a, b)$): Smallest positive integer divisible by both $a$ and $b$.
  $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = a \cdot b \quad (\text{for } a, b > 0)$

3. Bézout's Identity & Modular Inverses

• Bézout's Theorem: For non-zero integers $a$ and $b$, there exist integers $s$ and $t$ (Bézout coefficients) such that:
  $s \cdot a + t \cdot b = \gcd(a, b)$
• Modular Multiplicative Inverse: An integer $\bar{a}$ is the modular inverse of $a$ modulo $m$ if:
  $a \cdot \bar{a} \equiv 1 \pmod m$
  The inverse $\bar{a} \pmod m$ exists if and only if $\gcd(a, m) = 1$.

---

◇Stepped Algorithmic Traces & Calculations

Calculation 1: Extended Euclidean Algorithm & Modular Inverse

Problem: Find $\gcd(43, 17)$ and compute the modular inverse of $17 \pmod{43}$.

Step 1: Forward Euclidean Division

1. $43 = 2 \cdot 17 + 9 \implies 9 = 43 - 2(17)$
2. $17 = 1 \cdot 9 + 8 \implies 8 = 17 - 1(9)$
3. $9 = 1 \cdot 8 + 1 \implies 1 = 9 - 1(8)$
4. $8 = 8 \cdot 1 + 0$ (Remainder 0; last non-zero remainder is 1)
   Thus, $\gcd(43, 17) = 1$, confirming that $17$ is invertible modulo $43$.

Step 2: Extended Back-Substitution for Bézout Coefficients

Express the remainder $1$ in terms of $43$ and $17$:
$\begin{aligned} 1 &= 9 - 1(8) \\ &= 9 - 1[17 - 1(9)] = 2(9) - 1(17) \\ &= 2[43 - 2(17)] - 1(17) = 2(43) - 4(17) - 1(17) \\ 1 &= 2(43) - 5(17) \end{aligned}$
Hence, Bézout's Identity is:
$2(43) + (-5)(17) = 1$

Step 3: Extract Modular Inverse

Reducing modulo $43$:
$(-5) \cdot 17 \equiv 1 \pmod{43}$
Because the coefficient $-5$ is negative, add $43$ to find the canonical representative in $[0, 42]$:
$\bar{a} \equiv -5 + 43 = \mathbf{38} \pmod{43}$
Verification: $17 \times 38 = 646$. Notice $646 = 15 \times 43 + 1 \equiv 1 \pmod{43}$. Correct!

---

Calculation 2: Solving a Linear Congruence

Problem: Solve the linear congruence $7x \equiv 3 \pmod{19}$.

Step 1: Find Inverse of 7 Modulo 19

Since $\gcd(7, 19) = 1$, an inverse exists. Use Euclidean algorithm:

• $19 = 2(7) + 5 \implies 5 = 19 - 2(7)$
• $7 = 1(5) + 2 \implies 2 = 7 - 1(5)$
• $5 = 2(2) + 1 \implies 1 = 5 - 2(2)$
  Back-substitute:
  $1 = 5 - 2[7 - 1(5)] = 3(5) - 2(7) = 3[19 - 2(7)] - 2(7) = 3(19) - 8(7)$
  Thus, $(-8) \cdot 7 \equiv 1 \pmod{19} \implies 7^{-1} \equiv -8 + 19 = 11 \pmod{19}$.

Step 2: Multiply Both Sides by the Inverse

$x \equiv 11 \cdot 3 \pmod{19}$
$x \equiv 33 \equiv 33 - 19 = \mathbf{14} \pmod{19}$
Verification: $7(14) = 98$. And $98 = 5(19) + 3 \equiv 3 \pmod{19}$. Solution is unique modulo 19: $x \equiv 14 \pmod{19}$.

---

Calculation 3: Chinese Remainder Theorem (CRT)

Problem: Find the smallest non-negative integer $x$ satisfying the system:
$x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5, \quad x \equiv 2 \pmod 7$

Step 1: Verify Pairwise Coprimality

The moduli $m_1 = 3, m_2 = 5, m_3 = 7$ are pairwise coprime ($\gcd(3, 5) = \gcd(3, 7) = \gcd(5, 7) = 1$).
Compute product of moduli:
$M = m_1 \cdot m_2 \cdot m_3 = 3 \times 5 \times 7 = 105$

Step 2: Compute Partial Moduli & Their Inverses

1. For $m_1 = 3$:
   $M_1 = \frac{105}{3} = 35$
   Find $y_1$ such that $35 y_1 \equiv 1 \pmod 3 \implies 2 y_1 \equiv 1 \pmod 3 \implies y_1 = 2$.
2. For $m_2 = 5$:
   $M_2 = \frac{105}{5} = 21$
   Find $y_2$ such that $21 y_2 \equiv 1 \pmod 5 \implies 1 y_2 \equiv 1 \pmod 5 \implies y_2 = 1$.
3. For $m_3 = 7$:
   $M_3 = \frac{105}{7} = 15$
   Find $y_3$ such that $15 y_3 \equiv 1 \pmod 7 \implies 1 y_3 \equiv 1 \pmod 7 \implies y_3 = 1$.

Step 3: Compute Linear Combination

$x = \sum_{i=1}^3 a_i M_i y_i \pmod M$
$x = (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1)$
$x = 140 + 63 + 30 = 233$
Reduce modulo $105$:
$x \equiv 233 \bmod 105 = 233 - 2(105) = 233 - 210 = \mathbf{23}$

Step 4: Verification

• $23 = 7(3) + 2 \equiv 2 \pmod 3$
• $23 = 4(5) + 3 \equiv 3 \pmod 5$
• $23 = 3(7) + 2 \equiv 2 \pmod 7$
  The unique solution modulo 105 is $x = \mathbf{23}$.

---

◇References & Navigation

• Previous Topic: ◇Mathematical Induction
• Related Notes: ◇Number Theory, ◇Equivalences, ◇Sums and Sequences