# Modular arithmetic

### Definition

Two numbers in Z are said to be congruent modulo m if their difference is multiple of m.
That's written x ≡ y (modulo m).

It is an equivalence relation, that is :

• x ≡ x (modulo m)
• x ≡ y (modulo m) implies y ≡ x (modulo m)
• x ≡ y (modulo m) and y ≡ z (modulo m) implies x ≡ z (modulo m)
We can then define equivalence classes. There are m equivalence classes in modulo m congruence.
A set of m numbers representing these classes will be called a set of residues modulo m.
The set of these equivalence classes is named Z/mZ, quotient set of Z by multiples of m.

An important case is when m is a prime p :

 If p is a prime Z/pZ is a field

The condition is also necessary because if m is not prime, Z/mZ has at least one divisor of 0, that is there are two integers a and b not null with a×b ≡ 0 (mod m). If m is not prime, Z/mZ is just a ring.
Every element (a) in Z/pZ has an inverse (a') : (a)×(a') = 1 that is a×a' ≡ 1 (mod p)
If m not prime, (a) has an inverse iff GCD(a,m) = 1.

### Solving modular equations

That is equations in Z/mZ, that is f(x) ≡ 0 (mod m).
We'll specifically study cases when f(x) is a polynom P(x) with coefficients in Z/mZ.

#### First degree equation a.x ≡ b (mod m)

That is a.x = b + m.k, which is a first degree Diophantine equation whose solution is known.
Let p = GCD(a,m), then equation has solution iff p divides b.
Let a' = a/p, b' = b/p, m' = m/p, equation becomes a'.x ≡ b' (mod m') with GCD(a',m') = 1.
Then a' has an inverse (1/a') and x ≡ (1/a')×b' (mod m').
Practically we get the inverse of a' by Euclid algorithm.
The Euler-Fermat theorem says if a and m coprimes,  aφ(m) ≡ 1 (mod m)  with φ(m) the Euler totient function. Inverse of a is then  aφ(m)-1
Note that if m is a prime p, inverse of a always exists, a.x ≡ b (mod p) has always solution. And φ(p) = p - 1.

Example : 14x ≡ 21 (mod 35)
GCD of 14 and 35 is 7, dividing 21, solutions are the same as 2x ≡ 3 (mod 5)
Inverse of 2 modulo 5 is 3 , hence x ≡ 3×3 ≡ 4 (mod 5)
And 7 solutions in Z/35Z : 4, 9, 14, 19, 24, 29, 34.

#### Chinese remainder theorem

If m1, m2, ... mn are integers ≥2 and two by two coprimes, if a1, a2,... an are any integers,
then there is a unique integer x modulo m1m2...mn, which satisfies simultaneously :
x ≡ a1 modulo m1
x ≡ a2 modulo m2
...
x ≡ an modulo mn

Let m = m1m2...mn and calculate the inverses qi ≡ (m/mi)-1 modulo mi
Then x ≡ ∑qiaim/mi    modulo m
Applying Euler-Fermat gives a formula for the qi ≡ (m/mi)φ(mi)-1 modulo mi
Practically we prefer to use Euclide algorithm to solve (m/mi)×qi ≡ 1 modulo mi.

Example :
x ≡ a modulo 7
x ≡ b modulo 11
x ≡ c modulo 13
7, 11 and 13 being two by two coprime (and even just primes), We get a unique x modulo 7×11×13 = 1001.

q1 ≡ (11×13)-1 ≡ 143-1 ≡ 3-1 ≡ 5 modulo 7
q2 ≡ (7×13)-1 ≡ 91-1 ≡ 3-1 ≡ 4 modulo 11
q3 ≡ (7×11)-1 ≡ 77-1 ≡ 12-1 ≡ 12 modulo 13

x ≡ a×5×11×13 + b×4×7×13 + c×12×7×11 ≡ 715a + 364b + 924c modulo1001

### Second degree equation a.x² + b.x + c ≡ 0 (mod m)

If p = GCD(a,m) : a'.p.x² + b.x + c ≡ 0 (mod (m'.p))
A necessary condition is then b.x + c ≡ 0 (mod p).
Solving this equation, then substitute into original equation results into a new equation with GCD(a',m') = 1, even by repeating the process. This always ends as m' < m.
For example : 6x² + 5x + 16 ≡ 0 (mod 33), GCD(6,33) = 3, hence 5x + 16 ≡ 0 (mod 3) <=> 2x + 1 ≡ 0 (mod 3)
whose solutions are x ≡ 1 (mod 3) that is x = 1 + 3k.
this gives 6(1 + 3k)² + 15k + 21 ≡ 0 (mod 33) that is
2(1 + 3k)² + 5k + 7 ≡ 0 (mod 11) or 18k² + 17k + 9 ≡ 0 (mod 11) that is 7k² + 6k + 9 ≡ 0 (mod 11)

We can then suppose GCD(a,m) = 1.
Hence a has an inverse a', and multiplying by a' we get x² + b'.x + c' ≡ 0
Our examples gives 1/7 = 8 (mod 11) and 7k² + 6k + 9 ≡ 0 (mod 11) <=> k² + 4k + 6 ≡ 0 (mod 11)
To finish this example, (k + 2)² + 2 ≡ 0 (mod 11) that is y² ≡ 9 (mod 11) => y ≡ ±3 (mod 11).
and taking calculation backwards k = y - 2 then
x = 1 + 3k = 3y - 5 ≡  4 and 19 (mod 33)

#### Second degree equation x² + b.x + c ≡ 0 (mod pn), p odd prime

Hence 2 has an inverse, 2q = 1 (mod pn) and we can write :
x² + 2q.b.x + c ≡ 0 (mod pn)
that is (x+b.q)² - (b.q)² + c ≡ 0 Let y = x + b.q and d = (b.q)² - c :
y² ≡ d (mod pn)

For instance : x² + 3x + 5 ≡ 0 (mod 25)
1/2 = 13 (mod 25) hence :
x² + 3x + 5 ≡ x² + 2×(13×3)x + 5 ≡ x² + 2×14x + 5 that is (x+14)² ≡ 14² - 5 ≡ 16 (mod 25)
then solutions are x + 14 ≡ ± 4 (mod 25) that is x = 7 and 15 mod 25

Multiplication by q = 1/2 is useless if b even = 2b' :
x² + 2b'.x + c ≡ 0 can directly be written (x + b')² ≡ b'² - c

#### Second degree equation x² + b.x + c ≡ 0 (mod 2n)

Then 2 has no inverse (mod 2n) and the previous method fails with b odd.
Solutions are searched in the two families :
• x even = 2u, 4u² + 2bu + c ≡ 0 (mod 2n)
c must be c ≡ 0 (mod 2), c = 2c' that is 2u² + bu + c' ≡ 0 (mod 2n-1),
hence bu + c' ≡ 0 (mod 2) and we can go on as previously.

• x odd = 2u + 1, 4u² + 4u + 1 + 2bu + b + c ≡ 0 that is
c must be b + c + 1 ≡ 0 (mod 2), taht is c = 2c' - b - 1 and 2u² + (b + 2)u + c' ≡ 0 (mod 2n-1),
hence (b + 2)u + c' ≡ 0 (mod 2) and we can go on as previously.

Example : x² + 7x + 2 ≡ 0 (mod 8)
1) x = 2u : 4u² + 14u + 2 ≡ 4u² + 6u + 2 ≡ 0 (mod 8)
2u² + 3u + 1 ≡ 0 (mod 4), 3u + 1 ≡ 0 (mod 2), u = 2k + 1
(2k + 1)² + 3k + 4 ≡ (2k + 1)² + k ≡ 0 (mod 2)
4k² + 5k + 1 ≡ k + 1 ≡ 0 (mod 2)
hence k = 2m + 1 and x = 2u = 4k + 2 =  8m + 6

2) x = 2u + 1 : 4u² + 18u + 10 ≡ 4u² + 2u + 2 ≡ 0 (mod 8)
2u² + u + 1 ≡ 0 (mod 4), u = 2k + 1
(2k + 1)² + k + 1 ≡ 0 (mod 2)
4k² + 5k + 2 ≡ k ≡ 0 (mod 2)
hence k even = 2m, x= 2u + 1 = 4k + 3 =  8m + 3

And two solutions modulo 8.

### square root x² ≡ a (mod m)

First note the important results :

 x² ≡ 1 (mod 2) has only one solution : x = 1 x² ≡ 1 (mod 4) has two solutions : x = ± 1 x² ≡ 1 (mod 2n), n>2, has four solutions :       x = ± 1 and x = ±(2n - 1 - 1) x² ≡ 1 (mod pn), p odd prime, has two solutions : x = ± 1

The same number at most of solutions for x² ≡ a (mod m), else, no solutions at all.
we define a quadratic residue as a number a for which x² ≡ a (mod m) has a solution.
We just limit to numbers to a being coprime with m, and even to m being pn, p prime, by using chinese remainder theorem.

Coming back to x² ≡ a (mod m), let's try an example : find all squares which end in 329.
x² ≡ 329 (mod 1000). As 1000 = 2³×5³ we have first to solve the two modular equations :
x² ≡ 329 ≡ 1 (mod 8) and
x² ≡ 329 ≡ 79 (mod 125)

The first one x² ≡ 1 (mod 8) has solutions x ≡ ±1 or ±3 (mod 8)

the second one x² ≡ 79 (mod 125) is a litle bit harder.
Let's solve first x² ≡ 79 ≡ 4 (mod 5) whose solutions are obviously x ≡ ±2 (mod 5).
Solutions of x² ≡ 79 ≡ 4 (mod 25), even if in this case obvious, but just to show the method, are deduced from the previous solutions ±2 (mod 5) as being ±2 + 5k.
that is (±2 + 5k)² = 4 ± 20k + 25k² ≡ 4 (mod 25) Hence 20k ≡ 0 (mod 25) or 4k ≡ 0 (mod 5).
Solutions of x² ≡ 4 (mod 25) are then as expected x ≡ ±2 (mod 25)
Search then solutions of x² ≡ 79 (mod 125) from those modulo 25 as being ±2 + 25k :
(±2 + 25k)² = 4 ± 100k + 25²k² ≡ 79 (mod 125) that is ±100k ≡ 75 (mod 125) hence ±4k ≡ 3 (mod 5) whose solutions are k = ±2 + 5m then x = ±2 + 25k = ±52 + 125m.

Generally speaking, solutions of x² ≡ a (mod pn+1) are obtained from solution x0 of x² ≡ a (mod pn) as being x0 + k.pn : (x0 + k.pn)2 = x02 + 2k.x0pn + k2p2n ≡ x02 + 2k.x0pn ≡ a (mod pn+1) as 2n>n+1 as soon as n>1.
Because x0² ≡ a (mod pn), this reduces to a modulo p relation : 2k.x0 ≡ a - x0² (mod p).
Hence value of k and x0 + k.pn.

Solutions of x² ≡ 329 (mod 8) and of x² ≡ 329 (mod 125) are then "mixed" by the chinese remainder theorem to get solutions of x² ≡ 329 (mod 1000).
First of all let's calculate 1/125 ≡ 5 (mod 8) and 1/8 ≡ 47 (mod 125)
then solutions are : u×5×125 + v×47×8 (mod 1000)
with u any solution of x² ≡ 329 (mod 8) that is the four values ±1 and ±3,
and v solution of x² ≡ 329 (mod 125) that is v = ±52
hence 4×2 = 8 solutions :

1×625 + 52×376 ≡ 177 (mod 1000)
1×625 - 52×376 ≡ 73 (mod 1000)
-1×625 + 52×376 ≡ 927 (mod 1000)
-1×625 - 52×376 ≡ 823 (mod 1000)
3×625 + 52×376 ≡ 427 (mod 1000)
3×625 - 52×376 ≡ 323 (mod 1000)
-3×625 + 52×376 ≡ 677 (mod 1000)
-3×625 - 52×376 ≡ 573 (mod 1000)
(Which we can reduce two just two solutions : 73 and 177 modulo 250)

Remains just to solve x² ≡ a (mod p), p prime.
For small values of p the most efficient is just try (p-1)/2 values from 1 to (p-1)/2, for larger p there is a more efficient method : Tonelli-Shanks algorithm.

### nth root : xn ≡ a (mod p)

#### Primitive root

We call primitive root of p, some integer g not multiple of p with gk ≡ 1 modulo p and the smallest value of k = p-1 (order of g is k). (for non primitive roots, k just divides p-1)
Every prime p has a primitive root (and even several).
Every number x not multiple of a is then x ≡ ak modulo p that is every number x not multiple of p is "generated" by a primitive root.

Generally speaking, there is a primitive root g of m iff m = 2, 4, pn, 2pn, p odd prime.
gk ≡ 1 modulo m, and the smallest k (order of g) is φ(m), Euler totient function of m.
There are then φ(φ(m)) primitive roots.

The problem is to find a primitive root.
g is not a primitive root of m if :
- GCD(g,m) ≠ 1
- or p is a prime factor of φ(m) and gφ(m)/p ≡ 1 modulo m

Finding g can be done systematically or at random :

 m = 2 : g = 1 m = 4 : g = 3 m = pn or 2pn : find a primitive root of p      try g = 2, 3, 5, 6 (OK in 80% cases)      else try at random between 7 and p-1  If g not a primitive root of pn, remplace g by g + p  At last if m = 2pn and g even, remplace g by g + pn

#### nth Root

xn ≡ a modulo p, a not multiple of p.
Let g a primitive root of p : x ≡ gk modulo p and a ≡ gh modulo p.
gn.k ≡ gh modulo p with k being the new unknown.
Hence  n.k ≡ h modulo p-1  (because ap-1 ≡ 1 modulo p, calculating on exponents is modulo p-1).
This is a first degree modular equation, what we can solve.

 Number of solutions of xn ≡ a modulo p is either 0 or d = GCD(n, p-1)

The problem is then to find a primitive root g of p, and to find h with a ≡ gh modulo p.

Example : x10 ≡ 43 modulo 97
First find a primitive root of 97
φ(97) = 96 = 25×3, test on g is then on gφ(m)/p = g48 and g32
216 ≡ 61 modulo 97 at most 232 ≡ 35 and 2481
316 ≡ 61 modulo 97 at most 3 doesn't work either
516 ≡ 36 modulo 97 at most 532 ≡ 35 and 548 ≡ 96
Hence 5 is a primitive root of 97.

We have then to find h such as 5h ≡ 43 modulo 97
Calculating successive powers of 5 gives :
5, 25, 28, 43... hence 43 = 54 (without need of calculating all the 96 powers ! pff !)

Remains to solve 10.k ≡ 4 modulo 96 that is 5.k ≡ 2 modulo 48 and k = 10 and 58.
And finally two solutions x ≡ 510 ≡ 53 modulo 97 and x ≡ 558 ≡ 44 modulo 97.