[Week 8] Module 7 Applied Class

Preparation

Glossary: Basic terms you should recognise before class

Read through this list of basic terminology before class, and check through the Lesson content up to and
including Module 7 for the definitions of any terms you're unsure about.

Revision from previous modules

Integer, natural number (Module 1)

Equivalence relations and equivalence classes (Module 2)
Logical connectives ( ∧, ∨, ¬, ⇒, ⇔) (Module 4)
Predicates (Module 5)

Integers and divisibility

Divides ( ∣ )
Divisor
Multiple
Divisible
Greatest common divisor (gcd)
Coprime
Integer linear combination
Euclidean Algorithm
Extended Euclidean Algorithm

Modular arithmetic

Remainder
Modulo
Congruence
Congruent modulo n
Modular equivalence ( ≡ )
Multiplicative inverse
Inverse modulo (n)
Zn

Euler totient function ( φ(n) )

Number theory applications

Fast exponentiation
Fermat’s Little Theorem
Primitive root modulo n
Diffie–Hellman key exchange
Public key
Private key
Applied Class 7 Activities

Your Applied Class in Week 8 will focus on these problems. Discuss and work through them together
in class, as guided by your tutors.
Full sample solutions to all problems will be released here after all Applied Classes in Week 8 are finished.
You can find some additional exercises on Number Theory at the end of Chapter 7 of the Course Notes.
Solutions to these will also be released here at the end of Week 8.

Warm-up
Problem 1

Recall that we write d ∣ n if n is divisible by d, i.e. if there exists some integer k such that n = dk .

(a) Write down whether the following statements are True or False:

3 ∣ 18

5 ∣ 42

7 ∣ 56

10 ∣ 103

12 ∣ 0

(b) For each, give the value of k when the statement is true.

Problem 2

Recall that for integers a, b, n with n > 0 , we write

a ≡ b (mod n)

to mean that a and b leave the same remainder when divided by n. We say that a and b are
congruent modulo n.

(a) Compute the following remainders:

23 ÷ 5

41 ÷ 6

1001 ÷ 9

(b) For each case, rewrite the result as a congruence.

Main questions
Problem 3

The rule for determining if a year is a leap year is as follows.

A positive integer is a leap year if and only if it is a multiple of 4, unless it is also a

multiple of 100, in which case it is not a leap year unless it is a multiple of 400.

Define the unary predicate Leap with domain N to be True if and only if its argument is a leap year.

Using Leap and the divisibility predicate ∣, write the above rule for leap years in predicate logic.

To translate into predicate logic, identify each clause in the English rule ("multiple of 4", "multiple of 100",
"multiple of 400") and express it using divisibility. Use logical connectors (∧,∨,¬) carefully.

Problem 4

Prove each of the following statements.

(a) 4 ∣ n if and only if the last two digits of the decimal representation of n give a multiple of 4.

Hint: Try writing n in the form 100q + r . Then reason about divisibility of n in terms of r .

(b) 8 ∣ n if and only if the last three digits of the decimal representation of n give a multiple of 8.

(c) 25 ∣ n if and only if the last two digits of the decimal representation of n give a multiple of 25.

(d) Extend (a) and (b) to higher powers of 2.

Challenge: These divisibility tests, and those at the end of Course Notes Section 7.1, all have the property
that the presence of divisor d can be determined just from some constant number of digits at the end of the
number. In other words, the number of digits of n that you need to look at is independent of n. For example,
to test divisibility by 4, you only look at the last two digits, regardless of how large n is.

Can you characterise when this happens? For which d is it the case that, to test divisibility of n by d, you only
need to look at some constant number of digits at the very end of n?

Problem 5

The digital sum of a positive integer n, written in standard decimal notation, is the sum of its digits.
Let's denote it by ds(n).

For example,
 ds(1984) = 1 + 9 + 8 + 4 = 22.

(a) Prove that, for all n ,

∈ N

n mod 3 = ds(n) mod 3.

This can be used repeatedly to compute n mod 3 : just keep computing the digital sum of the digital
sum of the digital sum ... until you get just a single digit, and then you can determine the remainder
manually.

(b) A similar method works for remainders modulo 9. Explain why, briefly.

(c) The alternating digital sum of n is obtained by alternately adding and subtracting its digits,
starting with addition at the right-hand end and moving to the left. We'll denote it by ads(n).

For example,

ads(1984) = −1 + 9 − 8 + 4 = 4.

Prove that, for all n ∈ N ,

n mod 11 = ads(n) mod 11.

(d) Devise a technique of similar type for working out n mod 3 from the bits of the binary
representation of n.

Problem 6

For each of the following equations, apply the method from Problem 5(b) to work out, by hand, the
remainder mod 9 of each side. In each case, comment on what comparing these two remainders tells
you.

(a) 92 × 31 = 2847

(b) 92 × 31 = 2852

(c) 92 × 31 = 2861

(d) 2718281828 × 3141592653 = 8539734219628209634

Problem 7

Use the Extended Euclidean Algorithm to show that 86 and 99 are coprime, and to express 1 as in
integer linear combination of them, and to find the inverse of 86 in Z9 9 .
Problem 8

(a) Find φ(n) for all n up to 20.

(b) Find primitive roots for a selection of values of n.

Problem 9

Compute
31415926535897932384626433832795028841971693993751058209749445923078164
1752 mod 125

by hand, showing your working.

The base here is the year in which the Gregorian calendar was introduced in Britain. The exponent is ⌊107 0 π⌋.
But you do not need this information to do the computation.

Problem 10

Alice and Bob are using the Diffie-Hellman scheme to agree on a key. Their public global parameters
are prime p = 11 and primitive root a = 7. Their public numbers are

yA = 2, yB = 8.

Play the role of the cryptanalyst: find their private numbers and the shared key they each compute.
Applied Class 7 Sample Solutions

Warm-up
Problem 1

Recall that we write d ∣ n if n is divisible by d, i.e. if there exists some integer k such that n = dk .

(a) Write down whether the following statements are True or False:

3 ∣ 18

5 ∣ 42

7 ∣ 56

10 ∣ 103

12 ∣ 0

(b) For each, give the value of k when the statement is true.

Solution:
3 ∣ 18 — True, k = 6

5 ∣ 42 — False

7 ∣ 56 — True, k = 8

10 ∣ 103 — False

12 ∣ 0 — True, k = 0

Problem 2

Recall that for integers a, b, n with n > 0 , we write

a ≡ b (mod n)

to mean that a and b leave the same remainder when divided by n. We say that a and b are
congruent modulo n.

(a) Compute the remainders of the following expressions:

23 ÷ 5

41 ÷ 6

1001 ÷ 9

(b) For each case, rewrite the result as a congruence.

Solution:
23 ÷ 5 leaves remainder 3 . 23 ≡ 3 (mod 5) .
41 ÷ 6 leaves remainder 5 . 41 ≡ 5 (mod 6).
 1001 ÷ 9 leaves remainder 2. 1001 ≡ 2 (mod 9) .

Main questions
Problem 3

The rule for determining if a year is a leap year is as follows.

A positive integer is a leap year if and only if it is a multiple of 4, unless it is also a

multiple of 100, in which case it is not a leap year unless it is a multiple of 400.

Define the unary predicate Leap with domain N to be True if and only if its argument is a leap year.

Using Leap and the divisibility predicate ∣, write the above rule for leap years in predicate logic.

Solution:
We want to write a predicate logic statement saying that x is a leap year if and only if it satisfies the rule
written in the question.

The rule needs some unpacking for us to be able to write it as a logic statement. The first part says that x must
be a multiple of 4 to be a leap year. The last part says that if x is also a multiple of 100 then it must be a
multiple of 400 to be a leap year. We can therefore write our predicate logic statement as:

Leap(x) ⟺ ( (4 ∣ x) ∧ [ ( 100 ∣ x ) ⟹ ( 400 ∣ x ) ] )

The first clause ensures that x is divisible by 4. The second clause (in square brackets) ensures that if x is also
divisible by 100 then it must be divisible by 400 to make the whole RHS of the statement true. If x is not
divisible by 100 then this last clause (in square brackets) will always evaluate to true, which is what we want.

An equivalent form of the statement:

Leap(x) ⟺ (400 ∣ x) ∨ ( ¬( 100 ∣ x ) ∧ ( 4 ∣ x ) )

Problem 4

Prove each of the following statements.

(a) 4 ∣ n if and only if the last two digits of the decimal representation of n give a multiple of 4.

(b) 8 ∣ n if and only if the last three digits of the decimal representation of n give a multiple of 8.

(c) 25 ∣ n if and only if the last two digits of the decimal representation of n give a multiple of 25.
(d) Extend (a) and (b) to higher powers of 2.

Challenge: These divisibility tests, and those at the end of Course Notes Section 7.1, all have the property
that the presence of divisor d can be determined just from some constant number of digits at the end of the
number. In other words, the number of digits of n that you need to look at is independent of n. For example,
to test divisibility by 4, you only look at the last two digits, regardless of how large n is.

Can you characterise when this happens? For which d is it the case that, to test divisibility of n by d, you only
need to look at some constant number of digits at the very end of n?

Solution:
In these solutions, let D be the number of digits in the decimal representation of n. We can therefore write n
as

D− 1 D− 2 1 0
nD ⋅ 10 + nD− 1 ⋅ 10 + ⋯ + n2 ⋅ 10 + n1 ⋅ 10

where nD , nD− 1 , ⋯ n1 are the digits of n (from most significant to least significant).
Also note that to show that n is divisible by some number d, we can show that n ≡ 0 (mod d) .

(a)

D− 1 1 0
n mod 4 = (nD ⋅ 10 + ⋯ + n2 ⋅ 10 + n1 ⋅ 10 ) mod 4 (1)

D− 1 2 1 0
= ((nD ⋅ 10 + ⋯ + n3 ⋅ 10 ) mod 4 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 4 ) mod 4 (2)

2 D− 3 0 1 0
= (10 ⋅ (nD ⋅ 10 + ⋯ n3 ⋅ 10 ) mod 4 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 4 ) mod 4 (3)

1 0
= 0 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 4 (4)

1 0
= (n2 ⋅ 10 + n1 ⋅ 10 ) mod 4 (5)

We have (4) because 4∣102 .

It follows that 4 ∣ n if and only if 4 ∣ 10n2 + n1 , i.e., 4 divides the number with digits n2 n1 .

(b)

n mod 8 (6)

D− 1 1 0
= nD ⋅ 10 + ⋯ + n2 ⋅ 10 + n1 ⋅ 10 mod 8 (7)

D− 1 3 2 1 0
= ((nD ⋅ 10 + ⋯ + n4 ⋅ 10 ) mod 8 + (n3 ⋅ 10 + n2 ⋅ 10 + n1 ⋅ 10 ) mod 8 ) mod(8)
8

3 D− 4 0 2 1 0
= (10 ⋅ (nD ⋅ 10 + ⋯ + n4 ⋅ 10 ) mod 8 + (n3 ⋅ 10 + n2 ⋅ 10 + n1 ⋅ 10 ) mod 8 )(9)
mo

2 1 0
= 0 + (n3 ⋅ 10 + n2 ⋅ 10 + n1 ⋅ 10 ) mod 8 (10)

2 1 0
= (n3 ⋅ 10 + n2 ⋅ 10 + n1 ⋅ 10 ) mod 8 (11)

We have (10) because 8∣103 .

It follows that 8 ∣ n if and only if 8 ∣ 100n3 + 10n2 + n1 , i.e., 4 divides the number with digits n3 n2 n1 .

(c)
 D− 1 1 0
n = nD ⋅ 10 + ⋯ + n2 ⋅ 10 + n1 ⋅ 10 mod 25 (12)

D− 1 2 1 0
= ((nD ⋅ 10 + ⋯ + n3 ⋅ 10 ) mod 25 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 25 ) mod 25 (13)

2 D− 3 0 1 0
= (10 ⋅ (nD ⋅ 10 + ⋯ n3 + ⋅10 ) mod 25 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 25 ) mod 25 (14)

1 0
= 0 + (n2 ⋅ 10 + n1 ⋅ 10 ) mod 25 (15)

1 0
= (n2 ⋅ 10 + n1 ⋅ 10 ) mod 25 (16)

We have (15) because 25∣102 .

It follows that 25 ∣ n if and only if 25 ∣ 10n2 + n1 , i.e., 25 divides the number with digits n2 n1 .

(d) We need to find the lowest power of 10 which is divisible by 2i . The prime decomposition of 10x is 2x ⋅ 5x ,
so in order for 10x to be divisible by 2i , we need x ≥ i. This tells us that for divisibility by 2i , we would need
the last i digits to be divisible by 2i , as the rest of the number is guaranteed to be. Let's prove this in a similar
way to parts (a)–(c).

We show n ≡ 0 (mod 2 )
i
when the last i digits are divisible by 2i .

i
n mod 2 (17)

D− 1 1 0 i
= nD ⋅ 10 + ⋯ + n2 ⋅ 10 + n1 ⋅ 10 mod 2 (18)

D− 1 i i i− 1 0 i i
= ((nD ⋅ 10 + ⋯ + ni+ 1 ⋅ 10 ) mod 2 + (ni ⋅ 10 + ⋯ + n1 ⋅ 10 ) mod 2 ) mod
(19)
2

i D− 1 − i 0 i i− 1 0 i
= (10 ⋅ (nD ⋅ 10 + ⋯ + ni+ 1 ⋅ 10 ) mod 2 + (ni ⋅ 10 + ⋯ + n1 ⋅ 10 ) mod (20)
2 ) m

i− 1 0 i
= 0 + (ni ⋅ 10 + ⋯ + n1 ⋅ 10 ) mod 2 (21)

i− 1 0 i
= (ni ⋅ 10 + ⋯ + n1 ⋅ 10 ) mod 2 (22)

The first part is 0 since all the terms have 2i as a factor (because they have 10i as a factor). It follows that 2i ∣

n if and only if 2 divides the number formed from the last i digits of n, i.e., the number with digits
i

ni … n2 n1 .

Challenge: We can use the same idea about the prime decomposition of 10. For divisibility by d to depend
only on a constant number, say k , of digits at the end of n, we would need the number formed by all the other
digits followed by k zeros to be divisible by d. So we need to find a number x such that d is a factor of 2i ⋅ 5i
for all i ≥ x. This can only happen when the prime decomposition of d contains only 2 and 5, i.e. d = 2a ⋅ 5b .
The number of digits we would need to check would be the higher of a, b since once we exclude those digits,
all more significant digits would have a power of 10 large enough to guarantee divisibility by d.

Problem 5

The digital sum of a positive integer n, written in standard decimal notation, is the sum of its digits.
Let's denote it by ds(n).

For example,

ds(1984) = 1 + 9 + 8 + 4 = 22.

(a) Prove that, for all n ∈ N ,

 n mod 3 = ds(n) mod 3.

This can be used repeatedly to compute n mod 3 : just keep computing the digital sum of the digital
sum of the digital sum ... until you get just a single digit, and then you can determine the remainder
manually.

(b) A similar method works for remainders modulo 9. Explain why, briefly.

(c) The alternating digital sum of n is obtained by alternately adding and subtracting its digits,
starting with addition at the right-hand end and moving to the left. We'll denote it by ads(n).

For example,

ads(1984) = −1 + 9 − 8 + 4 = 4.

Prove that, for all n ∈ N ,

n mod 11 = ads(n) mod 11.

(d) Devise a technique of similar type for working out n mod 3 from the bits of the binary
representation of n.

Solution:
Throughout, let the digits of n be nD nD− 1 … n3 n2 n1 , so

D D− 1 2
n = nD 10 + nD− 1 10 + ⋯ + n3 10 + n2 ⋅ 10 + n1 . (23)

(a) Observe that

10 mod 3 = 1.

It follows that, for any k ,

k k k
10 mod 3 = (10 mod 3) mod 3 = 1 mod 3 = 1.

Now take the remainder mod 3 of each side of (23):

D D− 1 2
n mod 3 = (nD 10 + nD− 1 10 + ⋯ + n3 10 + n2 ⋅ 10 + n1 ) mod 3
D D− 1
= ((nD 10 mod 3) + (nD− 1 10 mod 3) + ⋯
2
+ (n3 10 mod 3) + (n2 ⋅ 10 mod 3) + n1 ) mod 3

= (nD + nD− 1 + ⋯ + n3 + n2 + n1 ) mod 3

= ds(n) mod 3.

(b) Since

10 mod 9 = 1,

the same argument as we used in (a) would work again, with 3 replaced by 9 throughout.
 (c) We have

10 ≡ −1 (mod 11)

from which it follows that

k
−1 (mod 11), if k is odd;
10 ≡ {
1 (mod 11), if k is even.

Now take the remainder mod 11 of each side of (23):

D D− 1 2
n mod 11 = (nD 10 + nD− 1 10 + ⋯ + n3 10 + n2 ⋅ 10 + n1 ) mod 11
D D− 1
= ((nD 10 mod 11) + (nD− 1 10 mod 11) + ⋯
2
+ (n3 10 mod 11) + (n2 ⋅ 10 mod 11) + n1 ) mod 11
D+ 1 D
= (nD (−1) + nD− 1 (−1) + ⋯ + n3 − n2 + n1 ) mod 11

= ads(n) mod 11.

(d) The argument is very similar to (c), except that the base is now 2 instead of 10, and the modulus is 3 instead
of 11. But in each case, the modulus is one more than the base. In this case, we have

2 mod 3 = −1,

k
−1 (mod 3), if k is odd;
2 ≡ {
1 (mod 3), if k is even.

We can work through the same steps as we did in (c), with 10 and 11 replaced by 2 and 3, respectively,
throughout. The conclusion is that

n mod 3 = abs(n) mod 3,

where abs(n) is the alternating bit sum of n, which is formed by alternately adding and subtracting the bits
of the binary representation of n, starting with addition at the right-hand end and moving to the left.

Problem 6

For each of the following equations, apply the method from Problem 5(b) to work out, by hand, the
remainder mod 9 of each side. In each case, comment on what comparing these two remainders tells
you.

(a) 92 × 31 = 2847

(b) 92 × 31 = 2852

(c) 92 × 31 = 2861

(d) 2718281828 × 3141592653 = 8539734219628209634

Solution:
 From Problem 5(b), we found that n mod 9 = ds(n) mod 9 , where ds(n) is the sum of the digits of n.

Each equation here is of the form

n1 × n2 = n3 .

Modular arithmetic tells us that this equation, if true, must still hold mod 9. In other words,
we must have

(n1 mod 9) × (n2 mod 9) ≡ (n3 mod 9) (mod 9).

So, as a check, we can take remainders mod 9 of all three numbers, do the arithmetic with them, and see if the
two results are congruent mod 9. And Problem 5(b) gave us a simple way of working out these remainders, by
taking the digital sum (and then the digital sum of the digital sum, etc, if we need to).

We can also explain how this works using basic algebra, although it takes some more work. We can express
any two natural numbers as n1 = q1 d + r1 and n2 = q2 d + r2 , where where d is some divisor we might
care about (say, 9), and r1 and r2 are the remainders for n1 and n2 when divided by d, respectively.

If we then take the product of n1 and n2 , this can be expressed as (q1 d + r1 )(q2 d + r2 ) = q1 q2 d2 +
q1 dr2 + q2 dr1 + r1 r2 = d(q1 q2 d + q1 r2 + q2 r1 ) + r1 r2 . Since that first term is a multiple of d, then if

we take n3 mod d, we will have n1 × n2 ≡ r1 r2 (mod d). So we should be finding that ds(n3 ) mod 9 =
ds(n1 ) mod 9 × ds(n2 ) mod 9 . If not, then the equation is incorrect. But if this equality does hold, all we

know is n3 is congruent to the true result mod 9, so may or may not be correct.

(a) 9 + 2 mod 9.
= 11 = 2

3 + 1 = 4 = 4 mod 9 .

2 + 8 + 4 + 7 = 21 = 3 mod 9 . n1 × n2 
≡ n3 (mod 9). This equation must be false.

(b) 9 + 2 = 11 = 2 mod 9.
3 + 1 = 4 = 4 mod 9 .

2 + 8 + 5 + 2 = 17 = 8 mod 9 . n1 × n2 ≡ n3 (mod 9 ), so this equation could be correct, or n3 could be

off by a multiple of 9, we can't say just based on this information. (It is correct though, if you choose to verify
yourself.)

(c) 9 + 2 = 11 = 2 mod 9.
3 + 1 = 4 = 4 mod 9 .

2 + 8 + 6 + 1 = 17 = 8 mod 9 . n1 × n2 ≡ n3 (mod 9 ), so again this may be correct or off by a multiple of

9 . (It is incorrect if you choose to verify yourself.)

(d) ds(n1 ) = ds(2718281828) = 2 + 7 + 1 + 8 + 2 + 8 + 1 + 8 + 2 + 8 = 47 ≡ 2 mod 9

ds(n2 ) = ds(3141592653) = 3 + 1 + 4 + 1 + 5 + 9 + 2 + 6 + 5 + 3 = 39 ≡ 3 mod 9 .

(n1 mod 9) × (n1 mod 9) = 2 × 3 = 6 .

ds(n3 ) = ds(8539734219628209634) = 8 + 5 + 3 + 9 + 7 + 3 + 4 + 2 + 1 + 9 + 6 + 2 + 8 +

2 + 0 + 9 + 6 + 3 + 4 = 91 ≡ 1 (mod 9) .

So n1 × n2  ≡ n3 (mod 9 ). This equation must be false. Specifically it's off by 5 . What happens if you increase

the second-last digit by 5?

Problem 7
Use the Extended Euclidean Algorithm to show that 86 and 99 are coprime, and to express 1 as in
integer linear combination of them, and to find the inverse of 86 in Z9 9 .

Solution:
Input: m = ,
99 n = 86 . (Since we must have m ≥ n )
(a, x, y) := (99, 1, 0)

(b, z, w) := (86, 0, 1)

b =
 0 , continue.
99
q := ⌊ ⌋ = 1
86

(a, x, y) := (86, 0, 1)

(b, z, w) := (99, 1, 0) − 1(86, 0, 1) = (13, 1, −1)

b =
 0 , continue.
86
q := ⌊ ⌋ = 6
13

(a, x, y) := (13, 1, −1)

(b, z, w) := (86, 0, 1) − 6(13, 1, −1) = (8, −6, 7)

b =
 0 , continue.
13
q := ⌊ ⌋ = 1
8

(a, x, y) := (8, −6, 7)

(b, z, w) := (13, 1, −1) − 1(8, −6, 7) = (5, 7, −8)

b =
 0 , continue.
8
q := ⌊ ⌋ = 1
5

(a, x, y) := (5, 7, −8)

(b, z, w) := (8, −6, 7) − 1(5, 7, −8) = (3, −13, 15)

b =
 0 , continue.
5
q := ⌊ ⌋ = 1
3

(a, x, y) := (3, −13, 15)

(b, z, w) := (5, 7, −8) − 1(3, −13, 15) = (2, 20, −23)

b =
 0 , continue.
3
q := ⌊ ⌋ = 1
2

(a, x, y) := (2, 20, −23)

(b, z, w) := (3, −13, 15) − 1(2, 20, −23) = (1, −33, 38)

b =
 0 , continue.
2
q := ⌊ ⌋ = 2
1

(a, x, y) := (1, −33, 38)

(b, z, w) := (2, 20, −23) − 2(1, −33, 38) = (0, 53, −99)

b = 0 , output (1, −33, 38).

This shows us that the gcd(86, 99) is a = 1, which means 86 and 99 are coprime.
The other two terms of our output tuple show us how to express 1 as a linear combination of 86 and 99, as
1 = 99(−33) + 86(38). This also shows us that the inverse of 86 in Z9 9 is 38 . Why? Well, if we rearrange our

linear combination to be 99(33) + 1 = 86(38), we clearly see that 86(38) is equal to a multiple of 99, plus 1,
and thus 86(38) ≡ 1 (mod 99), and thus 38 is the inverse of 86 in Z9 9 .

Problem 8

(a) Find φ(n) for all n up to 20.

(b) Find primitive roots for a selection of values of n.

Solution:
(a) We will use the following facts:
(1): ϕ(p) = p − 1, if p is prime.
(2): ϕ(pm ) = pm− 1 (p − 1), is p is prime and m is a natural number.
(3): ϕ(ab) = ϕ(a)ϕ(b), if a and b are coprime natural numbers.

ϕ(1) = 0 (by (1))

ϕ(2) = 1 (by (1))

ϕ(3) = 2 (by (1))

2
ϕ(4) = ϕ(2 ) = 2 (by (2))

ϕ(5) = 4 (by (1))

ϕ(6) = ϕ(2)ϕ(3) = 2 (by (3))

ϕ(7) = 6 (by (1))

3
ϕ(8) = ϕ(2 ) = 4 (by (2))

2
ϕ(9) = ϕ(3 ) = 6 (by (2))

ϕ(10) = ϕ(2)ϕ(5) = 4 (by (3))

ϕ(11) = 10 (by (1))

2
ϕ(12) = ϕ(4)ϕ(3) = ϕ(2 )ϕ(3) = 4 (by (3) then (2) and (1))

ϕ(13) = 12 (by (1))

ϕ(14) = ϕ(7)ϕ(2) = 6 (by (3))

ϕ(15) = ϕ(5)ϕ(3) = 8 (by (3))

4
ϕ(16) = ϕ(2 ) = 8 (by (2))

ϕ(17) = 16 (by (1))

2
ϕ(18) = ϕ(9)ϕ(2) = ϕ(3 )ϕ(2) = 6 (by (3) then (2) and (1))

ϕ(19) = 18 (by (1))

2
ϕ(20) = ϕ(5)ϕ(4) = ϕ(5)ϕ(2 ) = 8 (by (3) then (2) and (1))

(b) Let's look at primitive roots of 5. There should be ϕ(ϕ(5)) = 2 of them. We want numbers which
generate Z∗5 when repeatedly multiplied together mod 5.
If we repeatedly multiply by 2 in Z5 , we get 2, 4, 3, 1, in that order. The power 2k don't hit 1 for k < ϕ(5), so 2
is a primitive root. Same for 3, we generate 3, 4, 2, 1. Again, we don't hit 1 for k < ϕ(5), so 3 is another
primitive root of 5. \\

Primitive roots of 9: There should be ϕ(ϕ(9)) = 2 of them.

2 ≡ 2 (mod 9), 2 ≡ 4 (mod 9), 2 ≡ 8 (mod 9), 2 ≡ , ,
1 2 3 4 5 6
7 (mod 9) 2 ≡ 5 (mod 9) 2 ≡ 1

(mod 9). 2 is a primitive root of 9.

5 ≡ 5 (mod 9), 5 ≡ 7 (mod 9), 5 ≡ 8 (mod 9), 5 ≡ , ,

1 2 3 4 5 6
4 (mod 9) 5 ≡ 2 (mod 9) 5 ≡ 1

(mod 9). 5 is a primitive root of 9.

Primitive roots of 18: There should be ϕ(ϕ(18)) = 2 of them. Z∗1 8 = {1, 5, 7, 11, 13, 17} since these are all
numbers less then 18 which are coprime with it, so we want numbers which generate all of these. So these are
the only numbers we have to check! Since they'll all first generate themselves mod 18 with a power of 1.
5 ≡ 5 (mod 18), 5 ≡ 7 (mod 18), 5 ≡ 17 (mod 18), 5 ≡ 13 (mod 18), 5 ≡ 11 (mod 18), 5 ≡
1 2 3 4 5 6

1 (mod 18). 5 is a primitive root of 18.

 With one root, we know all others take the form 5k mod 18, where k is coprime with ϕ(18) ≡ 6. The only
number coprime with 6 which is less than 6 is 5. 55 ≡ 11 (mod 18). The other primitive root must be 11,
let's verify.
11 ≡ 11 (mod 18), 11 ≡ 13 (mod 18), 11 ≡ 17 (mod 18), 11 ≡ 7 (mod 18), 11 ≡ 5 (mod 18),
1 2 3 4 5

11 ≡ 1 (mod 18). 11 is a primitive root of 18.

6

Problem 9

Compute

31415926535897932384626433832795028841971693993751058209749445923078164
1752 mod 125

by hand, showing your working.

Solution:
We first find 1752 mod 125 by dividing and finding the remainder. Since 125 × 14 = 1750, 1752 mod 125
is 2. Next we will use Euler's generalisation of Fermat's little theorem as described in the course notes:
mod n = 1 . So we first calculate ϕ(125) = ϕ(5 ) = 5 (5 − 1) = 100 . Thus 2 mod 125 = 1 . This
ϕ (n) 3 2 100
x

means that 2 to the power of any multiple of 100 will be 1 so in particular:

31415926535897932384626433832795028841971693993751058209749445923078100
2 ≡ 1 mod 125.

Therefore using the first index law:

31415926535897932384626433832795028841971693993751058209749445923078164 64
2 ≡ 1 ⋅ 2 mod 125
64
≡ 2 mod 125

The final step is to use the procedure for fast exponentiation to calculate 26 4 mod 125. As good computer
scientists/discrete mathematicians we already know that 28 = 256 ≡ 6 mod 125 so we will start our
procedure doubling the exponent from there:

8
2 ≡ 6 mod125
16 2
2 ≡ 6 ≡ 36 mod125
32 2
2 ≡ 36 ≡ 36 × 6 × 6 ≡

216 × 6 ≡ 1296 ≡ 1296 − 1250 ≡ 46 mod125

64 2
2 ≡ 46 ≡ 46 × 2 × 23

≡ 92 × 23 ≡ −33 × 23 ≡ −700 + 7 − 66 ≡ −759 ≡ −9 ≡ 125 − 9 ≡ 116 mod125

quantity to work out calculation result

8
2 256 − 250 = 6 6

16 2
2 6 = 36 36

32 2 4
2 36 = 6 = 1296

1296 ≡ 1296 − 1250 ≡ 46 mod 125 46

64 2
2 46 = 46 × 2 × 23 = 92 × 23

92 × 23 ≡ −33 × 23 ≡ −700 + 7 − 66 ≡ −759 mod 125

−759 ≡ −9 ≡ 125 − 9 ≡ 116 mod 125 116

Problem 10

Alice and Bob are using the Diffie-Hellman scheme to agree on a key. Their public global parameters
are prime p = 11 and primitive root a = 7. Their public numbers are

yA = 2, yB = 8.

Play the role of the cryptanalyst: find their private numbers and the shared key they each compute.

Solution:
Our job is to try and find xA and xB , respectively, Alice and Bob's private numbers, and also to find
mod 11 . We also know that
x x
a A B

xA xB
2 = yA = 7 mod 11 and 8 = yB = 7 mod 11.

Now we simply look at all the powers of 7 modulo 11 until we find the desired numbers. We have

1
7 mod 11 = 7

2
7 mod 11 = 5

3
7 mod 11 = 2

4
7 mod 11 = 3

5
7 mod 11 = 10

6
7 mod 11 = 4

7
7 mod 11 = 6

8
7 mod 11 = 9

9
7 mod 11 = 8

10
7 mod 11 = 1.

From the above calculations, we know that xA = 3 and xB = 9 . Therefore, we can also conclude that their
shared key is

xB xA 3
kAB = (a ) mod 11 = 8 mod 11 = 6.

This calculation used Bob's public number and Alice's private number, which is the key calculation done by
Alice. This is sufficient to answer the question. But let's also check the key calculation done by Bob using
Alice's public number and his own private number, so we can see that it gives the same result:

xA xB 9
kAB = (a ) mod 11 = 2 mod 11 = 6.

So the two key calculations do indeed give the same result.