Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 2

MAT315: Introduction to Number Theory

Due May 26th

Problem 1. Use Euclid’s proof of the infinitude of the primes to give an explicit lower bound of the form C log log x < π(x) on the prime-counting function.

Solution: We prove by induction that the rth prime is less than 22r . For the base case, p1  = 2 < 221 = 4. For the inductive hypothesis, assume that for every k < r , pk < 22k . Then using Euclid’s proof of the infinitude of the primes, the inductive hypothesis, and the formula for the geometric series,

we obtain

r−1                         r−1

pr ≤ u pk + 1 对k(r) − 1 2k   + 1 = 22r −1 + 1

k=1                       k=1

For r > 1, 22r −1  > 1, so the rightmost term in the expression above is less than 22r −1 + 22r −1  = 22r . Since the prime counting function is monotone and only changes at integer values, we deduce that the inequality r < π(22r ) can be extended to the positive real numbers greater than 2. Thus, substituting log2 log2 x for r, we get that

log2 log2 x < π(x)

Finally, as log2 x > 0.6logx and log2 (0.6log(x)) > 0.01loglog(x) for x > 10, we conclude that 0.01loglog(x) < π(x) for all x > 10.  Remark:  The exact constant C is not too important, and could be optimized       further.

Problem 2. Show the converse to Wilson’s theorem. That is, show that if (m − 1)! ≡m  − 1, then m must be prime.

Proof: Assume m is not a prime. Then there exist two positive integers a,b ∈ {1, ...,m − 1} such that ab = m. Thus, we obtain a chain of congruences

m−1                                    m−1

(m − 1)! ≡m  ab      u      i ≡m  0 *      u      i ≡m  0

But 0 \≡m − 1, so we deduce that (m − 1)! \≡m − 1, as desired □ .

Problem 3. a) Let p be a prime and let a be an integer not divisible by p. Determine the number

of solutions to the equation x2 − y2 ≡p  a.

b) With the same assumptions, determine the number of solutions to the equation x2 + y2  ≡p  a.

Solution:  a) Consider the change of variables u = x − y,v = x + y .  This change of variables is invertible, hence the number of solutions to the equation x2  − y2  ≡p  a is the same as the number of  solutions to the equation uv ≡p  a. Since a is not divisible by p, any solution to this last equation must have u,v \≡p  0.  Now, for each choice of u ∈ {1, ...p − 1}, theorem 2.9 implies that there is a unique choice of v such that uv ≡p  a, namely v = ua. Thus the equation has precisely p − 1 solutions □ .

b) We split into cases depending on if p = 2, p ≡ 1 mod 4 or p ≡ 3 mod 4.

Case 1: If p = 2, the only possibility for the residue class of a is that of 1. By inspection, we see that {(0, 1), (1, 0)} are the only solutions, so there are 2 solutions.

Case 2: If p ≡ 1 mod 4, then by theorem 2.12, we know there exist some i which solves the congruence x2  ≡p  − 1.  Under the change of variables u = x,v = iy, the congruence x2 + y2  ≡p  a transforms to x2 − y2  ≡p  a. Therefore by part a) we conclude that the equation has p − 1 solutions.

Case 3: If p ≡ 3 mod 4, consider the function

f : C(p) × C(p) \ {(0, 0)} −→ C(p) \ {0} : (x,y) →I (x2 + y2 )

By theorem 2.12, this is well defined, as if f(u,v) ≡p  0 then u solves the congruence x2  ≡p  1, which is absurd in this case.  As x,y ranges over {1, ...,p − 1}, the expressions x2  mod p and a − y2  mod p each take on at most p − 1 distinct values.  Hence by the pigeonhole principle there exist (u,v) such that f(u,v) ≡p  a for any value of a. Now, I claim that the number of solutions is independent of a, so that #f−1(a) = #f−1(b) for all a,b ∈ {1, ...,p − 1} . Indeed, taking an arbitrary (u,v) ∈ f −1(b), the map

(x,y) →I (xu − vy,xu + vy)

is  a bijection between  f −1(a)  and  f −1(b):   A simple computation shows  f(xu − vy,xu + vy)  = f(x,y)f(u,v) and we get an inverse by picking an arbitrary pair in f −1(b).   Putting all of this together, we conclude that the number of solutions to the equation is given by

#C(p) × C(p) \ {(0, 0)} p2 − 1

=

#C(p) \ {0}                   p − 1

and therefore there are p + 1 solutions to the equation □ .

Problem 4. Let p be a prime and let n ∈  {1, 2, ...,p − 1} .  Define the quadratic form Qn (x,y) := x2 + ny2

a)  Prove that if the congruence x2 ≡p −n has a solution, then Qn   represents at least one of the

numbers p,2p, ..., (p − 1)p.

b) Prove that if Q2  represents 2p, then it represents p.  Deduce that if x2 ≡p − 2 has a solution, then Q2  represents p.

c) In the other direction, prove that if p is represented by Q2 , then x2 ≡p − 2 has a solution.

Proof: a) We adapt the proof of lemma 2.13. Let x be a solution to x2  ≡p  −n. Define K = ⌊ √p⌋ and define

f : {0, 1, ··· ,K}2 → }

by

f(u,v) = residue class of u + xv

By the definition of K , '{0, 1, ··· ,k}2 ' = (k+1)2  > ( √p)2  = p, thus by the pigeonhole principle ∃ pairs (v1 ,v1 )&(v1 ,v2 ) with f (u1 ,v1 ) = f (u2 ,v2 ). Let a = u1  − u2  and b = v1  − v2 . I claim that a2 + nb2  represents one of p,2p, ..., (p − 1)p.  By construction, a ≡p   −xb.  Thus a2  ≡p   ( −xb)2  ≡p   −nb2  and a2 +nb2  ≡ 0. So it’s enough to show 0 < a2 +nb2 < p2 , because p,2p, ...(p − 1)p are all the multiples of p in this range. But |a| < √p and |b| < √p and n ≤ p − 1, therefore a2 +nb2 < √p2 +(p − 1) √p 2  = 2p

b) Say Q2  represents 2p. That is, 2p = a2 + 2b2  for some integers a and b. Then as 2 | 2p and 2 | 2b2 , it must be the case that 2 | a2 . It follows that we can rewrite a as 2c for some integer c. Consequently, 2p = 4c2 + 2b2  and dividing both sides by 2 gives p = b2 + 2c2 , thus the quadratic form Q2  represents p   □ .

c) Let u,v be such that u2  + 2v2  = p.  Since p is prime, it must be the case that both u and v are nonzero and that gcd(v,p) = 1.  Thus by theorem 2.9 there exist such that v ≡p  1.  Now, if we multiply both sides of the congruence

u2 + 2v2  ≡ 0 mod p

by 2 , we obtain

(u)2 + 2 ≡ 0 mod p

and rearranging this expression yields (u)2 ≡p − 2, as desired □ .