Proof: Primative root mod(p)

**davidodea** · August 10th 2010, 01:49 AM

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.

**chiph588@** · August 10th 2010, 07:16 AM

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)

**melese** · August 10th 2010, 03:20 PM

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

**davidodea** · August 10th 2010, 05:47 PM

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).

Hi, thanks for the reply..
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?

**chiph588@** · August 10th 2010, 05:52 PM

Originally Posted by davidodea

Hi, thanks for the reply..
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?

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

Thread: Proof: Primative root mod(p)

LinkBack

Thread Tools

Display

Proof: Primative root mod(p)

Similar Math Help Forum Discussions

N-th Root Irrationality Proof

Proof there is a root

Primative roots and indexes

Root 2 recursion proof help

[SOLVED] proof of root 3