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.

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

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.

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.