On prime numbers .

Question

For $$a\in \mathbb{Z}$$ and "$p"$ a positive prime:

And : Gcd(a:p)=1

Prove that :

$$\left( \forall k\in \mathbb{N} \right):a^{\left( p-1\right){p^{k}}}\equiv 1\mod p^{k+1}$$

Induction and Gauss tiny theorem ,I think I am close to solving it . — Nima Dible, May 24 '17 at 01:05
The theorem isn't true... take $a=2, p=3, k=1$. Then $a^{{p-1}^{p^k}} = 2^{2^3} = 256 \equiv 4 \pmod 9$ — SEWillB, May 24 '17 at 01:38
@NimaDible The exponent in your question is incorrect. It should be $(p-1)p^k$ but you have it written as $(p-1)^{p^k}$. For instance when $p=2$ the latter is equal to $1$ regardless of $k$, which is clearly false. For other primes it still makes a big difference. — Erick Wong, May 24 '17 at 01:38
There is indeed a simple proof by induction starting from Fermat's little theorem (is that what you mean by Gauss tiny theorem??). — Erick Wong, May 24 '17 at 01:50
Sorry for the misleading statement, I made all necessary changes and it's correct now . — Nima Dible, May 24 '17 at 12:50

score 3 · Accepted Answer · answered May 24 '17 at 01:40

If $\phi$ is Euler's totient function, we have $a^{\phi(n)}\equiv 1 \mod n$ by Euler's totient theorem.

If $n = p^{k+1}$ we have $\phi(p^{k+1}) = p^{k+1} - p^k = (p - 1)p^k$.

Using this we find that $a^{(p-1)p^k} \equiv 1 \mod p^{k+1}$, which is the identity I believe you actually meant, as mentioned in the comments.

1 Answers1