# Thread: Proof: Primative root mod(p)

1. ## Proof: Primative root mod(p)

hi, i'm stuck on this assignment question. my teacher said it's really easy so i think i'm just missing something obvious? thanks

Let p be an odd prime and g be a primitive root modulo p. Let y be an integer such
that gcd(y, p-1) = 1. Show that g^y is a primitive root modulo p.

2. If gcd(y,p-1)=1 then {1,2,3,...,p-1}={y,2y,3y,...,(p-1)y} mod p.

Given a=g^b, then a=(g^y)^(bc) where c=y^(-1) mod(p-1)

3. Originally Posted by davidodea
hi, i'm stuck on this assignment question. my teacher said it's really easy so i think i'm just missing something obvious? thanks

Let p be an odd prime and g be a primitive root modulo p. Let y be an integer such
that gcd(y, p-1) = 1. Show that g^y is a primitive root modulo p.
Here's what I think.... The goal is to show that the order of $g^y$ modulo $p$ is the equal to $p-1$ (namely, primitive root).
Let the integer $t$ be the order of $g^y$ modulo $p$, so $t|p-1$. Also, $(g^y)^t=g^{yt}\equiv 1\bmod p$ and the order of $g$ modulo $p$ must divide $yt$, so $p-1|yt$. Now you can use $gcd(y,p-1)$...

4. Originally Posted by chiph588@
If gcd(y,p-1)=1 then {1,2,3,...,p-1}={y,2y,3y,...,(p-1)y} mod(p-1).
Sorry, i don't understand why if the gcd(y,p-1)=1 then 1=y [mod (p-1)]

eg for p=17 and y=39
gcd(39,16)=1 , but 1 =/ 39 mod 16?

5. Originally Posted by davidodea
That's not what I meant. Let $\displaystyle A=\{1,2,3,\ldots,p-1\}$ and $\displaystyle B=\{y,2y,3y,\ldots,(p-1)y\}$.
I'm saying that for all $a\in A, \; \exists \; b\in B$ such that $a\equiv b\bmod{p}$ and for all $b\in B, \; \exists \; a\in A$ such that $a\equiv b\bmod{p}$.
So I say $A\equiv B\bmod{p}$.