Question

Let p be a prime and let a be a primitive root modulo p. Show that...

Let p be a prime and let a be a primitive root modulo p. Show that if gcd (k, p-1) = 1, then b≡ak (mod p) is also a primitive root modulo p.

Math   Advanced-Math   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Since is a primitive root of unity modulo prime , there exists such that , and if . Note that implies . Suppose that . Then there exists integers such that . If then

Thus, is a root of unity modulo . If possible, suppose that there is such that . Then we get

From we get ; therefore,

Since and , this implies . Also, from Fermat's little theorem we get . Therefore,

But this contradicts the assumption of primitivity of since (as we explained at the beginning) primitivity implies if . Therefore, we have proved that is a primitive -th root of unity modulo .

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let b be a primitive root for the odd prime p. Prove that b^k is a...
Let b be a primitive root for the odd prime p. Prove that b^k is a primitive root for p if and only if gcd(k, p − 1) = 1.
Use the fact that each prime possesses a primitive root to prove Wilson’s theorem: If p...
Use the fact that each prime possesses a primitive root to prove Wilson’s theorem: If p is a prime, then (p−1)! ≡ −1 (mod p).
Let m > 1. If there exists a primitive root modulo m, prove that there are...
Let m > 1. If there exists a primitive root modulo m, prove that there are exactly φ(φ(m)) primitive roots modulo m. *Note that φ() is Euler's totient function.
Let p be an odd prime. Prove that −1 is a quadratic residue modulo p if...
Let p be an odd prime. Prove that −1 is a quadratic residue modulo p if p ≡ 1 (mod 4), and −1 is a quadratic nonresidue modulo p if p ≡ 3 (mod 4).
(i) Verify that 2 is a primitive root modulo 29. (ii) Find all the primitive roots...
(i) Verify that 2 is a primitive root modulo 29. (ii) Find all the primitive roots modulo 29. Explain how you know you have found them all. (iii) Find all the incongruent solutions to x6 ≡ 5(mod 29).
using discrete logarithms for modulo 17 relative to primitive root 3, solve the following: x^12 (is...
using discrete logarithms for modulo 17 relative to primitive root 3, solve the following: x^12 (is equivalent to) 13(mod 17) PLEASE SHOW ALL STEPS IN DETAIL ANd show ALLL POSSIBLE ANSWERS (values of x)
Given that 2 is a primitive root modulo 19, find all the primitive roots modulo, 19....
Given that 2 is a primitive root modulo 19, find all the primitive roots modulo, 19. You must know how you are getting your answer and make sure all your answers are in the canonical residue set
Let p be an odd prime of the form p = 3k+2. Show that if a^3...
Let p be an odd prime of the form p = 3k+2. Show that if a^3 ≡ b^3 (mod p), then a ≡ b (mod p). Conclude that 1^3,2^3,…,p^3 form a complete system of residues mod p.
Suppose that gcd ( a , 53 ) = 1 , a 4 ≢ 1 (...
Suppose that gcd ( a , 53 ) = 1 , a 4 ≢ 1 ( mod 53 ) , and a 26 ≢ 1 ( mod 53 ) . Show that a is a primitive root mod 53 . Let n = 151 and suppose gcd ( a , n ) = 1 . How many powers of a would you have to check to determine whether a is a primitive root mod n ?
Formal Proof: Let p be a prime and let a be an integer. Assume p ∤...
Formal Proof: Let p be a prime and let a be an integer. Assume p ∤ a. Prove gcd(a, p) = 1.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT