mock Exam 2017, answers PDF

Preview

Summary

Download mock Exam 2017, answers PDF

Description

SOLUTIONS ECM3704 UNIVERSITY OF EXETER MATHEMATICS May 2017 Number Theory - SOLUTION SHEET Module Leader: Dr Julio Andrade Duration: 2 HOURS. The mark for this module is calculated from 80% of the percentage mark for this paper plus 20% of the percentage mark for associated coursework.

Answer Section A (50%) and any TWO of the three questions in Section B (25% for each). Marks shown in questions are merely a guideline. Candidates are permitted to use approved portable electronic calculators in this examination. This is a CLOSED NOTE examination.

SECTION A 1. (a) Find the general solution of the following system of simultaneous congruences:   x ≡ 1 (mod 3) x ≡ 2 (mod 5)   x ≡ 3 (mod 7).

SOLUTION: Since the moduli m1 = 3, m2 = 5, and m3 = 7 are pairwise relatively prime, by the Chinese Remainder Theorem (CRT), the linear system has a unique solution. To find it, first we find M1 , M2 , M3 , y1 , y2 , and y3 as in the proof of the CRT. Thus, by the CRT,

x≡

3 X

ai Mi yi

(mod M)

i=1

≡ 1 · 35 · 2 + 2 · 21 · 1 + 3 · 15 · 1 (mod 105) ≡ 52 (mod 105). Therefore, 52 is the unique solution of the linear system modulo 105. Thus, the general solution is x = 52 + 105t. [Standard problem - similar seen in lectures and example sheets] (8) (b) Find all solutions of the congruence f (x) = x2 + 4x + 2 ≡ 0 (mod 49). SOLUTION: Since 49 = 72 , we first solve the congruence f (x) ≡ 0 (mod 7), since any solution to f (x) ≡ 0 (mod 49) must also be a solution to f (x) ≡ 0 (mod 7). By inspection, we find x ≡ 1 (mod 7) and x ≡ 2 (mod 7) are solutions to the congruence modulo 7. We compute ′ f (x) = 2x + 4. Page 2 of 11

ECM3704/continued . . .

′

′

In particular, f (1) = 6 6≡ 0 (mod 7) and f (2) = 8 ≡ 1 6≡ 0 ′ (mod 7). We now compute the inverse of f (1) (mod 7) which is f ′ (1) = 6 = 6, ′

and an inverse of f (2) (mod 7) which is f ′ (2) = 1. ′

Since f (1) 6≡ 0 (mod 7) then Hensel’s lemma applies. It tell us that there is a unique solution (mod 49) to f (x) ≡ 0 (mod 49) that is congruent to 1 (mod 7). In fact, the solution is x ≡ 1 − f ′ (1)f (1) ≡ 1 − 6 · 7 ≡ −41 ≡ 8 (mod 49). ′

By the same reasoning as before, since f (2) 6≡ 0 (mod 7), Hensel’s lemma tell us there is a unique solution (mod 49) to f (x) ≡ 0 (mod 49) that is congruent to 2 (mod 7), and this solution is x ≡ 2 − f ′ (2)f (2) ≡ 2 − 1 · 14 ≡ −12 ≡ 37 (mod 49). Therefore we conclude that the solutions are x ≡ 8 (mod 49)

and

x ≡ 37 (mod 49).

[Standard problem - similar seen in lectures and example sheets] (8) (c) State (without proof ) the Euler-Fermat theorem and then find the remainder when 252550 is divided by 18. SOLUTION: The Euler-Fermat Theorem: Let n ∈ N, a ∈ Z and suppose that gcd(a, n) = 1. Then aϕ(n) ≡ 1 (mod n). Since 25 ≡ 7 (mod 18) and ϕ(18) = 6, by the Euler-Fermat theorem, 76 ≡ 1 (mod 18). Therefore, 252550 ≡ 72550 ≡ (76 )425 ≡ 1425 ≡ 1 (mod 18). Thus, the desired remainder is 1. [Standard problem - similar seen in lectures and example sheets] (3 marks for the definition and 5 marks for the remainder) (8) Page 3 of 11

ECM3704/continued . . .

(d) Compute the Legendre symbol 

 31 . 641

SOLUTION: 

31 641



= = = = = = = =



 641 as 641 ≡ 1 (mod 4) 31   21 31    7 3 31 31       31 31 − − as 3, 7, 31 are all ≡ 3 (mod 4) 3 7       3 1 − − 3 7    7 as 3, 7, are both ≡ 3 (mod 4) [−1] + 3   1 − 3 −1.

[Standard problem - similar seen in lectures and example sheets] (8) (e) If n = a2 +b2 , we will regard any of the 8 expressions (±a)2 +(±b)2 and (±b)2 + (±a)2 for n as equivalent to a2 + b2 . Find four inequivalent representations of 112201 = 29 · 53 · 73. SOLUTION: It is easy to see that 112201 = 29 · 53 · 73 2

2

and that 29 = 2 + 5 , 53 = 72 + 22 , and 73 = 82 + 32 . Thus computing real and imaginary parts of (2 + 5i)(2 ± 7i)(3 ± 8i) we obtain that 112201 = 852 + 3242 = 1762 + 2852 = 3002 + 1492 = 992 + 3202 . Page 4 of 11

ECM3704/continued . . .

[Standard problem - similar seen in lectures and example sheets] (8) (f) Let p be a prime such that p ≡ 1 (mod 4). Prove that [((p − 1)/2)!]2 ≡ −1 (mod p). SOLUTION: Proof: Because p − i ≡ −i (mod p), (p − 1)! = [1 · 2 · · · (p − 1)/2][((p+1)/2) · · · (p−1)] ≡ [(p−1)/2]! {[−(p − 1)/2] · · · (−2)(−1) } ≡ [(p−1)/2]![(p−1)/2]!(−1)(p−1)/2 ≡ (−1)(p−1)/2 {[(p − 1)/2]!}2 (mod p). Therefore, by Wilson’s theorem, (−1)(p−1)/2 {[(p − 1)/2]!}2 ≡ −1 (mod p); that is, {[(p − 1)/2]!}2 ≡ (−1)(p+1)/2 (mod p). Since p ≡ 1 (mod 4), (p + 1)/2 is odd, so {[(p − 1)/2]!}2 ≡ −1 (mod p). (10) [Unseen, but easy application of theorems from lectures]

Page 5 of 11

ECM3704/continued . . .

[50]

SECTION B 2. Throughout this question, you may use about  standard   facts   the −1 2 3 Legendre symbol, including the values of , and . p p p  m valid for m ∈ Z (a) Give a careful definition of the Jacobi symbol n   2 and odd positive integers n. Prove that the Jacobi symbol n equals 1 if and only if n ≡ ±1 (mod 8). (You may assume that the definition of the Legendre symbol is known). SOLUTION: Definition (Jacobi Symbol): Let n = p1 . . . pr be the factorization of n into not necessarily distinct odd primes. Then m n

:=

 r  Y m i=1

pi

,

where the symbols on the right are Legendre symbols. We also define a1 = 1. Write n = p1 p2 . . . pr where the odd prime factors pi are not necessarily distinct. Then we have

n2 =

r Y

(1 + pi2 − 1) = 1 +

r X

(p2i − 1) +

i6=j

i=1

i=1

X 2 (pi − 1)(pj2 − 1) + · · · .

Since each pi is odd, we have p2i − 1 ≡ 0 (mod 8) so r X (pi2 − 1) n ≡1+ 2

(mod 64)

i=1

hence

r

X1 1 2 (n − 1) ≡ (pi2 − 1) 8 8 i=1

(mod 8).

This also holds modulo 2, hence

Page 6 of 11

ECM3704/continued . . .

 Y   Y r r  2 2 2 2 (−1)(pi −1)/8 = (−1)(n −1)/8 . = = n pi i=1 i=1

As n is odd we must have n ≡ ±1, ±3 (mod 8) and by checking the cases n = ±1, ±3 we deduce that n2 − 1 ≡ 8

( 0 (mod 2), n ≡ ±1 (mod 8) 1 (mod 2), n ≡ ±3 (mod 8),

which completes the proof. [Definition and Proof given in lectures] (3 marks for the definition and 7 marks for the proof) (10) (b) State (without proof ) the Reciprocity Law for Jacobi symbols. SOLUTION: The Reciprocity Law for Jacobi Symbols. Let m and n be coprime odd positive integers. Then m  n  n

m

= (−1)(m−1)(n−1)/4

( +1, if m ≡ 1 (mod 4) or n ≡ 1 (mod 4), = −1, if m ≡ n ≡ 3 (mod 4).

[Theorem stated (and proven) in lectures]

(5)

(c) Let m be an  3odd  positive integer such that 3 does not divide m. Prove that m = 1 if and only if the sum of the exponents of the prime factors congruent to ±5 (mod 12) of m is even. SOLUTION: Qk ei Qk (3/pi )ei . Since pi . Then (3/m) = i=1 Let m = i=1 ( 1, if p ≡ ±1 (mod 12) (3/p) = −1 if p ≡ ±5 (mod 12), we need only consider the case when m contains prime factors ≡ ±5 (mod 12). Each such factor p contributes a −1 to the product, e so (3/p)P contributes (−1)e to the product. Thus (3/m) = 1 if and only if e is even. [Unseen, but easy consequence of standard results] (5)

(d) Let p be an odd prime. Prove that p−1   X j =0 p j=1 Page 7 of 11

ECM3704/continued . . .

where

  j p

is the Legendre symbol.

SOLUTION: By the Proposition 3.4 from the lecture notes, precisely half of the integers in the interval [1, p − 1] are quadratic residues (while the Pp−1  j  other half are non-residues). Therefore in the sum j=1 p half of the terms are equal to 1 and half are equal to −1, so the sum is equal to 0. [Unseen, but easy application of results seen in class] (5) [25] 3. (a) Prove that 30 | (n5 − n), where n is an arbitrary integer. SOLUTION: We have that n5 − n = n(n4 − 1) = n(n2 − 1)(n2 + 1) = n(n − 1)(n + 1)(n2 − 5n + 6 + 5n − 5) = n(n − 1)(n + 1)[(n − 2)(n − 3) + 5(n − 1)] = (n − 3)(n − 2)(n − 1)n(n + 1) + 5(n − 1)2 n(n + 1). The first term on the RHS is the product of five consecutive integers, so it is divisible by 5! = 120. Since 3! | (n − 1)n(n + 1), the second term on the RHS is divisible by 5 · 6 = 30. Thus the RHS is divisible by min(120, 30) = 30. Consequently, 30 | (n5 − n) for every n. [Unseen, application of concepts seen in class] (7) (b) Prove that there is no polynomial f with integer coefficients such that the value f (n) is a prime for every integer n. SOLUTION: Suppose there is such a polynomial f (n) = ak nk + ak−1 nk−1 + · · · + a1 n + a0 , where ak 6= 0. Let b be some integer. Since f (n) is always a prime, f (b) must be a prime p; that is, f (b) = ak bk + · · · + a1 b + a0 = p.

(1)

Let t be an arbitrary integer. Then

Page 8 of 11

ECM3704/continued . . .

f (b + tp) = ak (b + tp)k + ak−1 (b + tp)k−1 + · · · + a1 (b + tp) + a0 = (ak bk + ak−1 bk−1 + · · · + a1 b + a0 ) + p · g(t) where g(t) is a polynomial in t. Thus, by (1) f (b + tp) = p + pg (t) = p[1 + g(t)]. So p | f (b + tp). But every value of f is a prime, so f (b + tp) must be a prime and hence f (b + tp) = p. Thus, f (b) = p = f (b + tp). This implies f takes on the same value infinitely many times, since t is an arbitrary integer. But f (n) is a polynomial of degree k, so it cannot assume the same value more than k times, yielding a contradiction. Thus, no polynomial with integral coefficients exists that will generate only primes. [Unseen, application of concepts seen in class] (10) (c) Prove that an odd integer n > 1 is a prime if and only if it is not expressible as a sum of three or more consecutive positive integers. SOLUTION: If an odd integer n is expressible as a sum of three or more consecutive positive integers, then for some m ≥ 1 and k ≥ 3, n = m + (m + 1) + . . . + (m + (k − 1)) = km +

k(k − 1) . 2

If k is odd, then n = k(m + k−1 ) and cannot be prime (k and 2 k−1 m + 2 are integers strictly bigger than 1). If k is even, then, n = k2 (2m + (k − 1)) and once again cannot be prime as k/2 and 2m + (k − 1) are integers strictly bigger than 1. Conversely, if an odd integer n is not prime, write n = ab for some other positive integers a and b strictly bigger than 1. Then a and b must be odd. Assume a ≤ b without loss of generality. Let k = a ≥ 3 and m = b − a−1 ≥ a − a−1 = a+1 ≥ 2. Then, 2 2 2 m+(m+1)+· · ·+(m+(k−1)) = km+

k−1 k(k − 1) ) = ab = n. = k(m+ 2 2

[Problem similar to the ones in Example sheets]

(8) [25]

Page 9 of 11

ECM3704/continued . . .

4. (a) Prove that if n ≡ 3 (mod 4), then n is not representable as the sum of two squares. SOLUTION: Suppose n = x2 + y 2 for some integers x and y. Since w2 ≡ 0 or 1 (mod 4) for any integer w, it follows that n = x2 + y 2 ≡ 0, 1 or 2 (mod 4). Since n ≡ 3 (mod 4), the result follows. [Unseen, but easy application of concepts and results seen in class] (5) (b) Let p be a prime. Prove that if p ≡ 1 (mod 4), then there are positive integers x and y such that x2 + y 2 = kp for some positive integer k, where k < p. SOLUTION: Since p ≡ 1 (mod 4) and that −1 is a quadratic residue of p we have that there is a positive integer a < p such that a2 ≡ −1 (mod p); that is, a2 + 1 = kp for some positive integer k. Thus, there are integers x = a and y = 1 such that x2 + y 2 = kp. It remains to show that k < p. Since a ≤ p − 1 and kp = a2 + 1 < (p − 1)2 + 1, kp < p2 − 2(p − 1); so kp < p2 and hence k < p, as desired. [Similar to results seen in class] (8) (c) Prove that every prime p ≡ 1 (mod 4) can be written as the sum of two squares. SOLUTION: By part (b) and the well-ordering principle we obtain that there is a least positive integer m such that mp = x2 + y 2 for some suitable positive integers x and y. We shall show that m = 1 by contradiction. Suppose m > 1. Define integers r and s by

r ≡ x (mod m)

and

s≡y

(mod m)

(2)

where −m/2 < r, s ≤ m/2.

(3)

Then r 2 + s2 ≡ x2 + y 2 = mp ≡ 0 (mod m), so r 2 + s2 = mn for some positive integer n. Therefore, (r 2 + s2 )(x2 + y 2 ) = (mn)(mp) = m2 np. But, using the result (seen in lectures) Page 10 of 11

ECM3704/continued . . .

that the product of two sums of two squares is representable as the sum of two squares, we have that (r 2 + s2 )(x2 + y 2 ) = (rx + sy)2 + (ry − sx)2 . Thus, (rx + sy)2 + (ry − sx)2 = m2 np.

(4)

It follows by congruences (2) that rx+sy ≡ x2 +y 2 ≡ 0 (mod m)

and

ry −sx ≡ xy−yx ≡ 0 (mod m).

These two congruences imply that both (rx + sy)/m and (ry − sx)/m are integers. It now follows from (4) that np =



rx + sy m

2

+



ry − sx m

2

which is a sum of two squares. The inequalities (3) imply that mn = r 2 +s2 ≤ (m/2)2 + (m/2)2 = m2 /2. Thus, mn ≤ m2 /2; that is, n ≤ m/2. Therefore, n < m. Now n 6= 0, since if n = 0, then r 2 + s2 = 0; so r = 0 = s. Then x ≡ 0 ≡ y (mod m), so m | x and m | y. Therefore, m2 | (x2 +y 2 ): that is, m2 | mp. This implies m | p. Since m < p by part (ii), m must be 1. This negates our hypothesis that m > 1. Therefore n ≥ 1. Thus, n is a positive integer < m such that np is a sum of two squares. This is a contradiction, since we assumed that m is the least such positive integer. Consequently, m = 1; that is, p = x2 + y 2 , as desired. [Proven in class] (12) [25]

Page 11 of 11

ECM3704/END OF PAPER...