MATH-UA-248 / UY-4014 — The Theory of Numbers
Homework Assignment #8
Due Date: April 29, 2024, 11:59 PM
• This homework should be submitted via Gradescope by 11:59 PM on the date listed above.
• There are two main ways you might want to write up your work.
– Write a PDF using a tablet
– Write your answers on paper, clearly numbering each question and part.
∗ You can use an app such as OfficeLens to take pictures of your work with your phone and convert them into a single pdf file. Gradescope will only allow pdf files to be uploaded.
• You must show all work. You may receive zero or reduced points for insufficient work. Your work must be neatly organized and written. You may receive zero or reduced points for incoherent work.
• Please start a fresh page for each numbered problem. You may have parts a), b) and c) on the page for example, but problems 1) and 2) should be on separate pages.
• When uploading to Gradescope, you must match each question to the page that your answer appears on. If you do not, we will be unable to grade the unmatched problems.
• When appropriate, please put a box or circle around your final answer.
• The problems on this assignment will be graded on correctness and complete- ness.
Lecture 16
1. (10 points) The orders of integers in Zn.
(a) Find the orders of the integers 2, 3, and 5 in each of the rings Z17 , Z19 , Z23 .
(b) Show that n | ϕ(2n − 1) for any n > 1.
(c) If a number a has order n−1 in Zn , show that n must be a prime number.
2. (10 points) Primitive roots in Zp.
(a) Assume p is an odd prime, then show that the only distinct solutions to x2 = 1 in Zp are 1 and p − 1.
(b) Moreover, show that xp −2 + ... +x2 +x+1 = 0 has exactly p−2 different solutions in Zp. What are they?
(c) Find by hand all of the primitive roots of Zp where p ∈ {11, 19, 23}.
Lectures 17 - 18
3. (10 points) Primitive roots of composite numbers. For these problems you may assume that p is always an odd prime.
(a) Find the primitive roots of Zn for n = 25, 26 (there should be 12 in total, split 8-4).
(b) Show that there are the same number of primitive roots in Zpn as there are in Z2pn .
(c) Show that any primitive root of Zpn is also a primitive root of Zp. (d) A primitive root of Zp2 is also a primitive root of Zpn .
4. (10 points) A nice piece of theory: let n = 2k0 “i(r)=1 pi(k)i be the prime factoriza-
tion of n (so pi are the odd primes in the factorization). Define the “universal exponent of n” by the formula
λ(n) := LCM(λ(2k0 ),ϕ(p1(k)1 ),...,ϕ(pr(k)r ))
where λ(2) = 1, λ(4) = 2, and λ(2k ) = 2k −2 for k ≥ 3. Note λ is not always equal to ϕ when evaluated on powers of two, in particular λ(8) = 2 = λ(4). We’re going to work out several cool facts about λ .
(a) Show that if n = 2, 4, pk , 2pk then λ(n) = ϕ(n). Here, p is an odd prime.
(b) Show that if a is not divisible by any power of two, then aλ(2k ) = 1 ∈ Z2k . This can be done fairly quickly with induction on k, once you know how to compute λ(2k ).
(c) Show that if (a,n) = 1 then aλ(n) = 1 ∈ Zn. Just like the totient function!
(d) Use the previous part to give a different proof (from the one we did in class) that if n 2, 4, pk , 2pk then Zn has no primitive roots. Hint: try to show that for n not on that list we have λ(n) < ϕ(n), then explain clearly why this inequality means there can be no primitive roots in Zn.
(e) Finally show that if (a,n) = 1 then the equation ax = b ∈ Zn has solution x = baλ(n) − 1 .