Skip to main content.

Solution to puzzle 128: Modular equation

Skip restatement of puzzle.For how many integers n > 1 is x49 congruent to x (modulo n) true for all integers x?


Lemma

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

Proof

Hence, for relatively prime integers m and n, x49 congruent to x (modulo mn) if and only if x49 congruent to x (modulo m) and x49 congruent to 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 congruent to x (modulo pr), for some prime p, and r greater than or equal to 1.
If x49 congruent to x (modulo pr) and r > 1, then (pr−1)49 congruent to (pr/p)49 congruent to (0/p)49 congruent to 0 (mod pr).
But we also have (pr−1)49 congruent to 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 congruent to x (mod p), or, equivalently for our purposes, x48 congruent to 1 (mod p).
By Fermat's Little Theorem, if (p − 1) divides 48, then x48 congruent to 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 congruent to 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 congruent to 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 congruent to 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 congruent to x (mod p) for all integers x.

Thus, the numbers n for which x49 congruent to 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 congruent to x (modulo n) is true for all integers x, is 26 − 1 = 63.

Source: (Adobe) Portable Document Format Problem of the Week, No. 5 (Spring 2003 Series)

Back to top