-2
$\begingroup$

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?

Please tell me.

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

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

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

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<p-1$. So $a^k\neq 1$.

$\endgroup$
  • $\begingroup$ I understood. Thanks. $\endgroup$ – MENZIES Oct 4 at 16:08
1
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.