For how many integers n > 1 is x^{49} x (modulo n) true for all integers x?

For any integers a and b, and relatively prime integers m and n, a b (modulo mn) a b (modulo m) and a b (modulo n).

- a b (modulo mn) a − b = k(mn) for some integer k a − b = (kn)m and a − b = (km)n a b (modulo m) and a b (modulo n).
- a b (modulo m) and a b (modulo n) both m and n divide a − b, in which case so does mn since a and b are relatively prime.

Hence, for relatively prime integers m and n, x^{49} x (modulo mn) x^{49} x (modulo m) and x^{49} x (modulo n), and we need only consider congruences modulo a prime or a power of a prime.

Now suppose, for all integers x, x^{49} x (modulo p^{r}), for some prime p, and r 1.

If x^{49} x (modulo p^{r}) and r > 1, then (p^{r−1})^{49} (p^{r}/p)^{49} (0/p)^{49} 0 (mod p^{r}).

But we also have (p^{r−1})^{49} p^{r−1} (mod p^{r}), which does not equal 0 (mod p^{r}).

We have reached a contradiction, and conclude that r > 1 is impossible.

Now consider x^{49} x (mod p), or, equivalently for our purposes, x^{48} 1 (mod p).

By Fermat's Little Theorem, if (p − 1) divides 48, then x^{48} 1 (mod p).

The divisors of 48 are: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48; those of the form p − 1 are: 1, 2, 4, 6, 12, 16.

Thus, x^{49} x (mod p) for p = 2, 3, 5, 7, 13, or 17.

Fermat's Little Theorem gives us the above primes, but there may be *other* primes for which x^{49} x (mod p).

For example, 2^{49} − 2 = 562949953421310 = 2 × 3^{2} × 5 × 7 × 13 × 17 × 97 × 241 × 257 × 673. (See Dario Alpern's Factorization Engine.)

Hence 2^{241} 2, modulo 97, 241, 257, or 673.

However, if we also consider 5^{49} − 5 = 17763568394002504646778106689453120 = 2^{6} × 3^{2} × 5 × 7 × 13 × 17 × 31 × 313 × 601 × 11489 × 390001 × 152587500001, we see that only the primes p = 2, 3, 5, 7, 13, 17 occur in *both* factorizations, and hence can satisfy x^{49} x (mod p) for all integers x.

Thus, the numbers n for which x^{49} x (modulo n) for all integers x, are products of the form 2^{a} × 3^{b} × 5^{c} × 7^{d} × 13^{e} × 17^{f}, where each index is 0 or 1, and not all six indices are equal to 0.

Therefore, the number of integers n > 1 for which x^{49} x (modulo n) is true for all integers x, is 2^{6} − 1 = 63.