Modular Arithmetic
Chaang Tze Shen Tristan
May 19, 2018
1 Congruence
Two integers are said to be congruent mod m if their remainders are equal when
divided by m, we write this as
a≡b (mod m)
For example the following holds:
16 ≡ 9 ≡ 2 ≡ −5 ≡ −12 (mod 7)
Note that congruence expressions are linear and multiplicative. Also, if a ≡ b (mod m),
then an ≡ bn (mod m) for any positive integer n.
2 Multiplicative Inverses
We want to solve 7x ≡ 3 (mod 9). Then we write x ≡ 37 (mod 9) (Note that here 3
7 is
not really a fraction! It is just a convention to write x in a neater manner.)
3 12 12
x≡ ≡ ≡ ≡ 12 (mod 9)
7 28 1
3 The Base-eliminating Method
When solving congruences with large powers, we need to find a way to eliminate it.
Example 1. Find the remainder of 210000 when divided by 127.
Solution. Note that 27 ≡ 1 (mod 127). Therefore we can do this:
210000 ≡ (27 )1428 × 24
≡ 11428 × 24
≡ 16 (mod 127)
We need to be smart to find the order, which is when will it be congruent to 1 (or
anything that would be easy to evaluate under large powers)
1
3.1 Problems
1. Find the remainder of 32000 when divided by 13.
2019
2. Find the remainder of 20192019 when divided by 7.
163
3. Find the units digit of 163163 .
4 The Chinese Remainder Theorem (CRT)
If given a system of ANY number of expressions
x ≡ ai (mod mi )
where mi are all pairwise coprime, then there is a unique solution mod m1 m2 ...mi
x ≡ A (mod m1 m2 ...mi )
77
Example 2. Find the last two digits of 77 .
Solution. We can first split 100 into two coprime numbers 4 and 25.
For mod 4,
77
77 ≡ (−1)2k+1 ≡ −1 ≡ 3 (mod 4)
For mod 25, note that 72 ≡ −1 (mod 25), so 74 ≡ 1 (mod 25).
77
77 ≡ 74k+3 ≡ 73 ≡ 343 ≡ 18 (mod 25)
77
Therefore 77 ≡ 43 (mod 100).
Example 3. Given n, is it always possible to have n consecutive integers, each
divisible by a square greater than 1?
Solution. Yes. Consider n pairwise coprime perfect squares X1 , X2 , X3 , ..., Xn . Let
x + i ≡ 0 (mod Xi ) (i = 1, 2, 3, ..., n)
x ≡ −i (mod Xi ) (i = 1, 2, 3, ..., n)
x is solvable by CRT. Thus x + 1, x + 2, x + 3, ...x + n is the desired sequence. (Q.E.D)
4.1 Real Problems
1717
1. Find the last two digits of 1717
2. (1987/IMO) Prove that there 1000 consecutive integers such that none is a power
of a prime.
3. (2017/ChenJingRun) How many positive integers n < 1000 are there such that
nn + 1 can be divisible by 66?
2
5 Perfect Squares
Here are some extremely important perfect-square properties.
x2 ≡ 0, 1 (mod 3)
x2 ≡ 0, 1 (mod 4)
x2 ≡ 0, 1, 4, 5, 6, 9 (mod 10)
5.1 Problems
1. How many n ∈ N are there such that 2007 + 4n is a perfect square?
2. Prove that there are no abc such that abc + bca + cab is not a perfect square.
3. Prove that there are infinitely primes which cannot be expressed as a sum of two
squares.
4. Let 2001m2 + m = 2002n2 + n and m, n positive integers. Prove that m − n is
a perfect square.