Section A (standard calculations)

Questions in this section are standard calculations.

You must show your working clearly to be awarded marks.

Answer all questions.

1. Find integers h and k such that 39h + 43k = 1.

Solution:

43 = 39 + 4

39 = 10 x 4 _ 1

1 = 10 x 4 _ 39

= 10(43 _ 39) _ 39

= 10 x 43 _ 11 x 39.

2. Calculate 39一1  modulo 43.

Solution:   By the previous question _11 x 39 = 1 mod 43. Therefore

39一1  = _11 = 32 mod 43.

3. Solve the congruence 117x = 9 mod 129.

Solution:   Dividing by 3, we get 39x = 3 mod 43. Then by the previous question we have x = 39一1  x 3 = _33 = 10 mod 43.

4. Solve the simultaneous congruences

x = 5 mod 39,        x = 6 mod 43.

Solution:   By the proof of the Chinese remainder theorem we have x = hnb + kma mod nm, where h = _11, n = 39, b = 6, k = 10, m = 43, a = 5. Therefore

x = 430 x 5 _ 429 x 6   mod 39 x 43.

Using a calculator, we get

x = 2150 _ 2574 = _424 = 1313   mod 1737.

5. Calculate ϕ(54), where ϕ is the Euler totient function.

Solution:   54 = 2 x 33 . Therefore ϕ(54) = (2 _ 1)(3 _ 1)32  = 18.

6. Calculate 3736724  modulo 54, writing your answer as an integer between 0 and 53.

Solution:   36734 = 4 mod 18. Therefore by Euler’s theorem 3736724  = 374  mod 54, and using a calculator we get 374  = 37.

7. Calculate 54100!  mod 2020, writing your answer as an integer between 0 and 2019.                  Solution:   2020 = 22  x 5 x 101. We clearly have 54100!  = 0 mod 22 . Note that ϕ(505) = 400. By Euler’s theorem, 54400  = 1 mod 505. Therefore 54100!  = 1 mod 505. We can now recover   the answer modulo 2020 using the Chinese reminder theorem.

505 = 126 x 4 + 1

1 = 505 _ 126 x 4

54100!  = 505 x 0 _ 126 x 4 x 1 = _504 = 1516   mod 2020.

8. Calculate the cyclotomic polynomial Φ 15 (X). Solution:   We have

X 15 _ 1 = Φ 1 Φ3 Φ5 Φ 15  = (X5 _ 1)(X2 + X + 1)Φ 15 .

Dividing by X5 + 1 we get

X 10 + X5 + 1 = (X2 + X + 1)Φ 15 .

Dividing X 10 + X5 + 1 by X2 + X + 1 we get

Therefore

Φ 15 (X) = X8 _ X7 + X5 _ X4 + X3 _ X + 1.

9. Which of the following are primitive roots modulo 101?

100,        3,        19.

Justify your answers.

Solution: Since 100 = _1, it has order 2, so it is not a primitive root. For an element x to be a primitive root, we need (x/101) = _1 and x10  /= 士1. We have

(3/101) = (101/3) = _1,

310  = 95  = 812  x 9 = (_20)2  x 9 = 400 x 9 = _36.               (19/101) = (101/19) = (6/19) = (2/19)(3/19) = (_1)(_1)(19/3) = 1.

Only 3 is a primitive root.

10. Calculate the quadratic residue symbol ╱ 、.

Solution:

(85/103) = (5/103)(17/103)

= (103/5)(103/17)

= (3/5)(1/17)

= (5/3) = (2/3) = _1.

11. Which of the following congruences have solutions? Justify your answers.

x2  = 17 x2  = 17 x2  = 17 x2  = 17

mod 19,

mod 191000 ,

mod 381000 ,

mod 3801000 .

Solution: yes, yes, yes, no.

12. Using Hensel’s Lemma, find a solution to the following congruence: x3 + 10x + 6 = 0   mod 54 .

Write your answer as an integer between 0 and 624.

Solution:   (There is a unique solution x = 359 mod 625.)

Let f (x) = x3 + 10x + 6. We start off by finding a root of f modulo 5:

x3  = _1 mod 5.

This has the solution x0  = _1. We then check the conditions of Hensel’s Lemma. f′ (x) = 3x2 + 10,        f′ (_1) = 13.

This is not a multiple of 5, so Hensel’s Lemma can be used, and the solution will be x2 , where

we define

f (xn )

xn+1  = xn _

We have

x1  = _1 _  = _1 +  = _1 + 5 x 2 mod 25 = 9    mod 25.

f (9) = 93 + 10 x 9 + 6 = 825,

f′ (9) = 3 . 92 + 10 = 253.

x2  = 9 _     mod 625.

We only need to find 253一1  modulo 25, and this is 17, or equivalently _8. Therefore x2  = 9 + 200 x 8 = 9 + 25 x 64 = 9 + 25 x 14 = 359   mod 625.

13. Which of the following series converge 7-adically? Justify your answer carefully.

&      7n2                             &    7n2                         &    7n2  

6n2 + 1 ,              (n!)3 ,              (n!)! .

For those which converge, calculate the sum modulo 74 .

Solution:   The first and second series converge. The third does not. Modulo 74 , the first series is 2 and the second is 8.

❼ v7 (7n2 /n2 ) = n2 _ v7 (6n2 + 1). Since v7 (6n2 + 1) < log(6n2 + 1)/ log(7) the valuation of the n-th term is at least n2 _ log(6n2 + 1)/ log(7), which converges to infinity.

❼ The n-th term has valuation at least n2 _ n/2, which converges to infinity.

❼ The n-th term has valuation less that n2 _ (n!)/7, which does not converge to infinity.

14. Write  as a finite continued fraction.

Solution:

48 = 1 x 31 + 17

31 = 1 x 17 + 14

17 = 1 x 14 + 3

14 = 4 x 3 + 2

3 = 1 x 2 + 1

2 = 2 x 1 + 0.

Therefore  = [1, 1, 1, 4, 1, 2].

15. Write ′ 15 as an infinite continued fraction.

Solution:

x0  = ′15                                                                                       a0  = | ′15│ = 3,

x1  =                =                                                                     a1  = |             │ = 1,

x2  =  _ 1 = ′ 15 _ 3 =         6         = ′15 + 3           a2  = | ′15 + 3│ = 6,

x3  =  = x1                                                                                                                a3  = a1  etc.

Therefore

′15 = [3, 1, 6, 1, 6, 1, 6, . . .] = [3, 1, 6].

16. Assuming that ′70 = [8, 2, 1, 2, 1, 2, 16], find the fundamental solution to Pell’s equation x2 _ 70y2  = 1.

Solution:

[8, 2, 1, 2, 1, 2] = [8, 2, 1, 2, 1 + 1/2]

= [8, 2, 1, 2, 3/2]

= [8, 2, 1, 2 + 2/3]

= [8, 2, 1, 8/3]

= [8, 2, 1 + 3/8]

= [8, 2, 11/8]

= [8, 2 + 8/11]

= [8, 30/11]

= 8 + 11/30

= 251/30.

Therefore the fundamental solution is x = 251, y = 11, i.e. 2512  _ 70 x 302  = 1.

17. Find a solution in integers to the equation x2 _ 70y2  = 11 with y > 200. Solution:   Another element with norm 1 is:

(251 + 30 ′70)2  = 2512 + 900 x 70 + 2 . 251 . 30 ′70 = 126001 + 15060 ′70. This gives the solution (x, y) = (126001, 15060) to Pell’s equation.

1    Section B

Questions in this section are more difficult.

It is not anticipated that many student will be able to answer all the questions. Answer as many as you can.

You may use any theorem from the course without proof.

If you wish to use a theorem not included in the course, then you should include a full proof of the theorem.

1.   (a) Prove that for every integer x e ←, the number x102 _ x2  is a multiple of 2020.                Solution:   2020 = 2 x 5 x 101 so it’s sufficient to prove the congruence modulo 2,5 and 101.

❼ modulo 2 we have xn  = x for all nge1, so both sides are x.

❼ modulo 5. If x = 0 mod 5 then both sides are 0. If not then by Fermat’s little theorem x4  = 1. Hence x100  = 125  = 1.

❼ Modulo 101. This is similar to 5, except that we instead have x100  = 1 by Fermat.

(b) Find the largest integer n such that x102 _ x2  is a multiple of n for all integers x. Justify your answer carefully.

Solution:   If p is a prime factor of n then by choosing x to be a primitive root modulo p we see that p _ 1 is a factor of 100. This gives the following possible values of p:

2, 3, 5, 11, 101.

If pn  is a factor of n for p odd, then the element x = exp(p) has order pn一1  modulo pn , so pn一1  must also be a factor of 100. For odd primes p, this gives the largest powers of p     diving n:

3, 52 , 11, 101.

Taking x = 2, we can see that the congruence is true modulo 4 but not modulo 8. Therefore

n = 4 x 3 x 25 x 11 x 101 = 333300.

2.   (a) Let x be an integer and let d be a factor of 2x2 _ 1. Prove that d2  = 1 mod 16.

Solution:   It’s sufficient to prove for prime factors. If p is a prime factor of 2x2 _ 1 then 2x2  = 1 mod p. Hence x and 2 are invertible modulo p, and we have x一2  = 2 mod p.       Therefore 2 is a quadratic residue modulo p. By the second Nebensatz, p = 士1 mod 8.   Therefore p2  = 1 mod 16.

(b) Hence prove that there are infinitely many prime numbers p such that p2  = 1 mod 16. Solution:   Suppose there are only finitely many such primes and call them p1 , . . . , pr .

Let N = 2x2 _ 1 with x = p1 . . . pr . Note that x > 7, so N > 1. Therefore N has at least