3. Let p>3 be an odd prime and let {ri,r2, .r} be the set of incongruent primitive roots modulo p. Compute the p...

Question

Question

Answer 1

Answer #1

$g$ is a primitive root then every other primitive root is of the form $g^k$ where $gcd (k, p 1) 1$

So that $II ged (k,p-1)-1$ is the quantity we are interested in

Which equals $ged(k.p-1)-1$

But $(p-1) ged(k,p-1)-1 ged(kp-1)-1$

So that $2S (p 1) (p 1)(p - 1) ged(kp-1)-1$

So that k (p 1)p 1)/2 ged (k.p-1)-1

So that $P-1(p-1) g 2$ is the product of all the distinct primitive roots

Which is $\left(g^{\frac{p-1}{2}} \right )^{\phi(p-1)}=(-1)^{\phi(p-1)}\pmod{p}$

And so the product of all the primitive roots modulo prime $p$ is $-1)p-1) (mod p)$

Answer 2

Similar Homework Help Questions

7.23 Theorem. Let p be a prime congruent to 3 modulo 4. Let a be a natural number with 1 a< p-1. Then a is a quadrut...

7.23 Theorem. Let p be a prime congruent to 3 modulo 4. Let a be a natural number with 1 a< p-1. Then a is a quadrutic residue modulo pif and only ifp-a is a quadratic non-residue modulo p. 7.24 Theorem. Let p be a prime of the form p odd prime. Then p 3 (mod 4). 241 where q is an The next theorem describes the symmetry between primitive roots and quadratic residues for primes arising from odd Sophie...
Let g be a primitive root modulo to the odd prime p. Prove that:

Let g be a primitive root modulo to the odd prime p. Prove that: 2)=-1 2)=-1
2.5. Let p be an odd prime and let g be a primitive root modulo has...

2.5. Let p be an odd prime and let g be a primitive root modulo has a square root modulo p if and only if its discrete logarithm log,(a) mod p. Prove t that is even.

Let p be an odd prime. Prove that if g is a primitive root modulo p, then g^(p-1)/2 ≡ -1 (mod p).

Let p be an odd prime. Prove that if g is a primitive root modulo p, then g^(p-1)/2 ≡ -1 (mod p). Let p be an odd prime. Prove that if g is a primitive root modulo p, then go-1)/2 =-1 (mod p) Hint: Use Lemma 2 from Chapter 28 (If p is prime and d(p 1), then cd-1 Ξ 0 (mod p) has exactly d solutions). Let p be an odd prime. Prove that if g is a primitive...
76.Let p be an odd prime. Prove that if Ord, (a) = his even, then a/2...

76.Let p be an odd prime. Prove that if Ord, (a) = his even, then a/2 = -1 mod p. 77.let p be an odd prime. Prove that if Ord, (a) = 3, then 1+ a + a? = 0 mod p and Ord,(1 + a) = 6. 78.Show that 3 is a primitive root modulo 17. How many primitive roots does 17 have? Find them.
please prove proofs and do 7.4 7.2 Theorem. Let p be a prime, and let b...

please prove proofs and do 7.4 7.2 Theorem. Let p be a prime, and let b and e be integers. Then there exists a linear change of variahle, yx+ with a an integer truns- farming the congruence xbx e0 (mod p) into a congruence of the farm y (mod p) for some integer 8 Our goal is to understand which integers are perfect squares of other inte- gers modulo a prime p. The first theorem below tells us that half...

(b) Let p be a prime that is congruent to 3 modulo 4. Let b ∈...

(b) Let p be a prime that is congruent to 3 modulo 4. Let b ∈ Z. Let a = b (p+1)/4 . Show that a 2 ≡ ±b (mod p). (c) Give an algorithm to compute square roots of something modulo p, when p ≡ 3 (mod 4). Note: Not all things are square modulo p, so the algorithm should return the square root or inform you there is no square.
Please prove the 3 theorems, thank you! 7.6 Theorem. Let p be a prime. Then half the numbers not congruent to 0 modulo p...

Please prove the 3 theorems, thank you! 7.6 Theorem. Let p be a prime. Then half the numbers not congruent to 0 modulo p in any complete nesidue system modulo p are quadratic residuess modulo p and half are quadratic non-residues modulo p. From clementary school days, we have known that the product of a pos- itive number and a positive number is positive, a positive times a negative is negative, and the product of two negative numbers is positive....
8. Let g be a primitive root of an odd prime p, and suppose that p3 (mod 4). Show that -g is not ...

8. Let g be a primitive root of an odd prime p, and suppose that p3 (mod 4). Show that -g is not a primitive root of p. 8. Let g be a primitive root of an odd prime p, and suppose that p3 (mod 4). Show that -g is not a primitive root of p.

please do 7.19 7.20 and 7.21 7.19 Theorem (Quadratic Reciprocity Theorem and q be odd primes,...

please do 7.19 7.20 and 7.21 7.19 Theorem (Quadratic Reciprocity Theorem and q be odd primes, then Reciprocity Part). Let p (e)99 (mod 4) if p (mod 4) or q1 i p 3 (mod 4). (i)) (llint: Iry to use the techniquets used in the case of Putting together all our insights, the Law of Quadratic Reciprocity. we can write one theorem that we call Theorem (Iaw of Quadratic Reciprocity). Let p and q be odd primes, then if p...