Description
Exercise 4.1
In this exercise we will determine the remainder r of the division of 10100 by 247, without using any calculator.
Please detail your calculations.
i) Write 247 as a product of two primes p1 < p2. Express their gcd as a linear combination, i.e. find x and
y ∈ Z such that 1 = p1 · x + p2 · y.
(1 Mark)
ii) Prove that 10100 ≡ 3 mod p1 and 10100 ≡ 9 mod p2.
(2 Marks)
iii) Using the Chinese Remainder Theorem, prove that r = 237.
(1 Mark)
Exercise 4.2
Find a number n ∈ N satisfying both 4n ≡ 7 (mod 9) and 2n = 3 (mod 11).
(2 Marks)
Exercise 4.3
Use Fermat’s factorization method to find factors of the number 2027651281. Detail all the steps in your
calculation.
(2 Marks)
Exercise 4.4
Use Fermat’s Little Theorem to compute 52003 mod 7, 52003 mod 11 and 52003 mod 13. Then use the Chinese
Remainder Theorem to compute 52003 mod 1001 (note that 1001 = 7 · 11 · 13).
(4 Marks)
Exercise 4.5
In the lectures we proved that if p is prime then (p − 1)! ≡ −1 (mod p).
i) Prove that the converse is also true, i.e., if (p − 1)! ≡ −1 (mod p), then p is prime.
(2 Marks)
ii) Prove that for any odd integer m, (m − 1)! ≡ (−1)z
(z!)2
(mod m), where z =
m−1
2
.
(2 Marks)
iii) Discuss a strategy to assess the primality of an odd integer.
(2 Marks)
Exercise 4.6
If m is a positive integer, the integer a is a quadratic residue of m if gcd(a, m) = 1 and the congruence
x
2 ≡ a mod m has a solution. In other words, a quadratic residue of m is an integer relatively prime to m that
is a perfect square modulo m. For example, 2 is a quadratic residue of 7 because gcd(2, 7) = 1 and 32 ≡ 2 mod 7
and 3 is a quadratic nonresidue of 7 because gcd(3, 7) = 1 and x
2 ≡ 3mod has no solution.
i) Which integers are quadratic residues of 11 ?
(2 Marks)
ii) Show that if p is an odd prime and a is an integer not divisible by p, then the congruence x
2 ≡ a mod p
has either no solutions or exactly two incongruent solutions modulo p.
(2 Marks)
iii) Show that if p is an odd prime, then there are exactly (p−1)/2 quadratic residues of p among the integers
1, 2, …, p − 1.
(2 Marks)
If p is an odd prime and a is an integer not divisible by p, the Legendre symbol (
a
b
)
is defined to be 1 if a is a
quadratic residue of p and −1 otherwise.
iv) Show that if p is an odd prime and a and b are integers with a ≡ b mod p, then
(
a
p
)
=
(
b
p
)
(1 Mark)
v) Prove that if p is an odd prime and a is a positive integer not divisible by p, then
(
a
p
)
≡ a
(p−1)/2 mod p.
(2 Marks)
vi) Show that if p is an odd prime and a and b are integers not divisible by p, then
(
ab
p
)
=
(
a
p
) ( b
p
)
.
(2 Marks)
vii) Show that if p is an odd prime, then -1 is a quadratic residue of p if p ≡ 1 mod 4, and -1 is not a quadratic
residue of p if p ≡ 3 mod 4.
(2 Marks)
viii) Find all solutions of the congruence x
2 = 29 mod 35.
Hint: Find the solutions of this congruence modulo 5 and modulo 7, and then use the Chinese Remainder
Theorem.
(2 Marks)
