(1) Suppose p and q = (4p + 1) are both primes. If a is a quadratic non-residue

Question

(1) Suppose p and q = (4p + 1) are both primes. If a is a quadratic non-residue of q show that a is either a primitive root of q, or that a has order 4 (mod q).

(2) Let n be an integer. Show that a prime p > 5 is a divisor of (n2 + n +5) if and only if p is a quadratic residue mod 19. (Hint: Compute (n +1/2)2 )

(3) Let n be a positive integer, and consider the equation 1/x + 1/y = 1/n . How many distinct solutions does this equation have with x and y positive integers? (Hint: Compute (x-n)(y-n).)

Explanation / Answer

(1) Given that p and q = 4p+1 are primes.

Also given that a is a quadratic non residue of q.

Hence by Fermat's Little theorem, the order of a divides q-1 is 4p.

Let ( Z/q)* is cyclic generated by some primitive root m.

Since a is a nonresidue mod q, we have a = q(odd power) and

a2p = a(q-1)/2

= [m(2r+1)] (q-1)/2

= m(q-1)/2

   -1 mod q

The above statement implies that ap 1 mod q and a2 1 mod q.

Hence the possible values of a are 4p and 4.

Now, if a has order 4p =q-1, then it is also a primitive root of q.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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