Number Theory and Integers
What the exam tests
Number Theory and Integers tests divisibility, the Euclidean algorithm, congruences, and integer solutions. Kyoto problems often ask for the remainder of a power, the gcd of large integers, or all solutions to a linear congruence.
Core rules
- a divides b if b = ak for some integer k. If d = gcd(a, b), then there exist integers x, y with ax + by = d (Bézout's identity).
- Euclidean algorithm: repeatedly replace (a, b) by (b, a mod b) until the remainder is 0; the last nonzero remainder is gcd(a, b).
- Congruence a ≡ b (mod m) means m divides a - b. Congruences may be added and multiplied.
- A linear congruence ax ≡ b (mod m) has a solution exactly when gcd(a, m) divides b. If it has one solution, it has gcd(a, m) solutions modulo m.
- Division by a modulo m is allowed only when gcd(a, m) = 1; then a has a modular inverse.
Worked example
Find gcd(1071, 462). Compute 1071 = 2·462 + 147; 462 = 3·147 + 21; 147 = 7·21 + 0. The last nonzero remainder is 21, so gcd(1071, 462) = 21. To solve 7x ≡ 3 (mod 11), note that 7·8 = 56 ≡ 1 (mod 11), so 8 is the inverse of 7. Multiply by 8: x ≡ 24 ≡ 2 (mod 11).
Traps
Do not divide a congruence by a number that is not coprime to the modulus; this can lose solutions. Use the positive remainder in the Euclidean algorithm to avoid sign errors. A congruence solution is a class modulo m, not a single integer unless the problem restricts the range.