Solution to puzzle 128: Modular equation

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

---

Hence, for relatively prime integers m and n, x⁴⁹ x (modulo mn) x⁴⁹ x (modulo m) and x⁴⁹ 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⁴⁹ x (modulo p^r), for some prime p, and r 1.
If x⁴⁹ x (modulo p^r) and r > 1, then (p^r−1)⁴⁹ (p^r/p)⁴⁹ (0/p)⁴⁹ 0 (mod p^r).
But we also have (p^r−1)⁴⁹ 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⁴⁹ x (mod p), or, equivalently for our purposes, x⁴⁸ 1 (mod p).
By Fermat's Little Theorem, if (p − 1) divides 48, then x⁴⁸ 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⁴⁹ 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⁴⁹ x (mod p).
For example, 2⁴⁹ − 2 = 562949953421310 = 2 × 3² × 5 × 7 × 13 × 17 × 97 × 241 × 257 × 673.  (See Dario Alpern's Factorization Engine.)
Hence 2²⁴¹ 2, modulo 97, 241, 257, or 673.
However, if we also consider 5⁴⁹ − 5 = 17763568394002504646778106689453120 = 2⁶ × 3² × 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⁴⁹ x (mod p) for all integers x.

Thus, the numbers n for which x⁴⁹ 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⁴⁹ x (modulo n) is true for all integers x, is 2⁶ − 1 = 63.

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

Back to top