# If a is a $\mathbb Z / p\mathbb Z$ generator, if $k$ is not a multiple of $p-1$, $a ^ k \not\equiv 1\pmod p$ [duplicate]

If $$a$$ is a $$\mathbb Z / p\mathbb Z$$ generator, if $$k$$ is not a multiple of $$p-1$$, $$a ^ k \not\equiv 1\pmod p$$.

I don't understand why.

What does "$$a$$ is a $$\mathbb Z / p\mathbb Z$$ generator" mean?

• Use the definition of generator or think what could be the order of a ? – Chinmaya mishra Oct 4 at 15:26
• @Chinmaya mishra G={a^n｜n∈Z/pZ}...What should I do next? – MENZIES Oct 4 at 15:31
• think when can be the power of a be 1? – Chinmaya mishra Oct 4 at 15:35
• Oh it's p-1. But...what does "𝑎 is a ℤ/𝑝ℤ generator" mean? – MENZIES Oct 4 at 15:47
• It means that a generates the whole group ℤ/𝑝ℤ or any element of ℤ/𝑝ℤ can be represented as power of a . – Chinmaya mishra Oct 4 at 15:50

Since $$\mathbb Z/p\mathbb Z$$ has order $$p$$, $$\operatorname{ord}(a)=p$$. But this means that, in particular, that $$a^k\neq1$$ if $$k\in\{1,2,\ldots,p-2\}.$$

• 𝑘∈{1,2,…,𝑝−2}? – MENZIES Oct 4 at 15:55
• Right. I've edited my answer. Thank you. – José Carlos Santos Oct 4 at 15:57

If $$a$$ is a generator, then $$a,a^2,\ldots,a^{p-1}$$ are all different. Because if there were two of them equal, in that sequence there would be fewer than $$p-1$$ different elements.

We know by little Fermat's Theorem that $$a^{p-1}=1$$.

So take $$k$$ s.t. $$a^k\neq 1$$. Now use Euclidean division $$k/(p-1)$$: $$k=q(p-1)+r$$. Then $$a^k=a^{q(p-1)+r}=(a^{p-1})^q\cdot a^r=1^q\cdot a^r=a^r$$

Since $$k$$ is not a multiple of $$q-1$$, $$r\neq 0$$ and $$r. So $$a^k\neq 1$$.

• I understood. Thanks. – MENZIES Oct 4 at 16:08

HINT:

If you're question is "Let $$a$$ be a generator of $$\Bbb Z/p \Bbb Z$$, if $$k$$ is not a multiple of $$p-1$$, then $$a^k \not \equiv 1$$ (mod $$p$$)".

Then this is the same as asking "Let $$a$$ be a generator of $$\Bbb Z/p \Bbb Z$$, if $$a^k \equiv 1$$ (mod $$p$$), then $$k$$ is a multiple of $$p-1$$."