Number Theory

🎯 Learning Objectives

• Apply divisibility rules and the division algorithm
• Use the Euclidean algorithm to find GCD
• Compute with modular arithmetic
• Prove properties of primes
• Understand the Fundamental Theorem of Arithmetic

7.1 Divisibility

• If $a \mid b$ and $b \mid c$, then $a \mid c$ (transitive)
• If $a \mid b$ and $a \mid c$, then $a \mid (b + c)$ and $a \mid (b - c)$
• If $a \mid b$, then $a \mid bc$ for any integer $c$

Division Algorithm

7.2 GCD and Euclidean Algorithm

1. $a = q_1 b + r_1$ ($0 \leq r_1 < b$)
2. $b = q_2 r_1 + r_2$ ($0 \leq r_2 < r_1$)
3. $r_1 = q_3 r_2 + r_3$
4. Continue until remainder = 0. The last non-zero remainder is $\gcd(a,b)$.

Example: $\gcd(1071, 462)$

• $1071 = 2 \times 462 + 147$
• $462 = 3 \times 147 + 21$
• $147 = 7 \times 21 + 0$
• $\gcd(1071, 462) = 21$

7.3 Modular Arithmetic

• If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$ and $ac \equiv bd \pmod{n}$
• $a \equiv b \pmod{n} \implies a^k \equiv b^k \pmod{n}$

Application: Divisibility Tests

7.4 Prime Numbers

Fundamental Theorem of Arithmetic

Infinitely Many Primes (Euclid's Proof)

✅ Practice Questions

Solution

$123 = 2 \times 45 + 33$ $45 = 1 \times 33 + 12$ $33 = 2 \times 12 + 9$ $12 = 1 \times 9 + 3$ $9 = 3 \times 3 + 0$ $\gcd(123, 45) = 3$ Q2: Compute $7^{100} \pmod{5}$. Solution

$7 \equiv 2 \pmod{5}$, so $7^{100} \equiv 2^{100} \pmod{5}$. $2^4 = 16 \equiv 1 \pmod{5}$. $2^{100} = (2^4)^{25} \equiv 1^{25} = 1 \pmod{5}$. So $7^{100} \equiv 1 \pmod{5}$. Q3: Prove that if $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$ (Euclid's lemma). Solution

Assume $p$ prime, $p \mid ab$, and $p \nmid a$. Then $\gcd(a,p) = 1$ (since $p$ is prime, its only divisors are 1 and $p$). By Bézout's identity, there exist integers $x,y$ such that $ax + py = 1$. Multiply by $b$: $abx + pby = b$. Since $p \mid ab$, $p \mid abx$, and $p \mid pby$, so $p \mid b$. Join Discord PreviousRelations and FunctionsNextModular Arithmetic Deep