Let $p$ be a prime, and ($x,p$) = $1$
If for integers $a$ and $b$ we have $x^a \equiv x^b$ (mod $p$) for all $x \in \Bbb Z$, show that $a \equiv b$ (mod $p-1$)
I know that if $x^a \equiv 1$(mod $p$), then it implies that $a \equiv 0$(mod $p-1$), but I don't know how to go from here.
Any tips would be appreciated!
Answer
Hint $ $ Let $\,x = a\,$ be a primitive root, i.e. $\,a\,$ has order $\,p-1\,$ Then it is the special case of $(\Leftarrow)$ below where $\, m=p\,$ and $\,e = p-1\,$ (by little Fermat).
Theorem $ \ \ $ Suppose that: $\,\ \color{#c00}{a^{\large e}\equiv\, 1}\,\pmod{\! m}\ $ and $\, e>0,\ n,k\ge 0\,$ are integers. Then
$\qquad n\equiv k\pmod{\! \color{#c00}e}\,\Longrightarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}.\ $ Further, $ $ conversely
$\qquad n\equiv k\pmod{\! \color{#c00}e}\,\Longleftarrow\,a^{\large n}\equiv a^{\large k}\pmod{\!m}\ \, $ if $\,a\,$ has order $\,\color{#c00}e\,$ mod $\,m$
Proof $\ $ Wlog $\,n\ge k\,$ so $\,a^{\large n} \equiv a^{\large n-k} \color{#0a0}{a^{\large k}}\equiv \color{#0a0}{a^{\large k}}\!\iff a^{\large n-k}\equiv 1,\,$ by cancelling $\,\color{#0a0}{a^{\large k}}\,$ using $\,a^{\large e}\equiv 1\,\Rightarrow\, a\,$ is invertible so cancellable (cf. Remark). $\,n\equiv k\pmod{\!e}\Longrightarrow\,$ $a^{\large n-k}\equiv 1,\,$ and conversely if $\,a\,$ has order $\,e,\,$ by here,
Remark $ $ If you are familiar with modular inverses then it is not necessary to restrict to nonnegative powers of $\,a\,$ above since $\,a^{\large e}\equiv 1,\ e> 0\,\Rightarrow\,$ $a$ is invertible by $\,a a^{\large e-1}\equiv 1\,$ so $\,a^{\large -1}\equiv a^{\large e-1}$.
No comments:
Post a Comment