Lemmas and Theories

Question 1

Lemma 1

Answer 1

A composite integer 𝑛 > 1, has a prime factor 𝑝 ≤ √𝑛.

Question 2

Theorem 1

Answer 2

If 𝑑|𝑎 and 𝑑|𝑏, then for any integers 𝑠 and 𝑡,
𝑑 | (𝑠𝑎 + 𝑡𝑏)
We call (𝑠𝑎 + 𝑡𝑏) a linear sum, or linear combination, of 𝑎 and 𝑏.

Question 3

Lemma 2

Answer 3

Let 𝑎 and 𝑏 be two positive integers, where 𝑎 > 𝑏. Then,
gcd(𝑎, 𝑏) = gcd(𝑏, 𝑎 𝑚𝑜𝑑 𝑏).

Question 4

Lemma 3

Answer 4

Let 𝑟1 and 𝑟2 each be a linear sum of integers (𝑎, 𝑏), and let 𝑟3 be a linear
sum of (𝑟1, 𝑟2). Then, 𝑟3 is a linear sum of the original integers (𝑎, 𝑏).

Question 5

Theorem 2

Answer 5

Let 𝑎 and 𝑏 be positive integers, 𝑎 > 𝑏. There exist integers 𝑠 and 𝑡 such
that
gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏
Furthermore, gcd(𝑎, 𝑏) is the smallest positive integer which is a linear sum of (𝑎, 𝑏)

Question 6

Lemma 4

Answer 6

Let 𝑎 be the larger of the two inputs to GCD algorithm. The number of
iterations (thus the number of mod operations) is at most 2 log2 𝑎.

Question 7

Lemma 5

Answer 7

Suppose the larger input to GCD algorithm is 𝑎 ≤ 𝐹𝑛 for some integer 𝑛. The
number of iterations of the algorithm (the number of mod operations) is at most 𝑛 − 2.

Question 8

Lemma 6

Answer 8

Let 𝑥, 𝑦, 𝑧, and 𝑛 be positive integers.
(1) (𝑥 ∗ 𝑦) mod 𝑛 = ((𝑥 mod 𝑛) ∗ (𝑦 mod 𝑛) ) mod 𝑛
(2) (𝑥 ∗ 𝑦 ∗ 𝑧) mod 𝑛 = ((𝑥 ∗ 𝑦) mod 𝑛) ∗ 𝑧) mod 𝑛

Question 9

Theorem 3

Answer 9

Let 𝑥 and 𝑛 be two positive integers. The inverse of 𝑥 modulo 𝑛 exists, and
is unique, if and only if gcd(𝑥, 𝑛) = 1

Question 10

Lemma 7

Answer 10

Given positive integers 𝑥 and 𝑛, where gcd(𝑥, 𝑛) = 1. The sequence
(𝑥 ∗ 𝑖 mod 𝑛 | 𝑖 = 1, 2, ⋯ , 𝑛 − 1)
is a permutation of (1, 2, ⋯ , 𝑛 − 1).

Question 11

Theorem 4 (Fermat’s Little Theorem)

Answer 11

Let 𝑝 be a prime integer, and let 𝑥 be a
positive integer with gcd(𝑥, 𝑝) = 1. (Since 𝑝 is prime, this condition means 𝑥 ≠ 𝑟𝑝 for
any integer 𝑟.) Then,
𝑥^(𝑝−1) mod 𝑝 = 1

Question 12

Lemma 8

Answer 12

1. Every integer 𝑖 ∈ 𝑍𝑛∗ has an inverse mod 𝑛, and the inverse is in 𝑍𝑛∗ (This is called closure under inversion.)
2. For every pair of integers 𝑖 and 𝑗 in 𝑍𝑛∗ , their product (𝑖 ∗ 𝑗 mod 𝑛) is also in 𝑍𝑛∗ . (This property is called closure under multiplication.)

Question 13

Lemma 9:

Answer 13

Let 𝑍𝑛∗ = {𝑢1, 𝑢2, ⋯ , 𝑢𝜙(𝑛)}. Let 𝑥 be any integer in 𝑍𝑛∗ . The sequence
(𝑥 ∗ 𝑢𝑖 mod 𝑛 | 𝑖 = 1, 2, ⋯ , 𝜙(𝑛))
is a permutation of (𝑢1, 𝑢2, ⋯ , 𝑢𝜙(𝑛)).

Question 14

Theorem 5 (Euler’s Theorem)

Answer 14

Let 𝑛 be a positive integer, and 𝑍𝑛∗ = {𝑢1, 𝑢2, ⋯ , 𝑢𝜙(𝑛)}
be the set of elements in 𝑍𝑛 which are prime relative to 𝑛. And let 𝑥 be an integer in 𝑍𝑛∗ .Then,
𝑥^(𝜙(𝑛)) mod 𝑛 = 1

Question 15

Computing Inverse by Exponentiation

Answer 15

Euler’s Theorem gives another way of
computing the inverse of an integer 𝑥 mod 𝑛, where 𝑥 ∈ 𝑍𝑛∗ ,. Namely,
𝑥^−1 = 𝑥^(𝜙(𝑛)−1) mod 𝑛

Question 16

Corollary 1

Answer 16

Let 𝑛 be a positive integer, and 𝑍𝑛∗ = {𝑢1, 𝑢2, ⋯ , 𝑢𝜙(𝑛)} be the set of
elements prime relative to 𝑛. And let 𝑥 be an integer in 𝑍𝑛∗ . Then, for any integer 𝑟,
𝑥^(𝑟𝜙(𝑛)+1) mod 𝑛 = 𝑥

Question 17

Theorem 6 (Generalized Euler’s Theorem)

Answer 17

Let 𝑛 = 𝑝𝑞 be product of two primes 𝑝 and 𝑞, and 𝜙(𝑛) = (𝑝 − 1)(𝑞 − 1).
Let 𝑥 be any positive integer, 𝑥 < 𝑛. Then, for any integer 𝑟,
𝑥^(𝑟𝜙(𝑛)+1) mod 𝑛 = 𝑥

Question 18

RSA Public Key

Answer 18

Public key composed of (s, n) s being a small number relatively prime to 𝜙(𝑛)

y = x^s mod n

Question 19

RSA Private Key

Answer 19

Private key composed of (t), t being s^-1 mod 𝜙(𝑛).

z = y^t mod n