Section A

1.   (a) Find all solutions to the congruence x3 + x + 5 = 0  mod 35. Solution (9 marks- seen similar).

35 = 5 * 7. We will find all solutions mod 5 and 7 and then put them together using the Chinese Remainder Theorem, since 5 and 7 are coprime.

x = 0, 2, 3  mod 5 and x = 1, 3  mod 7.  (4 marks)

Thus, we have 6 solutions:

(5 marks)

(b) Let p e N, p = 1 mod p.

x = 3, 8, 10, 15, 17, 22   mod 35.

mod 40.  Explain why 2 and 5 cannot be primitive roots

Solution (8 marks- seen similar).

In particular, p = 1  mod 8. Hence 2 is a quadratic residue mod p. By Euler’s

Criterion, 2  2       = 1  mod p, hence 2 cannot be a primitive root mod p since it’s order is ≤ (p - 1)/2 mod p.  (5 marks)

Similarly, since p = 1  mod 5, 5 is a quadratic residue mod p so it cannot be a primitive root mod p.  (3 marks)

(c) Let ζ22  = e2πi/22. Compute the product

(2 - ζ2(a)2 ).

1 ≤a<22, hcf(a,22)=1

Solution (8 marks- seen similar).

First find the cyclotomic polynomial

x22 - 1                                x22 - 1                         x11 + 1

Φ 1 (x)Φ2 (x)Φ1 1(x)      (x - 1)(x + 1)(x11 - 1)/(x - 1)       x + 1  .

5 marks)

The product above is Φ22 (2) =  = 683. (3 marks)

2.   (a)   (i)  Compute the Legendre Symbol sented in the lecture notes that

╱ 、. State clearly all the properties pre-

you are using.

Solution (8 marks- seen similar; students should get at most half the marks if they do not explain their steps clearly).

( ) = ( )( ) (since the Legendre Symbol is multiplicative)

= 1 * ( ) (since 97 = 1  mod 4 and 97 = 1  mod 8 ), respectively ) = 1 * 1 * ( ) (by Quadratic Reciprocity, since 97 = 1  mod 4 )       = ( )

= ( )( ) (since the Legendre Symbol is multiplicative)

= (-1) * ( ) (since 13 = -3  mod 8 )

= (-1) * 1 * ( ) ( by Quadratic Reciprocity, since 13 = 1  mod 4) = (-1) * ( )

= (-1) * 1

= -1.

(ii)  Show that if x, y  e Z satisfy the congruence 26x2   = y2    mod 97, then

26x2  = y2    mod 972 .

Solution (7 marks- not seen).

Since  ╱ 、  = -1, 97|x (otherwise, 26 = (x_1y)2    mod 97, which is not

possible since 26 is not a QR mod 97).  But then 97|y2  and, since 97 is prime, we get that 97|y. Thus, 972 |26x2 - y2  ÷ 26x2  = y2    mod 972 .

(b) For which odd primes p e N does the congruence x2  = 15  mod p have solu- tions? Your answer should be given in terms of congruences mod 60.              Solution (10 marks- seen similar).

╱ 、= ╱ 、╱ 、= ╱ 、╱ 、.

From the lecture notes, we know that ╱  、 = 1 if p = 士1  mod 12 and ╱  、 = 1

if p = 士5  mod 12.  (2 marks)

By direct computation,  ╱  、  = 1 if p = 士1  mod 5 and  ╱  、  = -1 if p = 士3

mod 5.  (4 marks)

Putting the above together using the Chinese Remainder Theorem, we get that 15 is a QR mod p if any only if p = 士1, 士7, 士11, 士17  mod 60.  (4 marks)

3.   (a) Let f (x) = x7 + 200x4 + x3 + 9x + 32. Remark that f (1) = 0  mod 3. Find a solution to the congruence

f (x) = 0   mod 36 .

Solution (9 marks- seen similar).

f( (x) = 7x6 + 800x3 + 3x2 + 9.

f( (1) = 819 so vp (f( (1)) = 2.  (3 marks)

f (1) = 243 = 0  mod 34 , so we can use Hensel’s Lifting Method with c = 2, which means that a1  will be a solution to the congruence mod 36 , where

a1  = a0 -  = 1 -     mod 36 .

(3 marks)

It is enough to find 91_1 mod 33 . So

(3 marks)

mod 33 . Using Euclid’s Algorithm, we find 91_1  = -8 a1  = 217   mod 36 .

(b)   (i) Using the fact that log(1 + 3x) converges 3-adically for all x e Z(3) , solve the congruence

28x  = 55   mod 37 .

Solution (9 marks- seen similar). log(1+33 x) = 33 x - x2  = 33 (x -54*x2 ) mod 37 .

Thus log(28)  = 33  * (-53)  mod 37   and log(55)  = 33  * 29  mod 37 .   (4 marks)

Taking log’s on both sides of the congruence, we obtain

log(28)x = log(55)   mod 37 ,

which, from the calculations above is equivalent to

x = (-53)_1 * 29 = 55 * 29 = 56   mod 34 .

(5 marks)

(ii)  Solve the congruence

x28  = 55   mod 37 .

Solution (7 marks- seen similar).  The fastest way is to use the binomial series:

551/28  = (1+2*32 )1/28  = 1+ +  *(32 *2)2  = 1+  = 784   mod 37

(3 marks)

Since mod 3 the solutions to the congruence are 士1 and one easily checks using Hensel’s Lemma that they lift uniquely to solutions mod 37 , the only solutions to the given congruence are x = 士784.  (4 marks)                       Alternatively:

Clearly, x must be invertible mod 3, so we can decompose it uniquely as x = T (a) exp(b)  mod 37 , where T (a) denotes the Teichmuller lift of a mod 37 . Thus, x28  = T (a28 ) exp(28b).  (1 mark)

In the previous part, we found that log(55) = 33  * 29  mod 37  and since 55 = 1  mod 3, we have 55 = T (1) exp(33 * 29)  mod 37 .  (1 marks)          By the uniqueness of the decompositions above, we must have a28   = 1 mod 3 and 28b = 33  * 29  mod 37 .   (1 marks) The first congruence has solutions a = 士1  mod 3.  (1 mark)

The second congruence has solutions if and only b = 33  * b( , for b(   e Z coprime to 3 satisfying 28 * b(  = 29  mod 34  兮 b(  = 28_1 * 29  mod 34  兮 b(  = 56  mod 34  (note that the last computation was already done in the previous part.)  (2 marks)

Thus, x = 士 exp(56*33 )  mod 37  = 士(1+33 *56+36 * )  mod 37  = 士784 mod 37 .  (1 mark)

4.   (a)   (i)  Determine the value of the continued fraction [5; 5, 10].

Solution (7 marks- seen similar). Let α = [5; 5, 10]. Then, α -5 =  (4 marks) ÷ α -5 =  ÷ α2  = 27 ÷ α = ,27, since α > 0 (3 marks).

(ii) Find two solutions (x, y) in positive integers to Pell’s equation x2 - 27y2  = 1.

Solution (9 marks- seen similar). The first two convergents of the contin- ued fraction of ,27 are  ,   and the second one gives us a solution to

Pell’s equation: (x, y) = (26, 5).  (4 marks)                              

This means that N (26 + 5,27) = N (26 + 15,3) = 1 in Z[,3].  (2 marks) So N ((26 + 5,27)2 ) = N (1351 + 260,27) = 1, which gives us another solution in positive integers to Pell’s equation: (1351, 260).  (3 marks)

(b) Find a solution x, y e Z to the diophantine equation

x2 + yx + y2  = 403.

Solution (9 marks- seen similar).  403 = 13 * 31 and both 13 and 31 are split in R = Z[] (which is a Unique Factorization Domain).  (4 marks)           To find a solution to the given equation, we need to find α, β e R such that N (α) =  13 and N (β) = 31.  Take for example α =    (2 marks) and β =   (2 marks). A solution is (x, y) = (-14, 23).  (1 marks)

Section B

1.   (a) Let P (x) e Z[x] be a monic polynomial of degree at least 1.

(i) Let M e Z such that P (M) = A  0. Show that Q(x) = A_1 P (M +Ax) e Z[x].

Solution (14 marks- not seen). Let P (x) = xd + cd_1 xd_1 + . . . + c1 x + c0 . Using the Binomial theorem,

P (M+Ax) = (M+Ax) +cdd_1 (M+Ax)d_1 +. . .+c1 (M+Ax)+c0  = P (M)   mod A.

Since P (M) = A, we get P (M + Ax) = 0  mod A.

Hence Q(x) = A_1 P (M + Ax) has integer coefficients.

(ii) Use the remark in the previous part to show that there are infinitely many primes dividing the integers

P (1), P (2), . . . , P (n), . . . .

Solution (28 marks- not seen).

Suppose there are only finitely many primes dividing the above list of integers.   Let’s call them p1 , p2 , . . . pr .   In particular,  P (n)    0 for all n e N.

Consider now

T (x) := Q(p1 ...pr x) = A_1 P (M + Ap1 ...pr x),

where P (M) = A  0. From the previous part, we know that T (x) e Z[x]. Furthermore, T (n) = 1  mod p1p2 ...pr , for all n e Z.

Now, since P (x) has degree at least 1, T (x) has degree at least one. Hence, there must exist an N  e N for which T (N)  士1 and thus T (N) has a prime divisor p which is not one of the pi ’s, i  =  1, 2, . . . r, from our observation above. So, p|P (M + Ap1p2 . . . pr N), which is a contradiction.

Thus, there must be infinitely many primes dividing

P (1), P (2), . . . , P (n), . . . .

(b) Let a e Z, d e N.

(i)  Consider the dth  cyclotomic polynomial, Φd (x).  Show that if p is an odd

prime dividing Φd (a) then either p|d or p = 1  mod d.

Solution (12 marks- seen similar).

Suppose p  /|d.  Since Φd (x)|(xd  - 1), Φd (a) = 0  mod p ÷ ad  - 1 = 0 mod p, so a is coprime to p and the order of a mod p is a divisor of d. Now suppose that the order of a mod p is a divisor, d( , of d, with d(  < d. Then ad′  - 1 =    e2d′  Φe (a) = 0  mod p. So there exists e|d(  such that Φe (a) = 0 mod p, and e < d since e|d(  and d(  < d by assumption. It follows that a is a root of xd - 1 =    f 2d Φf (x) mod p with multiplicity at least 2, i.e. that xd - 1 = (x - a)2 * f(x)  mod p for some polynomial f(x) e Z[x]. But this is impossible, since after taking derivatives, we would get that a must also

be a root of dxd  mod p , but dad  /= 0  mod p, since p /|d and p /|a. 

(ii) Use part (a) to show that there are infinitely many primes congruent to 1 mod d in Z.

Solution (6 marks- not seen).

Since Φd (x) e Z[x] and Φd (x) is monic, we can use the first part of the question to deduce that there are infinitely many primes dividing

Φd (1), Φd (2), . . . Φd (n), . . . .

From the previous part, we know that any prime diving Φd (n) must either divide d or be congruent to 1  mod d.  Since there are only finitely many primes dividing d, there must be infinitely many primes congruent to 1 mod d.

2.   (a) Let

αn  = 2 +  +  + .... +  .

Show that the 2-adic valuation of αn , v2 (αn ), satisfies the inequality

v2 (αn ) ≥ t1 (t - v2 (t)).

Solution(14 marks- not seen). Note that α := log(1 - 2) = -      converges 2-adically.

Furthermore, 2α = 2 log2 (1 - 2) = 2 log(-1) = log(1) = 0, hence α = 0. Thus v2 (αn ) = v2 (    n+1 ) ≥ mint≥n+1(t - v2 (t)).

(b)  Show that the value of the convergent series

1 

23k

k=1

is an irrational number.

Solution (26 marks- not seen).

Let Sn  =     k(n)=1 .  Clearly Sn  can be written in reduced form with denomi- nator 23n. We will show that the value of the series, α, satisfies the inequality |α - Sn |  <  2*22(1)￥3n     for all n  e N.   From lectures, we know that α must be irrational.