# Solution to puzzle 128: Modular equation

For how many integers n > 1 is x49 x (modulo n) true for all integers x?

## Lemma

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).

### Proof

• 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, x49 x (modulo mn) x49 x (modulo m) and x49 x (modulo n), and we need only consider congruences modulo a prime or a power of a prime.

Now suppose, for all integers x, x49 x (modulo pr), for some prime p, and r 1.
If x49 x (modulo pr) and r > 1, then (pr−1)49 (pr/p)49 (0/p)49 0 (mod pr).
But we also have (pr−1)49 pr−1 (mod pr), which does not equal 0 (mod pr).
We have reached a contradiction, and conclude that r > 1 is impossible.

Now consider x49 x (mod p), or, equivalently for our purposes, x48 1 (mod p).
By Fermat's Little Theorem, if (p − 1) divides 48, then x48 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, x49 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 x49 x (mod p).
For example, 249 − 2 = 562949953421310 = 2 × 32 × 5 × 7 × 13 × 17 × 97 × 241 × 257 × 673.  (See Dario Alpern's Factorization Engine.)
Hence 2241 2, modulo 97, 241, 257, or 673.
However, if we also consider 549 − 5 = 17763568394002504646778106689453120 = 26 × 32 × 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 x49 x (mod p) for all integers x.

Thus, the numbers n for which x49 x (modulo n) for all integers x, are products of the form 2a × 3b × 5c × 7d × 13e × 17f, 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 x49 x (modulo n) is true for all integers x, is 26 − 1 = 63.

Source: Problem of the Week, No. 5 (Spring 2003 Series)