Number Theory and

Cryptography

Chapter 4
Solving Congruence's

Section 4.4
 Section Summary

 Linear Congruences
 The Chinese Remainder Theorem
 Computer Arithmetic with Large Integers (not currently included in slides,
see text)
 Fermat’s Little Theorem
 Pseudoprimes
 Primitive Roots and Discrete Logarithms
 Linear Congruence
Definition: A congruence of the form
ax ≡ b( mod m),
where m is a positive integer,
a and b are integers, and
x is a variable,
is called a linear congruence.

– The solutions to a linear congruence ax≡ b( mod m) are all integers x that
satisfy the congruence.

Definition: An integer ā such that āa ≡ 1( mod m) is said to be an inverse of a

modulo m.

Example: 5 is an inverse of 3 modulo 7 since 5∙3 = 15 ≡ 1(mod 7)

– One method of solving linear congruences makes use of an inverse ā, if it exists.

– Although we can not divide both sides of the congruence by a, we can multiply
by ā to solve for x.
 Inverse of a modulo m

Theorem 1: If a and m are relatively prime integers and m > 1, then an

inverse of a modulo m exists.

Proof:
From BÉZOUT’S THEOREM, If a and m are positive integers, then there
exist integers s and t such that gcd(a, m) = sa + tm.

Since gcd(a,m) = 1,so, sa + tm = 1.

Hence, sa + tm ≡ 1 ( mod m).
Since tm ≡ 0 ( mod m), it follows that sa ≡ 1 ( mod m)
Consequently, s is an inverse of a modulo m.

The uniqueness of the inverse is Exercise 7. ⨞

 Finding Inverses

The Euclidean algorithm and Bézout coefficients gives us a systematic

approaches to finding inverses.
Example: Find an inverse of 3 modulo 7.
Solution:
Because gcd(3,7) = 1, by Theorem 1, an inverse of 3 modulo 7 exists.
– Using the Euclidian algorithm:
7 = 2⨯3 + 1.
Or −2⨯3 + 1∙7 = 1, (sa + tm = 1)
– See that −2 and 1 are Bézout coefficients of 3 and 7.
– Hence, −2 is an inverse of 3 modulo 7.
– General solution: -2+7ℤ (every integer congruent to −2 modulo 7 is an
inverse of 3 modulo 7 i.e., 5, −9, 12, etc.)
 Finding Inverses

Example: Find an inverse of 101 modulo 4620.

Solution: First use the Euclidian algorithm to show that gcd(101,4620) = 1.

Working Backwards:
4620 = 45∙101 + 75 1 = 3 − 1∙2
101 = 1∙75 + 26 1 = 3 − 1∙(23 − 7∙3) = − 1 ∙23 + 8∙3
75 = 2∙26 + 23 1 = −1∙23 + 8∙(26 − 1∙23) = 8∙26 − 9 ∙23
26 = 1∙23 + 3 1 = 8∙26 − 9 ∙(75 − 2∙26 )= 26∙26 − 9 ∙75
23 = 7∙3 + 2 1 = 26∙(101 − 1∙75) − 9 ∙75
3 = 1∙2 + 1 = 26∙101 − 35 ∙75
2 = 2∙1 1 = 26∙101 − 35 ∙(4620 − 45∙101)
= − 35 ∙4620 + 1601∙101
Since the last nonzero, remainder is 1, gcd(101,4260) = 1
Bézout coefficients : − 35 and 1601
1601 is an inverse of 101 modulo 42620
 Using Inverses to Solve
Congruence
 We can solve the congruence ax≡ b( mod m) by multiplying both sides
by ā.
Example: What are the solutions of the congruence 3x≡ 4( mod 7).

Solution: We found that −2 is an inverse of 3 modulo 7 (two slides back).

We multiply both sides of the congruence by −2 giving

 2  3x   2  4(mod 7)
or - 6x   8 (mod 7)
or - 6x mod 7  - 8 mod 7
or ((-6 mod 7)(x mod 7) mod 7)  -8(mod 7)
or x mod 7  - 8 mod 7
 x  - 8 (mod 7)

Generally we say, x ≡ b⨯-2 (mod 7)

 The Chinese Remainder
Theorem
 In the first century, the Chinese mathematician Sun-Tsu asked:

There are certain things whose number is unknown. When divided by 3, the
remainder is 2; when divided by 5, the remainder is 3; when divided by 7, the
remainder is 2. What will be the number of things?

 This puzzle can be translated into the solution of the system of

congruences:
x ≡ 2 ( mod 3),
x ≡ 3 ( mod 5),
x ≡ 2 ( mod 7)?
 The Chinese Remainder Theorem can be used to solve Sun-Tsu’s problem.
 The Chinese Remainder
Theorem
Theorem 2: (The Chinese Remainder Theorem)
Let m1,m2,…,mn be pairwise relatively prime positive integers greater than
one and a1,a2,…,an arbitrary integers. Then the system
x ≡ a1 ( mod m1)
x ≡ a2 ( mod m2)
∙
∙
x ≡ an ( mod mn)
Let Mk=m/mk for k = 1,2,…,n and there is an integer yk , an inverse of Mk
modulo mk,
x = a1 M1 y1 + a2 M2 y2 + ∙ ∙ ∙ + an Mn yn
is a unique solution modulo m = m1m2 ∙ ∙ ∙ mn.
(That is, there is a solution x with 0 ≤ x <m and all other solutions are
congruent modulo m to this solution.)
 The Chinese Remainder
Theorem
Proof:
Mk=m/mk for k = 1,2,…,n and m = m1m2 ∙ ∙ ∙ mn.

gcd(mk ,Mk ) = 1, by Theorem 1, there is an integer yk , an inverse of Mk modulo

mk, such that Mk yk ≡ 1 ( mod mk ).

if j ≠k , then mk divides Mk , therefore

aj Mj yj ≡ 0 (mod mk ) when j≠k

Let, the solution is

x = a1 M1 y1 + a2 M2 y2 + ∙ ∙ ∙ + an Mn yn

x mod m1 = (a1 M1 y1 + a2 M2 y2 + ∙ ∙ ∙ + an Mn yn ) mod m1

x mod m1 = (a1 M1 y1 mod m1+ 0 + ∙ ∙ ∙ + 0 ) mod m1 [aj Mj yj ≡ 0 (mod mk ) when j≠k]
x mod m1 = a1 M1 y1 mod m1
x mod m1 = ((a1 mod m1)(M1 y1 mod m1)) mod m1
x mod m1 = a1 (mod m1) [ Since Mk yk ≡ 1 ( mod mk )]
x ≡a1 (mod m1)

So x ≡ak (mod mk)

 The Chinese Remainder
Theorem
Proof (Continue):
If z is any other solution of the system, then for each k = 1,2,3 … , n
z≡ak (mod mk) and x ≡ak (mod mk)

Therefore some q1, q2  ℤ

z =ak + q1 mk
x =ak + q2mk ? – Wait it will be proved later
Thus
z - x=1+(q1 -q1) mk
This implies mk divides (z-x), for each i. Hence m1m2 ∙ ∙ ∙ mn divides (z-x)
z≡x (mod m1m2 ∙ ∙ ∙ mn )

Conversely , if z≡x (mod m1m2 ∙ ∙ ∙ mn ) then m1m2 ∙ ∙ ∙ mn divides (z-x). Consequently,

since m1, m2, ∙ ∙ ∙ mn are relatively prime numbers, so mi divides (z-x), for each i.
hence z≡x (mod mk)
And x ≡ak (mod mk)
So z ≡ak (mod mk)
Therefore z is a solution of given system
 The Chinese Remainder
Theorem
Example: Consider the 3 congruence's from Sun-Tsu’s problem:
x ≡ 2 ( mod 3),
x ≡ 3 ( mod 5),
x ≡ 2 ( mod 7).
– Let m = 3∙ 5 ∙ 7 = 105, M1 = m/3 = 35, M3 = m/5 = 21, M3 = m/7 = 15.
– 35y1 ≡ 1 (mod 3),
– 35 = 3⨯11+2
– 3 = 2⨯ 1 +1
– 35 = 3⨯11+(3-2) = 3⨯12-1 or -35 + 3⨯12 = 1
– y1 = -1 + 3ℤ ( i.e. 2,-1,-4 etc)
– 21y2 ≡ 1 (mod 5), y2 = 1+ 5ℤ ( i.e. 1, 6 , -4 etc)
– 15y3 ≡ 1 (mod 7), y3 = 1+ 7ℤ ( i.e. 1, 8 , -6 etc)
– x = a1M1y1 + a2M2y2 + a3M3y3
= 2 ∙ 35 ∙ 2 + 3 ∙ 21 ∙ 1 + 2 ∙ 15 ∙ 1 = 233

– x≡ 233 (mod 105) or x≡ 23 (mod 105)

– We have shown that 23 is the smallest positive integer that is a simultaneous solution. Check it!
 Back Substitution

Example: Use the method of back substitution to find all integers x such that x ≡ 1 (mod 5), x
≡ 2 (mod 6), and x ≡ 3 (mod 7).
Solution: Note: x ≡ 1 (mod 5), 5|x –1
x ≡ 1 (mod 5), according theorem, x – 1 = 5t or x = 5t +1
x ≡ 2 (mod 6) or 5t+1 ≡ 2 (mod 6)
Or 5t ≡ 1 (mod 6)
Or 5t ≡ 1+6 (mod 6)
Or 5t ≡ 7 (mod 6)
Or 5t ≡ 13 (mod 6)
Or 5t ≡ 19 (mod 6)
Or 5t ≡ 25 (mod 6)
Or t ≡ 5 (mod 6) Since gcd(5,6) = 1
t ≡ 5 (mod 6), according to theorem, t = 6u+5
x = 5(6u+5) + 1 = 30u+26
x ≡ 3 (mod 7) or 30u+26 ≡ 3 (mod 7)
Or 30u ≡ -23 (mod 7)
Or 30u ≡ 180 (mod 7)
Or u ≡ 6(mod 7) Since gcd(30,7) = 1
u= 7v+6,
x=30(7v+6)+26 = 210v+206
x-206 = 210v so x≡ 206 (mod 210)
 Computer Arithmetic with Large
Integers
 Use the Chinese remainder theorem to show that an integer a , with 0≤a
<m=m1.m2···mn, where the positive integers m1, m2 , . . . , mn are pairwise
relatively prime, can be represented uniquely by the n-tuple (a mod m1, a
mod m2, . . . , a mod mn).
Proof: suppose there exists distinct integers a and b, where 0≤a,b<m and the n-
tuples for a and b are identical. i.e. I,1≤i≤n, a ≡ b ( mod mi)

Since the mi are relatively prime, by Chinese remainder theorem, we get that
a ≡ b ( mod m)
From definition
m|(a-b)
Since 0≤a,b<m , so -m≤a-b<m
Hence a-b is divisiable by m iff (a-b)=0 which is a condradiction (i.e. a =b)
So there does not exist distinct integers a and b where 0≤a,b<m and the n-tuples for a
and b are identical
 Computer Arithmetic with Large
Integers
 Example: What are the pairs used to represent the nonnegative integers
less than 12 (3x4) when they are represented by the ordered pair where the
first component is the remainder of the integer upon division by 3 and the
second component is the remainder of the integer upon division by 4?
There pairs are unique.

Solution: a= {0,1,2,3,4,5,6,7,8,9,,10,11}

0 = (0 mod 3, 0 mod 4) = (0,0) 4 = {4 mod 3, 4 mod 4) = (3,1) 8= {4 mod 3, 4 mod 4)=(2,0)

1 = (1 mod 3, 1 mod 4) = (1,1) 5 = {5 mod 3, 5 mod 4) = (2,1) 9= {9 mod 3, 9 mod 4)=(0,1)

2 = (2 mod 3, 2 mod 4) = (2,2) 6 = {6 mod 3, 6 mod 4) = (0,2) 11={11 mod 3, 11 mod 4)=(2,3)

3 = (3 mod 3, 3 mod 4) = (0,3) 7 = {7 mod 3, 7 mod 4) = (1,3)

These pair are unique. i.e. (0,0) is unique.

 Computer Arithmetic with Large
Integers
 Consider four moduli 99,98,97,95 those are less than 100
By the Chinese remainder theorem, every nonnegative integer less than 99 · 98 · 97 · 95 =
89,403,930 can be represented uniquely by its remainders when divided by these four mod-
uli.

123,684 = (33, 8, 9, 89), because 123,684 mod 99 = 33 and so on.

Similarly, we represent, 413,456 = (32, 92, 42, 16).

To find the sum of 123,684 and 413,456, we work with these 4-tuples instead of these two
integers directly.
537,140 = (33, 8, 9, 89) + (32, 92, 42, 16)
= (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95)
= (65, 2, 51, 10).
We solve the follwing system of congruences

The solution is 537140.(Home Task)

 Fermat’s Little Theorem

Fermat’s Little Theorem: If p is prime and a is an integer not divisible by p, then

ap-1 ≡ 1 (mod p)

Proof: Given p is prime and p∤a.

Every integer is congruent to one of 0,1,2,3…., p-1( mod p)
Note: a ≡ b (mod p), aℤ, and one of *0,1,2,3 …. p-1}

Only focus on nonzero congruence class, we ignore 0 (because p∤a)

Multiply all these by a: a, 2a, 3a, … , (p-1)a

Show: a, 2a, 3a, … , a(p-1) is a rearrangement of 1,2,3, …, p-1

Case 1: None of a, 2a, 3a, … , a(p-1) are congruence of 0

Suppose r.a ≡ 0(mod p), then p|r.a,
This is impossible since p∤a and r<p
 Fermat’s Little Theorem

Fermat’s Little Theorem: If p is prime and a is an integer not divisible by p, then

ap-1 ≡ 1 (mod p)

Proof (continue):

Case 2: a, 2a, 3a, … , a(p-1) are distinct; no two are congruent to each other.
Pick two values: r.a and s.a
0<r<p
0<s<p
Suppose ra≡sa (mod p) then p | a(r-s)
But p∤a ,
-p<-s<0
So –p<r-s<p
p∤(r-s) if r-s ≠0, but it is assumed that r ans s are distinct.
So ra≢sa (mod p)

From case 1 and case 2, a, 2a, 3a, … , a(p-1) is a rearrangement of 1,2,3, …, p-1
 Fermat’s Little Theorem

Fermat’s Little Theorem: If p is prime and a is an integer not divisible by p, then

ap-1 ≡ 1 (mod p)

Proof (continue):

a, 2a, 3a, … , a(p-1) = 1,2,3, …, p-1(mod p)

(p-1)! ap-1 =(p-1)! (mod p)
ap-1 =1 (mod p)
 Fermat’s Little Theorem

Fermat’s little theorem is useful in computing the remainders modulo p of large

powers of integers.
Example: Find 7222 mod 11.
By Fermat’s little theorem, we know that 710 ≡ 1 (mod 11),
so 710 mod 11 = 1,

7222 = 722∙10 + 2 = (710)2272

7222 mod 11= (710)2272 mod 11

= 1. 49 mod 11
= 5

Hence, 7222 mod 11 = 5.

 Pseudoprimes

 By Fermat’s little theorem n > 2 is prime, where

2n-1 ≡ 1 (mod n).
 But if this congruence holds, n may not be prime. Composite integers n
such that 2n-1 ≡ 1 (mod n) are called pseudo-primes to the base 2.
Example: The integer 341 is a pseudo-prime to the base 2.
341 = 11 ∙ 31
2340 ≡ 1 (mod 341) (see in Exercise 37)

 We can replace 2 by any integer b ≥ 2.

Definition: Let b be a positive integer. If n is a composite integer, and bn-1 ≡
1 (mod n), then n is called a pseudo-prime to the base b.
 Robert Carmichael Carmichael Numbers
(1879-1967)

Definition: A composite integer n that satisfies the congruence bn-1 ≡ 1 (mod n) for
all positive integers b with gcd(b,n) = 1 is called a Carmichael number.

Example: The integer 561 is a Carmichael number.

To see this:
–561 is composite, since 561 = 3 ∙ 11 ∙ 17.
–If gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) = gcd(b, 17) =1.
–Using Fermat’s Little Theorem: b2 ≡ 1 (mod 3), b10 ≡ 1 (mod 11), b16 ≡ 1 (mod 17).
–Then
b560 = (b2) 280 ≡ 1 (mod 3),
b560 = (b10) 56 ≡ 1 (mod 11),
b560 = (b16) 35 ≡ 1 (mod 17).
–It follows that b560 ≡ 1 (mod 561) for all positive integers b with gcd(b,561) = 1. Hence, 561 is a
Carmichael number.
 Primitive Roots
Definition: A primitive root modulo a prime p is an integer r in Zp such that
every nonzero element of Zp ={ 1 2 3 , … , p-1} is a power of r.

Example: Since every element of Z11 is a power of 2, 2 is a primitive root of

11.
Powers of 2 modulo 11: 21 = 2, 22 = 4, 23 = 8, 24 = 5, 25 = 10, 26 = 9, 27 =
7, 28 = 3, 29 = 6, 210 = 1.
2,4,8,5,10,9,7,3,6,1  Unique
Example: Since not all elements of Z11 are powers of 3, 3 is not a primitive
root of 11.
Powers of 3 modulo 11: 31 = 3, 32 = 9, 33 = 5, 34 = 4, 35 = 1, and the
pattern repeats for higher powers.
Important Fact: There is a primitive root modulo p for every prime number
p.
 Primitive Roots
Primitive root of modulo 5

a1mod 5 a2 mod 5 a3 mod 5 a4 mod 5 Is

primitive
root
1 1 1 1 1 ⨯
2 2 4 3 1 √
3 3 4 2 1 √
4 4 1 4 1 ⨯
 Discrete Logarithms
Suppose
• p is prime
• r is a primitive root modulo p.
• aZp ={1, 2, … , p-1},
• there is a unique exponent e such that r e = a in Zp,
• r e mod p = a.

Example:
A prime, p=11,
A primitive root, r = 2,
An integer, a= 2Zp,
r e = a  21=2
e = 1,
21 mod 11 = a
 Discrete Logarithms
Definition:

Suppose that

p is prime,
r is a primitive root modulo p, and
a is an integer between 1 and p −1, inclusive. If re mod p = a and 1 ≤ e ≤ p − 1,

we say that

e is the discrete logarithm of a modulo p to the base r

and we write

logr a = e (where the prime p is understood).

 Discrete Logarithms
Example 1: Find the discrete logarithms of 3 modulo 11 to the base 2.

Suppose that
p =11
r = 2 (base)
a =3 is an integer between 1 and 10, inclusive.

a mod 5 → a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
a↓
2 2 4 8 5 10 9 7 3 6 1

e=8
logr a = e
→log2 3 = 8
 Discrete Logarithms
Example 1: Find the discrete logarithms of 5 modulo 11 to the base 2.

Suppose that
p =11
r = 2 (base)
a =5 is an integer between 1 and 10, inclusive.

a mod 5 → a1 a2 a3 a4 a5 a6 a7 a8 a9 a10
a↓
2 2 4 8 5 10 9 7 3 6 1

e=4
logr a = e
→log2 5 = 4
 Query???

1 2 3 4 ....
 x    y  ( x  y )  ?

  1
 x 1 x ?
 x 1  ?
x

 x( | x )  ?  x    y  ( x  y )  ?

 1
1 2 3 4 .... ?
 x 1  ?
1  1  1  1  1 .........  ? x