Quiz · Medium
Twenty questions on gcd and the Euclidean algorithm, primes, congruences, modular inverses, Fermat, Euler, the Chinese remainder theorem and RSA.
What is ?
42
6
21
252
84 = 2^2 * 3 * 7 and 126 = 2 * 3^2 * 7, so gcd = 2 * 3 * 7 = 42. (252 is the lcm.)
Using the Euclidean algorithm, equals
7
33
147
21
1071 = 2*462 + 147; 462 = 3*147 + 21; 147 = 7*21. The last non-zero remainder is 21.
How many positive divisors does 72 have?
8
12
10
24
72 = 2^3 * 3^2, so (3 + 1)(2 + 1) = 12.
Which of these numbers is prime?
91
119
149
143
91 = 7*13, 119 = 7*17, 143 = 11*13. 149 has no prime factor up to 12 (not 2, 3, 5, 7, 11), so it is prime.
The remainder of divided by 7 is
1
4
2
6
2^3 = 8 = 1 (mod 7), so 2^100 = 2^(99+1) = (2^3)^33 * 2 = 2.
The inverse of 4 modulo 9 is
7
2
5
8
4 * 7 = 28 = 3 * 9 + 1, so the inverse is 7. 4 * 5 = 20 = 2 (mod 9) is not 1.
How many solutions modulo 12 does have?
0
4
1
2
gcd(8, 12) = 4 divides 4, so there are 4 solutions mod 12 (x = 2, 5, 8, 11).
The number is
12
36
44
24
45 = 3^2 * 5, so phi = 45 * (2/3) * (4/5) = 24.
Which statement is Fermat's little theorem (p prime, p does not divide a)?
Fermat gives a^(p-1) = 1. a^p = a (not 1) holds for all a, and Wilson's theorem says (p-1)! = -1.
The Chinese remainder theorem guarantees a unique solution mod when
m1 and m2 are both prime
m1 and m2 are coprime
m1 divides m2
m1 + m2 is even
Pairwise coprime moduli are what is required; they need not be prime (e.g. 4 and 9).
Which has no solution?
gcd(6, 9) = 3 does not divide 4, so 6x = 4 (mod 9) is unsolvable. The others have gcd 1 or gcd dividing the right side.
The smallest positive x with and is
17
7
9
21
Candidates congruent to 2 mod 5: 2, 7, 12, 17; the first that is 1 mod 4 is 17 (7 = 3 mod 4, 12 = 0 mod 4, 17 = 1 mod 4).
In RSA with p = 5, q = 11 and e = 3, the private exponent d is
7
13
27
17
phi = 4 * 10 = 40. We need 3d = 1 (mod 40): d = 27 since 81 = 2*40 + 1. (7 would give 21, not 1 mod 40.)
Why is the Sieve of Eratosthenes on the grid up to 120 only run with the primes 2, 3, 5, 7?

Larger primes have no multiples in the grid
Multiples of 11 are already prime
Only odd numbers need sieving
Every composite up to 120 has a prime factor at most 10
A composite n has a prime factor at most sqrt(n), and sqrt(120) is about 10.95. Multiples of 11 below 121 (22, 33, ...) already have a smaller prime factor. Image: Ricordisamoa, public domain, via Wikimedia Commons.
The 21 x 15 rectangle in the picture is tiled by squares as in the Euclidean algorithm. What is ?

3
5
6
15
The last (smallest) squares have side 3, so gcd(21, 15) = 3. Image: Kelam, CC BY-SA 3.0, via Wikimedia Commons.
True or false: for positive integers a and b.
True
False
Taking, for each prime, the min and max exponents multiplies to the sum of exponents, which is exactly ab.
What day of the week is it 1000 days after a Monday?
Tuesday
Sunday
Wednesday
Friday
1000 = 142 * 7 + 6, so the day moves forward 6 places: Monday + 6 days = Sunday. Only the remainder mod 7 matters.
The last two digits of are (use )
03
09
01
81
3^20 = 1 (mod 100), so 3^100 = (3^20)^5 = 1 (mod 100). Euler's theorem gives only 3^40 = 1, but 20 is the actual order.
Which statement about primes is correct?
There are finitely many twin primes
There are infinitely many primes
Every even integer greater than 2 is a sum of two primes (proved)
Every prime is odd
Euclid's theorem. The Goldbach and twin prime statements are conjectures, and 2 is an even prime.
For prime p = 13, what is by Wilson's theorem?
12
1
6
0
(p-1)! = -1 (mod p), and -1 = 12 (mod 13).