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

MAT315

Problem Set 5

To get a full mark you must show all your work and justify your answers.  Feel free to discuss the problem set questions and post about them on Ed Discussion.  You can provide clarity on the problems when needed and give hints when appropriate.  All numbers/variables are integers unless stated otherwise. This problem set covers up to Lecture 18.

1. Let m and n be positive integers with gcd(m, n) = d. Prove that

φ(m) . φ(n) = φ(mn) .


d

     2. Let k be a positive integer and p > 3 be a prime. Prove that


 

1k + 2k + . . . + (p _ 1)k  = 

(Hint: You should express the numbers 1, 2, . . . , p _ 1 in terms of a primitive root g in mod p)

 

3.   (a) Let n be an even integer and p be a prime such that p | n4 + 1. Prove that p = 1  (mod 8). (Hint: What can you say about ordp(n)?)

(b)  Modify the proof of the infinitude of the primes of the form 4k + 3 (Lecture 4) to show that there are infinitely many primes of the form 8k + 1 using part (a).

 

4. Let n be a positive integer and a and b be units modulo n satisfying ordn(a) = 4 and ordn(b) = 9. Prove that ordn(ab) = 36.

 

5. Let a be an integer such that gcd(a, 19 . 25 . 29) = 1. Prove that the congruence x70 = a    (mod 19 . 25 . 29)

has either 0 or 280 solutions in 19125129  (You may nd Q2-(a) of PS3 useful for this problem).

 

6.   (a) How many primitive roots 25  has? Find all of them. Show all your steps/computations.

 

(b) List all primitive roots 1 < g < 125 modulo 125 from smallest to largest. Justify your answer with two-three sentences of explanation.

 

(c) List all primitive roots 1 < g < 50 modulo 50 from smallest to largest.  Justify your answer with two-three sentences of explanation.