# Proof: Primative root mod(p)

• Aug 10th 2010, 01: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.
• Aug 10th 2010, 07: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)
• Aug 10th 2010, 03: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 $\displaystyle g^y$ modulo $\displaystyle p$ is the equal to $\displaystyle p-1$ (namely, primitive root).
Let the integer $\displaystyle t$ be the order of $\displaystyle g^y$ modulo $\displaystyle p$, so $\displaystyle t|p-1$. Also, $\displaystyle (g^y)^t=g^{yt}\equiv 1\bmod p$ and the order of $\displaystyle g$ modulo $\displaystyle p$ must divide $\displaystyle yt$, so $\displaystyle p-1|yt$. Now you can use $\displaystyle gcd(y,p-1)$...
• Aug 10th 2010, 05: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?
• Aug 10th 2010, 05:52 PM
chiph588@
Quote:

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