Divisibility, modular arithmetic and primes

This week we begin number theory. It is not on the midterm, it is a final exam topic. But next week (cryptography, RSA) is built entirely on it: GCD, taking mods and the Euclidean algorithm are needed in every question there. Golden rules:

1. $a \mid b$ is a proposition, not a number. “3 divides 12” is true or false; $12/3 = 4$ is a number.
2. The remainder is never negative: $0 \le r < d$. For a negative number the quotient goes one lower.
3. In mod m, shrink the numbers before adding and multiplying. You never have to compute the big product.
4. For the GCD use Euclid: $\gcd(a, b) = \gcd(b, a \bmod b)$, until the remainder is 0.
5. In a proof question, write the definition: if $a \mid b$ then $b = ak$. That line is half of the proof.

Divisibility

Let $a \ne 0$. a divides b ($a \mid b$) means there is an integer $c$ with $b = ac$. $a$ is called a factor (divisor) of $b$, and $b$ a multiple of $a$.

Examples: $4 \mid 28$ because $28 = 4 \cdot 7$. $5 \nmid 28$ because $28/5 = 5.6$ is not an integer. $7 \mid 0$ because $0 = 7 \cdot 0$.

Basic properties ($a, b, c$ integers):

A fully written proof

Let’s prove transitivity the way you would write it on the exam.

Claim. If a | b and b | c, then a | c.
Proof. Suppose a | b and b | c. Then there are integers k and l
such that b = ak and c = bl.
Substituting, c = bl = (ak)l = a(kl).
Since kl is an integer, a | c by the definition of divisibility. ∎

Note: for the two separate divisibilities we used two separate letters ($k$ and $l$). Using the same letter would mean ”$b$ and $c$ have the same coefficient”, and the proof would break.

The division algorithm

For every integer $a$ and positive integer $d$ there are unique $q$ and $r$ with:

$a = dq + r, \qquad 0 \le r < d.$

$q = a \textbf{ div } d$ (quotient), $r = a \bmod d$ (remainder).

101 = 7 * 14 + 3      ->  101 div 7 = 14,  101 mod 7 = 3
-23 = 6 * (-4) + 1    ->  -23 div 6 = -4,  -23 mod 6 = 1

PITFALL · the remainder of a negative number. Writing $-23 = 6 \cdot (-3) - 5$ and saying the remainder is $-5$ is wrong: the remainder must satisfy $0 \le r < 6$. Take the quotient one lower ($-4$) and the remainder comes out positive ($1$). Java’s % operator gives $-5$ here, while the mathematical mod gives $1$.

Congruence and modular arithmetic

$a \equiv b \pmod m$ (a is congruent to b modulo m) means $m \mid (a - b)$. The same thing: $a$ and $b$ leave the same remainder when divided by $m$.

Example: $38 \equiv 14 \pmod{12}$, because $38 - 14 = 24 = 12 \cdot 2$. A clock shows 2 at hour 38 and at hour 14.

Rules: if $a \equiv b$ and $c \equiv d \pmod m$ then

$a + c \equiv b + d \pmod m, \qquad ac \equiv bd \pmod m.$

So when computing big expressions, you shrink each part first:

(17 * 29 + 8) mod 5
17 mod 5 = 2,  29 mod 5 = 4,  8 mod 5 = 3
2 * 4 + 3 = 11,  11 mod 5 = 1
Check: 17 * 29 + 8 = 501 = 5 * 100 + 1

TIP · big powers. In an $a^n \bmod m$ question, first look for a small $k$ with $a^k \equiv 1$. If you find it, divide $n$ by $k$ and compute the power of the remainder. If there is no such $k$, use the fast exponentiation (repeated squaring) method from the cryptography week.

Prime numbers

If $p > 1$ and its only positive divisors are $1$ and $p$, then $p$ is prime. A number greater than 1 that is not prime is composite. 1 is neither prime nor composite.

Fundamental Theorem of Arithmetic: every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order. Example: $600 = 2^3 \cdot 3 \cdot 5^2$.

Trial division: if $n$ is composite, it has a prime divisor less than or equal to $\sqrt{n}$. The reason: if $n = ab$ and both were greater than $\sqrt{n}$, then $ab > n$. So to show that 97 is prime, it is enough to try only 2, 3, 5, 7 ($\sqrt{97} \approx 9.8$). None divides it, so 97 is prime.

There are infinitely many primes (Euclid). Short proof idea: suppose there are finitely many, $p_1, \dots, p_n$. The number $Q = p_1 p_2 \cdots p_n + 1$ is divisible by none of the $p_i$ (the remainder is always 1). But $Q$ must have a prime divisor. We found a prime not in the list: contradiction.

GCD and LCM

$\gcd(a, b)$: the largest integer that divides both. $\operatorname{lcm}(a, b)$: the smallest positive integer that both divide. If $\gcd(a, b) = 1$, then $a$ and $b$ are relatively prime.

With factorization: for the GCD take the smaller exponent of each prime, for the LCM the larger exponent. And always

$\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab.$

Example: $\gcd(12, 18) = 6$, $\operatorname{lcm}(12, 18) = 36$, $6 \cdot 36 = 216 = 12 \cdot 18$.

The Euclidean algorithm

Factoring large numbers is hard. The Euclidean algorithm is based on this fact: if $a = bq + r$ then $\gcd(a, b) = \gcd(b, r)$. Divide until the remainder is zero; the last remainder before zero is the GCD.

gcd(2024, 748)
2024 = 2 * 748 + 528
 748 = 1 * 528 + 220
 528 = 2 * 220 + 88
 220 = 2 * 88  + 44
  88 = 2 * 44  + 0     ->  gcd = 44
lcm = 2024 * 748 / 44 = 34408

Bezout’s identity

There are always integers $s, t$ with $\gcd(a, b) = sa + tb$. To find them, you substitute the Euclid steps backwards:

44 = 220 - 2*88
   = 220 - 2*(528 - 2*220)        = 5*220 - 2*528
   = 5*(748 - 528) - 2*528        = 5*748 - 7*528
   = 5*748 - 7*(2024 - 2*748)     = 19*748 - 7*2024
s = -7, t = 19.  Check: -14168 + 14212 = 44

Next week this computation will be exactly the method for finding the modular inverse. Spend time on it here.

Common mistakes