$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

Question

I seem to have found that:

$$k | x^{k} - x, \ \text{for} \ k, x \in \mathbb{Z}.$$

I have tried it with a few values, and it seems to be true.

I am sure that this has been discovered before.

Ah, I have independently discovered Fermat's little theorem... xD — Taylor, Jul 21 '15 at 13:59
@DietrichBurde If you write this as an answer, I would be more than happy to accept it! — Taylor, Jul 21 '15 at 14:00
@GFauxPas I am trying to express that both $k$ and $x$ are elements of the set $\mathbb{Z}.$ — Taylor, Jul 21 '15 at 14:01

score 2 · Accepted Answer · answered Jul 21 '15 at 14:01

2

In fact, it does not work for all $k, x \in \mathbb{Z}$. Consider $k = 4, x = 2$: $4$ does not divide $2^4 - 2 = 16 - 2 = 14$.

However, this works if $k$ is prime, and is well-known Fermat's little theorem.

answered Jul 21 '15 at 14:01

lisyarus

15,517

Thank you very much for a great answer! – Taylor Jul 21 '15 at 14:01

score 1 · Answer 2 · edited Aug 18 '19 at 17:32

1

Your result only works for all $x$ if $k$ is a prime or a Carmichael number, and it is known as Fermat's little theorem for prime numbers.

But there are more general results known. In rewritten form, the Euler-Fermat theorem states that $$k|x^{\varphi(k)+1}-x$$ if $\gcd(x,k)=1$, and here we have $\varphi(k)$ as the Euler-phi function, equal to $k-1$ if $k$ is prime.

edited Aug 18 '19 at 17:32

darij grinberg

17,777

answered Jul 21 '15 at 14:14

wythagoras

25,026

$k | x^{k} - x,$ for $k, x \in \mathbb{Z}$?

2 Answers2