Advanced Level Further Pure Mathematics: Number Theory Notes

Advanced Level Further Pure Mathematics: Number Theory

Number theory studies the properties of integers. At Advanced Level, the central ideas are divisibility, prime factorisation, greatest common divisors, linear Diophantine equations, congruences and number bases. These ideas build a precise language for solving integer problems.

1. Divisibility

For integers a and b, with a ≠ 0, we say that a divides b if there is an integer k such that b = ak. We write a | b. If no such integer exists, write a ∤ b.

2. Division algorithm

For an integer a and a positive integer b, there are unique integers q and r such that

a = bq + r,   0 ≤ r < b.

The integer q is the quotient and r is the remainder. For example, dividing 527 by 23 gives 527 = 23(22) + 21.

3. Greatest common divisor and Euclidean algorithm

The greatest common divisor gcd(a,b) is the largest positive integer dividing both a and b. Repeatedly apply the division algorithm until the remainder is zero. The last non-zero remainder is the gcd.

Example: Find gcd(252,198).

252 = 198(1) + 54
198 = 54(3) + 36
54 = 36(1) + 18
36 = 18(2) + 0

Therefore, gcd(252,198) = 18. Working backwards also expresses 18 as a linear combination of 252 and 198.

4. Linear Diophantine equations

An equation ax + by = c is a linear Diophantine equation when integer solutions are required. It has a solution exactly when gcd(a,b) divides c. Once one solution (x₀,y₀) is known, all solutions are

x = x₀ + (b/d)t,   y = y₀ − (a/d)t, where d = gcd(a,b) and t ∈ ℤ.

5. Congruences

For a positive integer n, a ≡ b (mod n) means that n divides a − b. Congruence is compatible with addition, subtraction and multiplication. Division is permitted only when the factor being cancelled is coprime to the modulus.

Example: Solve 7x ≡ 5 (mod 12). Since 7 × 7 = 49 ≡ 1 (mod 12), the inverse of 7 is 7. Hence x ≡ 35 ≡ 11 (mod 12).

6. Simultaneous congruences

The Chinese Remainder Theorem states that a system x ≡ a (mod m), x ≡ b (mod n) has a unique solution modulo mn when gcd(m,n)=1. A practical method is substitution: write x = a + mk and solve the second congruence for k.

7. Fermat’s little theorem

If p is prime and p ∤ a, then a^p−1 ≡ 1 (mod p). This is particularly useful for reducing large powers.

Example: Since 2¹⁰ ≡ 1 (mod 11), 2²⁰²⁶ = (2¹⁰)²⁰²·2⁶ ≡ 64 ≡ 9 (mod 11).

8. Number bases

In base b, the numeral (a_n…a₁a₀)_b represents Σa_kb^k, where 0 ≤ a_k < b. To convert from base b to decimal, expand by place value. To convert a decimal integer to base b, use repeated division by b and read the remainders upwards.

Practice questions

1. Use the Euclidean algorithm to find gcd(414,662), then express the gcd as a linear combination.
2. Determine all integer solutions of 18x + 30y = 6.
3. Solve 9x ≡ 12 (mod 21), stating all incongruent solutions.
4. Solve x ≡ 2 (mod 5), x ≡ 3 (mod 7).
5. Convert (2314)₅ to base ten and convert 347₁₀ to base six.