1
$\begingroup$

If $p$ is a prime number and a is a positive integer, show that $$ a^{(p-1)!+1} \equiv a\pmod{p}$$ I think Wilson's theorem might related to this problem because $(p-1)!+1$ is similar to $ (p-1)! \equiv -1 \pmod{p}$.

Can anyone can give a hint or some part of proof for this problem?

$\endgroup$
  • $\begingroup$ Wilson's theorem is not relevant in any obvious way, since you care about the exponent mod $p-1$, not mod $p$. $\endgroup$ – Eric Wofsey Sep 21 '16 at 8:28
  • $\begingroup$ If $p$ does not divide $a$, then this follows directly from Fermat's little theorem (or the more general Euler's theorem), since as you've mentioned, you can rewrite $(p-1)!+1$ as $kp$ for some $k\in\mathbb{N}$. $\endgroup$ – barak manos Sep 21 '16 at 8:48
3
$\begingroup$

Hint: Use Fermat's little theorem. In particular, if $a$ is not divisible by $p$, what can you say about $a^{(p-1)!}$?

$\endgroup$
1
$\begingroup$

Here is a funny variation :

The first case $p\mid a$ is trivial (look at @fleabood argument).

For the second case $p\not \mid a$ we will prove this statement :

Let $k,l$ two integers and $u$ an integer such that $p\not \mid u$. If $k\equiv l \ [p-1]$ then $u^k\equiv u^l\ [p].$

To prove this : we traduce the first congruence. It means that there exists $x\in \mathbb{Z}$ such that $(p-1)x+l=k$.

Then we can say that $u^k=u^{(p-1)x+l}=(u^{(p-1)})^{x}u^l$. By applying Fermat little theorem we have finally that : $u^{k}\equiv u^l \ [p]$.

Now we can apply the statement to : $a=u,k=(p-1)!+1$ and $l=1$ because $(p-1)!+1\equiv 1 \ [p-1]$ and it gives the final answer.

Remark : If we wanted to use the powerful Wilson's theorem we will have $(p-1)!+1\equiv 0 \ [p]$. But the previous statement is not sufficient. Indeed, in the last congruence, we will have $u^x$ which is totally unknown. If we suppose $p=k-l$, we will obtain $u^k\equiv u^{l+1} \ [p]$.

$\endgroup$
0
$\begingroup$

This is a very easy result gussied up to look hard.

Case 1: $p|a$

Then $a \equiv 0 \mod p$ and $a^N \equiv a \equiv 0 \mod p$ for any $N$.

Case 2: $p \not \mid a$ then as $p$ is prime $\gcd(a,p) = 1$

and $a^{p-1} \equiv 1 \mod p$ via Fermats Little Thereom.

So $a^{N(p-1) + 1} \equiv (a^{p-1})^Na \equiv a \mod p$ of any $N$ (including, but not limited to, $N = (p-2)!$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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