Proof: Primative root mod(p)

• August 10th 2010, 02:49 AM
davidodea
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 (Headbang)

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.
• August 10th 2010, 08:16 AM
chiph588@
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)
• August 10th 2010, 04:20 PM
melese
Quote:

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 (Headbang)

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)$...
• August 10th 2010, 06:47 PM
davidodea
Quote:

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?
• August 10th 2010, 06:52 PM
chiph588@
Quote:

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}$.