Let p be a prime number. We call a unit a in Z/pZ a primitive root, if ordp(a) =

Question

Let p be a prime number. We call a unit a in Z/pZ a primitive root, if ordp(a) = p - 1, i.e. any unit in Z/pZ can be written as some power of a. If p is of the form 2" + 1, prove that the primitive roots in Z/pZ are precisely the quadratic non-residues modulo p. If n > 1, prove 3 is always a primitive root. Let p be an odd prime, and (a,p) = 1. Show that if x2 = a(mod p) has solutions, then x2 = a(mod pN) always lias solutions, for any N > 1. Does x2 + x + 1 =0(mod 997) haw solutions? Why or why not?

Explanation / Answer

Consider the set S={am+bn | m,n are integers and am+bn>0}. Since S is obviously nonempty (if some choice of m and n makes am+bn<0, then replace m and n by -m and -n), the Well Ordering

Principle asserts that S has a smallest member, say, d=as+bt. We claim that d=gcd(a,b). To verify this claim, use the division algorithm to write a=dq+r, where 0<=r

n =

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.