The RSA Algorithm

Supplementary Notes

Prepared by Raymond Wong

Presented by Raymond Wong 1
 S T
1 1
2 2
3 3

e.g.1 (Page 3) 4
5
4
5
6 6

 Consider f3(x) = x.73 A

permutation
Consider each non-zero x in Z7
{0, 1, 2, 3, 4, 5, of {1, 2, 3, 4,
6} 5, 6}
x=1 f3(1) = 1.73 = 3
1 3
x=2 f3(2) = 2.73 = 6 Why?
2 6
x=3 f3(3) = 3.73 = 2 This is because
3 2
7 is a prime
x=4 f3(4) = 4.73 = 5 number.
4 5
x=5 f3(5) = 5.73 = 1
5 1
x=6 f3(6) = 6.73 = 4
6 4
2
 S T
1 1
2 2
3 3

e.g.1 4
5
4
5
6 6

 Illustration of Lemma 2.20

Lemma 2.20: 7 is a prime number. Consider a value 3 which is in Z 7.
the function f3(x) = x.73 is 1-to-1. In particular,

f3(1), f3(2), f3(3), f3(4), f3(5), f3(6)

(or 1.73, 2.73, 3.73, 4.73, 5.73, 6.73)

are a permutation of the set {1, 2, 3, …., 6}.

Why is it correct?

3
emma 2.20: 7 is a prime number. Consider a value 3 which is in Z 7.
he function f3(x) = x.73 is 1-to-1. In particular,

f3(1), f3(2), f3(3), f3(4), f3(5), f3(6)

(or 1.73, 2.73, 3.73, 4.73, 5.73, 6.73)

re a permutation of the set {1, 2, 3, …., 6}.

We prove by contradiction. S T
Suppose that f3(x) is not 1-to-1. …
…
That is, there exist two integers x, y x
v
such that
y
xy …
and …
f3(x) = f3(y)
Since 7 is a prime number, by Corollary 2.17, we know that 3 has a
multiplicative inverse in Z7 (denoted by 3-1) (i.e., 3.73-1 = 1)
Consider x = f3(x).73-1 =y.7(3.73- Thus, we have
= x.71
= f3(y).73-1 =y
1
) .71 x=y
= x.7(3.73-
=(y.73).73-1 = This leads to a
=) (x.73).73-1
1
y contradiction!
4
 S T
f3(x) = x.73
1 1
2 2
3 3

e.g.2 (Page 5) 4
5
4
5
6 6

 Private-key cryptosystems
a= fa(x) a= f-1a(x)
3 3

key Encryption function key Decryption function

x Encryption y y Decryption x

e.g. 4 e.g. 5 e.g. 5 e.g. 4

ppose that the encryption and decryption functions are known to the public.
the key is kept privately. Then, we can ensure that the encryption/decryption is
ure. 5
 S T
Given x, we can compute y = f3(x) efficiently. f3(x) = x.73
1 1
2 2
3 3

e.g.2
Suppose that I am the attacker.
However, knowing y does not provide
4
5
4
5
6 6
enough information to recover x efficiently.
Thus, we say that f3(x) is a one-way function.
 Private-key cryptosystems
I know that a=
f3(x) is one-to-one.
fa(x) a= f-1a(x)
3
Since function3f3(x) is a one-to-one
function, f3(x)key
mustEncryption
have an inverse f-13(x).
function key Decryption function
However, knowing that the inverse f-13(x) exists does not
help in finding x (given y).
Thus, given y, it might be hard to calculate (at the attacker side).
x Encryption y y Decryption x

e.g. 4 e.g. 5 e.g. 5 e.g. 4

6
 If we can ensure the following, we are confident to say that the
encryption/decryption is secure.
Given (1) the encryption function, (2) the decryption function and
(3) the public key, it is difficult to derive the secret-key (at the

In this
e.g.2
attacker side)
(i.e.,lecture,
it is notwe
efficient to derive
will illustrate this the secret-key). This secret key
concept for has some
Public-key cryptosystems
The public-key
 cryptosystem. relationships
with the public
key.
Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

ppose that the encryption and decryption functions are known to the public.
uppose that the public key is known to the public. How can we ensure
But the secret-key is kept privately. this statement?
7
Then, we should ensure that the encryption/decryption is secure.
 Lemma 2.3:
(a.b) mod 11 = ((a mod 11) . (b mod 11)) mod 11
= ((a mod 11) . b) mod 11

e.g.3 (Page 8) Note that

73 mod 11
= (7.7.7) mod 11
= ((7.7).7) mod 11
 E.g., = ([(7.7) mod 11].7) mod 11
= ((7.117) .7) mod 11
= (7.117) .
7
If 7  Z11, then = 7.117 .
7
11
11

75 mod 11 = [Link].117

8
 32.34 = 32+4
(34)2 = 34x2
e.g.4 (Page 10)
 Illustration of Lemma 2.19
Lemma 2.19:

(32 mod 7) .7 (34 mod 7) = 32+4 mod 7

(34 mod 7)2 = 34x2 mod 7

9
 e.g.5 (Page 12)
 If a = 3,
 please find the following

a0 mod 7 1

a1 mod 7 3

a2 mod 7 2

a3 mod 7 6 The pattern re-

a4 mod 7 4 appear for every

a5 mod 7 5 group of 6

a6 mod 7 1 elements

a7 mod 7 3

a8 mod 7 2

a9 mod 7 6

a10 mod 7 4

a11 mod 7 5

a12 mod 7 1 10
 e.g.6 (Page 12)
 If a = 5,
 please find the following

a0 mod 7 1

a1 mod 7 5

a2 mod 7 4

a3 mod 7 6 The pattern re-

a4 mod 7 2 appear for every

a5 mod 7 3 group of 6

a6 mod 7 1 elements

a7 mod 7 5

a8 mod 7 4 We observe that

a9 mod 7 6 a6 mod 7 = 1

a10 mod 7 2

a11 mod 7 3 or a7-1 mod 7 = 1

a12 mod 7 1 11
e.g.7 (Page 13)
 Illustration of Theorem 2.21
Theorem 2.21 (Fermat’s Little Theorem):
7 is a prime number. Then, for any non-zero a  Z7,
a7-1 mod 7 = 1
Why is it
correct?

12
 Theorem 2.21 (Fermat’s Little Theorem):
7 is a prime number. Then, for any non-zero a  Z7,
a7-1 mod 7 = 1

e.g.7
Illustrate with a = 3. S T
Consider Lemma 2.20 1 1
We know that 1.73, 2.73, 3.73, 4.73, 5.73, 6.73 2 2
3 3
(we call Group A)
4 4
are a permutation of 1, 2, 3, 4, 5, 6 5 5
(we call Group B). 6 6
Thus, we have
the product of all numbers in Group A= the product of all numbers in Group B
the product of all numbers in Group A (mod 7) = the product of all numbers in Group
B (mod 7)
(1.73).
7
.
(2 73)
. .
7 (3 73)
. . .
7 (4 73)
. .
7
.
(5 73) .
7
.
(6 73) = 1
. . .
7 2 7 3 7 4 7 5 7 6

Lemma 2.20: 7 is a prime number. Consider a value 3 which is in Z 7.

the function f3(x) = x.73 is 1-to-1. In particular,

f3(1), f3(2), f3(3), f3(4), f3(5), f3(6)

(or 1.73, 2.73, 3.73, 4.73, 5.73, 6.73)
13
Theorem 2.21 (Fermat’s Little Theorem):
7 is a prime number. Then, for any non-zero a  Z7,
a7-1 mod 7 = 1

e.g.7
Illustrate with a = 3. S T
Consider Lemma 2.20 1 1
We know that 1.73, 2.73, 3.73, 4.73, 5.73, 6.73 2 2
3 3
(we call Group A)
4 4
are a permutation of 1, 2, 3, 4, 5, 6 5 5
(we call Group B). 6 6
Thus, we have
the product of all numbers in Group A= the product of all numbers in Group B
the product of all numbers in Group A (mod 7) = the product of all numbers in Group
B (mod 7)
(1.73).
7(2 73) 7 (3 73) 7 (4 73) 7 (5 73) 7 (6 73) = 1 7 2 7 3 7 4 7 5 7 6
. . . . . . . . . . . . . .

1 .73 .7 2 .73 .7 3 .73 .7 4 .73 .7 5 .73 .7 6 .73 = 1 .7 2 .7 3 .7 4 .7 5

17 672 .7 3 .74 .7 5 .76 .7 3 .73 .7 3 .73 .7 3 .73 = 1 .7 2 .7 3 .7 4 .7 5
. .

(1 .726.7 3 .74 .7 5 .76) .7 (3 .73 .7 3 .73 .7 3 .73) = 1 .7 2 .7 3 .7 4 .7

5 .7 6 (1 .72 .7 3 .74 .7 5 .76) .7 (37-1 mod 7) = 1 .7 2 .7 3 .7 4 .7 5 .7 6
Let x = 1 .72 .7 3 .74 .7 5 .76 Consider x .7 (37-1 mod 7) =
We have x .7 (37-1 mod 7) = x x-1 .7 x .7 (37-1 mod 7) = x-1 .7 x
Since
x 7 is a prime number, (x-1 .7 x) .7 (37-1 mod 7) = x-1 .7
x 37-1 mod 7 = 1 14
x has a multiplicative inverse x in -1
 Theorem 2.21 (Fermat’s Little Theorem):
7 is a prime number. Then, for any non-zero a  Z7,
a7-1 mod 7 = 1

e.g.8 (Page 14)

 Illustration of Corollary 2.22
Corollary 2.22 (Fermat’s Little Theorem, Version 2):
7 is a prime number. Then, for any positive integer a that
is not a multiple of 7,
a7-1 mod 7 = 1
Why is it
Consider a 7-1
mod 7 correct?
= (a . a . a . a . a . a) mod 7
= [(a mod 7) . (a mod 7) . (a mod 7) . (a mod 7) . (a mod 7) . (a mod 7)] mod 7
Note that (a mod 7)  Z7
= (a mod 7)7-1 mod 7
a is not a multiple
If (a mod 7) is non-zero in Z7,
of 7.
we have (a mod 7) mod 7 = 1
7-1

i.e., a7-1 mod 7 = 1 15

 e.g.9 (Page 15)
 Illustration of Corollary 2.X1
Corollary 2.X1 (Fermat’s Little Theorem, Version 2):
7 is a prime number. Consider a non-negative integer 15.
Then, for any positive integer a that is not a multiple of 7,
a15 mod 7 = a15 mod (7-1) mod 7

Why is it
e.g., a15 mod 7 = a15 mod (7-1) mod 7
correct?
= a15 mod 6 mod 7 This proof is skipped.
You can prove it by
= a3 mod 7
yourself.
If a = 5, we have
515 mod 7 = 53 mod 7
=6 16
Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.10 (Page 19) d = e-1 mod T

Choose p =
1. Choose 2 large prime numbers p and q 5
q=
We can calculate
11
2. Set n = pq and T = (p-1)(q-1) n = 5 11 = 55
.

T = (5-1)(11-1) = 4.10 =
40
3. Choose e1 so that gcd(e, T) = 1 Choose e = 7
(Note: gcd(7, 40) =
4. Calculate d = e-1 mod T 1)
We can find
(i.e., the multiplicative inverse d = 7-1 mod 40
of e in ZT) We can use Extended GCD
5. Publish e, n as public key algorithm to find
d = 23.

6. Keep d as secret key Public key : (e, n) = (7, 55)

Secret key : d =
17
23
Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.11 (Page 20) d = e-1 mod T

y = 127 mod 55
= 35831808 mod 55 = 23
(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

12 23

18
Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.11 d = e-1 mod T

x = 2323 mod 55
(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

12 23 23 12

x = 20880467999847912034355032910567 mod
55 = 12 19
 Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.11 d = e-1 mod T

(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

Can the encrypted value y be decrypted correctly?

Is the following correct? Is the following correct?

“(xe mod n)d mod n = x” “xed mod n = x” 20
e.g.12 (Page 21)

Is the following correct?

“xed mod n = x” 21
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))
Consider d = e-1 mod T Corollary 2.22 (Fermat’s Little Theorem, Version 2):
p is a prime number. Then, for any positive integer a that
We can re-write it as follows. is not a multiple of p,
ed mod T = 1 a p-1 mod p = 1
We can further re-write it as follows.
We consider two cases.
ed = Tk + 1 where k is an integer
(a) x(q-1)k is not a multiple of p
Consider xed mod p= xTk+1 mod p
(b) x(q-1)k is a multiple of p
= x x mod p
Tk

= x(p-1)(q-1)kx mod p
= (x(q-1)k)p-1x mod p
= [((x(q-1)k)p-1 mod p) . (x mod p)] mod p
22
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))
Corollary 2.22 (Fermat’s Little Theorem, Version 2):
p is a prime number. Then, for any positive integer a that
is not a multiple of p,
a p-1 mod p = 1

We consider two cases.

(a) x(q-1)k is not a multiple of p
Consider xed mod p
(b) x(q-1)k is a multiple of p

= [((x(q-1)k)p-1 mod p) . (x mod p)] mod p

23
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))
Corollary 2.22 (Fermat’s Little Theorem, Version 2):
p is a prime number. Then, for any positive integer a that
is not a multiple of p,
Consider xed mod p a p-1 mod p = 1

= [((x(q-1)k)p-1 mod p) . (x mod p)] mod p We consider two cases.

= [1 . (x mod p)] mod p (a) x(q-1)k is not a multiple of p
= (x mod p) mod p (b) x(q-1)k is a multiple of p
= x mod p

24
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x, e.g. x1000 is a multiple of
x mod q = xed mod q 7
3. Prove that, if 0  x < n, Since 7 is prime, x is
x = xed mod n (by (1) and (2)) Italso
can abe shown of
multiple by 7.
proof
by contradiction.
We know that x(q-1)k is a multiple
of p.
Consider xedSincemod pp is prime, x is also a
multiple of p.
= [((x(q-1)k)p-1 mod p) . (x mod p)] mod p We consider two cases.
= [((x(q-1)k mod p)p-1 mod p) . (x mod p)] mod p (a) x(q-1)k is not a multiple of p
= [((0)p-1 mod p) . (x mod p)] mod p (b) x(q-1)k is a multiple of p
= [0 . (x mod p)] mod p
=0 We deduce that
Since x is also a multiple of p, x(q-1)k mod p = 0
we have x mod p = 0 Thus, x mod p = xed mod p 25
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x, The second proof is
x mod q = xed mod q similar to the first
3. Prove that, if 0  x < n, proof.
x = xed mod n (by (1) and (2))

26
 Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))

efore we prove this statement, we want to give some properties of prime numbe
If p and q are both prime numbers and both divides z,
then pq divides z.
e.g., p = 3, q = 11, z = 99
3, 11 both divides 99.
We know that 33 (=pq) also divides 99.
If p and q are not prime numbers and both divides z,
then pq may not divide z.
e.g., p = 6, q = 15, z = 60
6, 15 both divides 60.
We know that 90 (=pq) does not divide 60. 27
 Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p If p and q are both prime numbers
2. Prove that, for all x, and both divides z,
x mod q = x mod q
ed
then pq divides z.
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))
From (1), we know that From (2), we know that
x mod p = xed mod p x mod q = xed mod q
It can be re-written as follows. It can be re-written as follows.
xed =ip+x where i is an integer. xed =jq+x where j is an integer.
It can further be re-written as follows. It can further be re-written as follows.
xed – x =ip xed – x =jq
Let z = xed - x Note that xed – x (which is equal to z)
We have z = ip ………………..(*) We have z = jq ………………..(**)
Thus, p divides z. Thus, q divides z.
Since p and q are both prime numbers and
both divides z, pq divides z.
28
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))

Let z = xed - x

Since p and q are both prime numbers and

both divides z, pq divides z.
29
Is the following correct? p, q prime
“xed mod n = x” n = pq
T = (p-1)(q-1)

e.g.12
e s.t. gcd(e, T) = 1
We want to prove the following d = e-1 mod T
1. Prove that, for all x,
x mod p = xed mod p
2. Prove that, for all x,
x mod q = xed mod q
3. Prove that, if 0  x < n,
x = xed mod n (by (1) and (2))

Let z = xed - x
Since p and q are both prime numbers and
both divides z, pq divides z.
We can write as follows.
z = pqk where k is an integer
z = nk
xed-x = nk
xed= nk + x
Since 0  x < n, we can re-write the above as follows.
xed mod n = x
30
 Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.13 (Page 31) d = e-1 mod T

(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

Can the encrypted value y be decrypted correctly?

Yes
Is the following correct? Is the following correct?
“(xe mod n)d mod n = x” “xed mod n = x” 31
 Public key : (e, n) = (7, 55) p, q prime
Secret key : d = 23 n = pq
T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.13 (Page 31) d = e-1 mod T

(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

Why is this RSA algorithm secure?

ote that the public key, the encryption function and the decryption function
known to the public.
f I am the attacker, after reading value y, I want to know the original value x.
32
How can I derive the original value x?
 Public key : (e, n) = (7, 55)First Way for Attack: p, q prime
Secret key : d = 23 Since I know that the formula n = pq
y = xe mod n, T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.13
i.e., (xe mod n)1/e mod
n
Slow Operation!
if I have value y,
I will try to calculate d = e-1 mod T
the e-th root (mod n)

(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

x Encryption y y Decryption x

Why is this RSA algorithm secure?

ote that the public key, the encryption function and the decryption function
known to the public.
f I am the attacker, after reading value y, I want to know the original value x.
33
How can I derive the original value x?
 Public key : (e, n) = (7, 55)Second Way for Attack: p, q prime
Secret key : d = 23 Since I know value n (in the n = pq
public key) and n = pq, T = (p-1)(q-1)
e s.t. gcd(e, T) = 1
e.g.13
With p and q, I can I will try to factorize value n
derive d easily. d = e-1 mod T
to find p and q such that
With d, I can decrypt y n = pq.
by the decryption Factorization is a Slow Operation!
function.
(e, n) = (7, d=
y = xe mod x = yd mod
55) 23
n n

Public Secret
key Encryption function key Decryption function

Nobody know how to

factor a number
quickly!
x Encryption y y Decryption x

Why is this RSA algorithm secure?

ote that the public key, the encryption function and the decryption function
known to the public.
f I am the attacker, after reading value y, I want to know the original value x.
34
How can I derive the original value x?
e.g.14 (Page 38)

5010 (in base 10) = 1100102 (in base 2)
(e5e4e3e2e1e0)
 50 is equal to
1.25+1.24+0.23+0.22+1.21+0.20
 If we only consider 1 only (not 0 in the
base 2/binary representation),
 50 is equal to
1.25+1.24+1.21

35
e.g.15 (Page 39)
 Second approach
If e = 10120, then
 e-1 multiplications e-1 = 10120
 Third approach
 2 log2 e multiplications

If e = 10120, then
2 log2 e = 796

36
 e.g.16 (Page 43)
x (x mod 3, x mod 5)
S T

0 (0, 0)
1 (0, 1)
2 (0, 2)
3 (0, 3)
4 (0, 4)
5 (1, 0)
6 (1, 1)
7 (1, 2)
8 (1, 3)
9 (1, 4)
10 (2, 0)
11 (2, 1)
12 (2, 2)
15 13 (2, 3) 15
elements 14 (2, 4) elements 37
 e.g.17 (Page 44)
 Illustration of Theorem 2.24
Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2
and
x mod 5 = 4
have one and only one solution for an integer x between 0 and 3.5-1 (= 14

Why is it
correct?
These equations have the solution x = 14.

38
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
3.3-1 mod 5= 1
x mod 3 = 2

e.g.17
d 5.5-1 mod 3 = 1
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n the following, we want to construct a value of x such that
a) this value is between 0 and 14.
b) this value satisfies the equations “x mod 3 = 2” and “x mod 5 = 4”.

Now, we want to see how to construct a value of y such that

(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
Since 3 and 5 are relatively prime, we have gcd(3, 5) = 1.
3 has a multiplicative inverse 3-1 in Z5 (i.e., 3.3-1 mod 5= 1)
5 has a multiplicative inverse 5-1 in Z3. (i.e., 5.5-1 mod 3 = 1)

39
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
3.3-1 mod 5= 1
x mod 3 = 2

e.g.17
d 5.5-1 mod 3 = 1
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n the following, we want to construct a value of x such that
a) this value is between 0 and 14.
b) this value satisfies the equations “x mod 3 = 2” and “x mod 5 = 4”.

Now, we want to see how to construct a value of y such that

(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
We set y = 2.5.5-1 + 4.3.3-1 Ok!
This value satisfies the equations. Why?
Consider y mod 3 = (2.5.5-1 + 4.3.3-1)
mod
= [(23 5 5 mod 3) + (4.3.3-1 mod 3) ] mod
. . -1

= [(2.1 mod 3) + 0 ] mod 3

3
40
=2
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
3.3-1 mod 5= 1
x mod 3 = 2

e.g.17
d 5.5-1 mod 3 = 1
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n the following, we want to construct a value of x such that
a) this value is between 0 and 14.
b) this value satisfies the equations “x mod 3 = 2” and “x mod 5 = 4”.

Now, we want to see how to construct a value of y such that

(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
We set y = 2.5.5-1 + 4.3.3-1 Ok! Ok!
This value satisfies the equations. Why?
Consider y mod 5 = (2.5.5-1 + 4.3.3-1)
mod
= [(25 5 5 mod 5) + (4.3.3-1 mod 5) ] mod
. . -1

= [0+ (4.1 mod 5) ] mod 5

5
41
=4
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
3.3-1 mod 5= 1
x mod 3 = 2

e.g.17
d 5.5-1 mod 3 = 1
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n the following, we want to construct a value of x such that
a) this value is between 0 and 14.
b) this value satisfies the equations “x mod 3 = 2” and “x mod 5 = 4”.

Now, we want to see how to construct a value of y such that

(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
We set y = 2.5.5-1 + 4.3.3-1
We want to show that x must be between 0 and
If we set x = (y mod 15) (NOTE: 15 = 3.5), 14.
then x is between 0 and 14
and x satisfies the equations “x mod 3 = 2” and “x mod 5 = 4”. 42
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
y = 3q1 +2
x mod 3 = 2

e.g.17
d y = 5q2 +4
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n theIffollowing,
we set x = we(ywant
modto construct
15) (NOTE:a15
value
= [Link]
5),x such that
a) this value
then x isisbetween
between00andand14
14.
b) this
and value satisfies
x satisfies the
the equations
equations “x“x mod
mod 3=3= 2”2”
andand
“x“x mod
mod 5 = 4”.
5=
4”.
want to
Now, we know see
that howis
there toaconstruct
value of ya such
valuethat
of y such that
(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
we2,can rewrite it as
Since y mod 3 = y = 3q1 +2 where q1 is an integer.
we4,can rewrite it as
Since y mod 5 = y = 5q2 +4 where q2 is an integer.

43
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
y = 3q1 +2
x mod 3 = 2

e.g.17
d y = 5q2 +4
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n theIffollowing,
we set x = we(ywant
modto construct
15) (NOTE:a15
value
= [Link]
5),x such that
a) this value
then x isisbetween
between00andand14
14. Ok!
b) this
and value satisfies
x satisfies the
the equations
equations “x“x mod
mod 3=3= 2”2”
andand
“x“x mod
mod 5 = 4”.
5=
4”.
want to
Now, we know see
that howis
there toaconstruct
value of ya such
valuethat
of y such that
(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
we can rewrite it as y = 15q3 +x where q3 is an integer.
Since x = (y mod 15),
x = y - 15q3
We can re-write as = (3q1 + 2) - 15q3
follows. = 3q1 + 2 - 15q3
x mod 3 = 2 = 3(q1 - 5q3) + 2 44
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
y = 3q1 +2
x mod 3 = 2

e.g.17
d y = 5q2 +4
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.
n theIffollowing,
we set x = we(ywant
modto construct
15) (NOTE:a15
value
= [Link]
5),x such that
a) this value
then x isisbetween
between00andand14
14. Ok! Ok!
b) this
and value satisfies
x satisfies the
the equations
equations “x“x mod
mod 3=3= 2”2”
andand
“x“x mod
mod 5 = 4”.
5=
4”.
want to
Now, we know see
that howis
there toaconstruct
value of ya such
valuethat
of y such that
(a) this value can be either in [0, 14] or not,
(b) this value satisfies the equations “y mod 3 = 2” and “y mod 5 = 4”.
we can rewrite it as y = 15q3 +x where q3 is an integer.
Since x = (y mod 15),
x = y - 15q3
We can re-write as = (5q2 + 4) - 15q3
follows. = 5q2 + 4 - 15q3
x mod 5 = 4 = 5(q2 - 3q3) + 4 45
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2

e.g.17
d
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.

Before we go to the proof, we illustrate a concept.

Consider a function f(x) from S to T where S and T has the same sizes.

Suppose that, given a single value y,

S x T y
I know how to find the corresponding value x.
0 0
1 1 Suppose that, given any value y,
2 2 I know how to find the corresponding value x.

This function must be a bijection function.

46
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2

e.g.17
d
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.

Consider a function f(x) = (x mod 3, x mod 5)

S
x T (x mod 3, x mod 5)
0 (0, 0)
1 (0, 1)
2 (0, 2)
… … In the first part of the proof,
we have already shown that
12 (2, 2) we can find the value x from
13 (2, 3) the two equations
14 (2, 4) (or this pair (2, 4))
“x mod 3 = 2” and “x mod 5 47
heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2

e.g.17
d
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.

Consider a function f(x) = (x mod 3, x mod 5)

S
x T (x mod 3, x mod 5)
0 (0, 0)
1 (0, 1)
2 (0, 2)
… …
Similarly,
12 (2, 2) we can find the value x from
13 (2, 3) other two equations
14 (2, 4) (or another pair (2, 3))

“x mod 3 = 2” and “x mod 5 48

heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2

e.g.17
d
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.

Consider a function f(x) = (x mod 3, x mod 5)

S
x T (x mod 3, x mod 5)
0 (0, 0)
1 (0, 1)
2 (0, 2)
… …
Similarly,
12 (2, 2) we can find the value x from
13 (2, 3) each possible two equations
14 (2, 4) (or each pair (2, 3))

“x mod 3 = 2” and “x mod 5 49

heorem 2.24:
nce 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2

e.g.17
d
x mod 5 = 4
ve one and only one solution for an integer x between 0 and 3.5-1 (= 14)
We want to do the following.
1. Given the equations “x mod 3 = 2” and “x mod 5 = 4”,
there is at least one solution for these two equations.
2. This solution is one and only one.

Consider a function f(x) = (x mod 3, x mod 5)

S
x T (x mod 3, x mod 5)
0 (0, 0) Note that S and T have the
1 (0, 1) same sizes.
2 (0, 2)
According to the concept
… … we just described,
12 (2, 2) we know that this function
13 (2, 3) is a bijection function.
14 (2, 4) We conclude that there is
one and only one solution. 50
 e.g.18 (Page 47)
 E.g., We want to find a solution x in Z66 of
the following equations.
We can use the
x mod 6 = 3 extended GCD
x mod 11 = 7 algorithm and
find the answer 6-
Step 1: (a) Find the multiplicative inverse 6-1 of 6 in Z11
1
is 2
(b) Find the multiplicative inverse 11-1 of 11 in Z6 We can use the
extended GCD
algorithm and
Step 2: Construct y= 3.11.11-1+ 7.6.6-1 find the answer
11 -1
is 5
y = 3 11 5 + 7.6.2
. .
Step 3: Find x = (y mod 66) where 66 is 6.11 = 249
x = 249 mod 66
51
= 51
 e.g.19 (Page 48)
 E.g. We are given the following functions.
2 if k = 3
f(k) =
4 if k = 5

1 if k = 3 0 if k = 3
g(k) = h(k) =
0 if k = 5 1 if k = 5
Find a single equation to express f(k) in terms of g(k) and h(k).

We can express f(k) = 2.g(k) + 4.h(k)

Let us verify whether this equation is correct.
When k = 3, When k = 5,
f(3) = 2.g(3) + 4.h(3) f(5) = 2.g(5) + 4.h(5)
= 2.1 + 4.0 = 2.0 + 4.1
=2 =4
52
 3.3-1 mod 5= 1

e.g.20 (Page 48) 5.5-1 mod 3 = 1

 In the proof of Theorem 2.24

Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations
x mod 3 = 2
and
x mod 5 = 4
have one and only one solution for an integer x between 0 and 3.5-1 (= 1

In the proof of Theorem 2.24,

we create a value y = 2.5.5-1 + 4.3.3-1

Why are we so smart to

create this “magic”
formula?
53
Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations 3.3-1 mod 5= 1
x mod 3 = 2
and
e.g.20
x mod 5 = 4
5.5-1 mod 3 = 1

have one and only one solution for an integer x between 0 and 3.5-1 (= 14)
y = 2.5.5-1 + 4.3.3-1 Why are we so smart to
create this “magic”
Consider the main set of equations. formula?
y mod 3 = 2
y mod 5 = 4
Step 1: We want to find a single equation to express y.
Similarly, if we have two sets of equations, then we can express y in a single
equation.
 mod 3 = 1  mod 3 = 0
 mod 5 = 0 where  and  are integers.
 mod 5 = 1
We can write y = 2 + 4
Let us verify whether this equation is correct.
Consider y mod 3 Consider y mod 5
= 2 + 4 mod 3 = 2 + 4 mod 5
= [(2 mod 3) + (4 mod 3)] mod 3 = [(2 mod 5) + (4 mod 5)]
= (2.1 + 4.0) mod 3 =mod
(2.05+ 4.1) mod 5
=2 =4 54
Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations 3.3-1 mod 5= 1
x mod 3 = 2
and
e.g.20
x mod 5 = 4
5.5-1 mod 3 = 1

have one and only one solution for an integer x between 0 and 3.5-1 (= 14)
y = 2.5.5-1 + 4.3.3-1 Why are we so smart to
create this “magic”
Consider the main set of equations. formula?
y mod 3 = 2  = 5.5-1
y mod 5 = 4
Step 1: We want to find a single equation to express y.
Similarly, if we have two sets of equations, then we can express y in a single
equation.
 mod 3 = 1  mod 3 = 0
 mod 5 = 0 where  and  are integers.
 mod 5 = 1
We can write y = 2 + 4
We know that  = 5q.
Step 2: We want to find  and  Thus, 5q mod 3 = 1
Consider  q is a multiplicative inverse of 5 in Z3
 mod 3 = 1 i.e., q = 5-1
 mod 5 = 0 We have  = 5q = 5.5-1
55
 is a multiple of 5 (i.e.,  = 5q where q is an
Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations 3.3-1 mod 5= 1
x mod 3 = 2
and
e.g.20
x mod 5 = 4
5.5-1 mod 3 = 1

have one and only one solution for an integer x between 0 and 3.5-1 (= 14)
y = 2.5.5-1 + 4.3.3-1 Why are we so smart to
create this “magic”
Consider the main set of equations. formula?
y mod 3 = 2  = 5.5-1
y mod 5 = 4  = 3.3-1
Step 1: We want to find a single equation to express y.
Similarly, if we have two sets of equations, then we can express y in a single
equation.
 mod 3 = 1  mod 3 = 0
 mod 5 = 0 where  and  are integers.
 mod 5 = 1
We can write y = 2 + 4 is a multiple of 3 (i.e.,  = 3q where q is an
Step 2: We want to find integer.)
and 
We know that  = 3q.
Consider  Thus, 3q mod 5 = 1
 mod 3 = 0 q is a multiplicative inverse of 3 in Z5
 mod 5 = 1 i.e., q = 3-1
56
We have  = 3q = 3.3-1
Theorem 2.24:
Since 3 and 5 are relatively prime integers, then the equations 3.3-1 mod 5= 1
x mod 3 = 2
and
e.g.20
x mod 5 = 4
5.5-1 mod 3 = 1

have one and only one solution for an integer x between 0 and 3.5-1 (= 14)
y = 2.5.5-1 + 4.3.3-1 Why are we so smart to
create this “magic”
Consider the main set of equations. formula?
y mod 3 = 2  = 5.5-1
y mod 5 = 4  = 3.3-1
Step 1: We want to find a single equation to express y.
Similarly, if we have two sets of equations, then we can express y in a single
equation.
 mod 3 = 1  mod 3 = 0
 mod 5 = 0 where  and  are integers.
 mod 5 = 1
We can write y = 2 + 4
Step 2: We want to find  and 

Note that y = 2 + 4
= 2.5.5-1 +
4.3.3-1 57