Modular Arithmetic
Ryan Ng
7 is congruent to 2, modulo 5. This means that when both of these numbers are divided by 5, their remainders are the same. -1 is congruent to 9, mod 10—this applies works even for negative numbers. While we’ve mostly left remainders in elementary school, they are actually involved in some highly sophisticated problem solving techniques.
We write modulo congruence like this:
7 ≡ 2 (mod 5)
Two basic properties
If a ≡ b (mod n) and c ≡ d (mod n) then
a + b ≡ c + d (mod n)
and
ab ≡ cd (mod n)
A slightly less basic property
If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any integer k
This theorem is quite interesting and actually quite handy. For example, if we need to find the remainder of 11^43895743 when divided by 10, note that 11 ≡ 1 (mod 10) so 11^43895743 ≡ 1^43895743 (mod 10). And 1 to the power of any integer is just 1. So it’s not that daunting!
We can use this property to solve our first cool question.
Question 1
Given that 22! = 1124000727777XYZ680000, write down the missing digits XYZ.
This strategy doesn’t really have a name, so I like to call it “dividing by 1001”. We’re pretty much going to take both sides mod 1001.
First, we’ll see that 1000 ≡ -1 mod 1001, and 1000^k ≡ (-1)^k mod 1001. We’ll then split the expression into chunks of 3 digits. We get:
22! ≡ 1124 * 1000^6 + 727 * 1000^4 + 777 * 1000^3 + XYZ * 1000^2 + 680 * 1000 (mod 1001)
Because of the properties ab ≡ cd (mod n) and a^k ≡ b^k (mod n), we can replace all the 1000s with -1:
22! ≡ 1124 * (-1)^6 + 727 * (-1)^4 + 777 * (-1)^3 + XYZ * (-1)^2 + 680 * (-1) (mod 1001)
We can simplify the exponents of -1 now:
22! ≡ 1124 + 727 + -777 + XYZ + -680 (mod 1001)
Now, note that 1001 = 7 × 11 × 13. These three are both factors of 22! so the left side is congruent to 0 mod 1001 — 22! is divisible by 1001.
0 ≡ 394 + XYZ (mod 1001)
Since XYZ is 3 digits, the right side has to add up to 1001. We finally get XYZ = 607.
Wilson’s theorem
An integer n is a prime number if and only if
(n-1)! ≡ -1 (mod n)
I’ve never ended up using this, but it looks useful and could be good to know.
Divide and conquer strategy
I made this name up because I’ve never seen this elsewhere. The rule here is:
If x ≡ b (mod m) and x ≡ b (mod n), then x ≡ b (mod mn)
This is useful to calculate high modulo values. For example, if we need to find the smallest a such that c^2 ≡ 1 (mod 100), then we can just find a value of c such that
c^2 ≡ 1 (mod 25) and c^2 ≡ 1 (mod 4), which simplifies the equation greatly. I’m not sure if this actually has a solution as I made this up, but you can give it a shot!
Euler’s totient function
Euler’s totient function is a function that takes in a positive integer n, and outputs the number of positive integers below n that are coprime to it (that share no common factors). We write it as φ(n).
First, for any prime number n, φ(n) = n-1 as it has no prime factors, so all numbers below n cannot share any prime factors with it.
Second, for any two coprime numbers m and n (once again, if they share no common factors), φ(mn) = φ(m)φ(n). You can try to prove this.
Finally, for any prime number n, φ(n^k) = n^k - n^(k-1).
Why is this important? Apart from counting coprime numbers, there is this rule, known as the Fermat-Euler theorem. If a and n are coprime, then.
a^φ(n) ≡ 1 (mod n)
If we replace n with a prime number p, we actually get Fermat’s little theorem, which is:
a^φ(p) ≡ 1 (mod p)
a^(p-1) ≡ 1 (mod p)
A last question
Find the remainder when 1111^2019 is divided by 11111.
1111 is congruent to -10000 mod 2019, so we have
(-10000)^2019 ≡ -10^(2019*4) mod 11111
≡ -10^8076 ≡ -10 * (10^5)^1615
Now, 10^5 = 100000 = 9 * 11111 + 1, meaning that it is congruent to 1 mod 11111. So we have
1111^2019 ≡ -10 * 1^1615 ≡ -10 mod 11111
So by adding 11111 to make it a proper remainder, the answer is 11101.