# Thread: how to prove multiplicative integers (mod p) has at least one generator?

1. ## how to prove multiplicative integers (mod p) has at least one generator?

How do you prove the multiplicative integers (mod p) has at least one generator?
I know how to show a^(p-1) is congruent to 1 using Fermat's Little Theorem but how do you show p-1 is the smallest such integer?

Thanks!

2. ## Re: how to prove multiplicative integers (mod p) has at least one generator?

How do you prove the multiplicative integers (mod p) has at least one generator?
I know how to show a^(p-1) is congruent to 1 using Fermat's Little Theorem but how do you show p-1 is the smallest such integer?

Thanks!
p-1 may not be the smallest such integer. example: in the multiplicative group mod 7,

$2^6=1$ by Fermat's Little Theorem but we also have $2^3=1$

3. ## Re: how to prove multiplicative integers (mod p) has at least one generator?

What I mean is how do I show that there is at least one integer whose smallest power that makes it congruent to 1 must be p-1?
In other words prove that the group of multiplicative integers (mod p) where p is prime must have at least one generator.

...as you say other (non-generator) integers have smaller powers that make them congruent to 1.

4. ## Re: how to prove multiplicative integers (mod p) has at least one generator?

in other words you want to prove that the multiplicative group of nonzero integers mod p is cyclic

a proof can be found in an algebra textbook