Maths Olympiad Prep

Library / Saudi Arabian Mathematical Competitions /129 of 395

Saudi Arabian Mathematical Competitions

Number theory Difficulty 5.3 AIME, harder Prove it Saudi Arabia

Find all integers nn, n≥2n \geq 2, such that the numbers 1!1!, 2!2!, …\ldots, (n−1)!(n-1)! give distinct remainders when divided by nn.

Solution

We claim that those integers are n=2n=2 and n=3n=3.

Suppose nn is a composite integer, n=abn=a b, 1<a≤b1<a \leq b. If a<ba<b, then n=abn=a b divides b!b! and (b+1)!(b+1)!. Since b<b+1<n−1b<b+1<n-1, it follows that b!b! and (b+1)!(b+1)! yield equal remainders (both 00) at division by nn. If 2<a=b2<a=b then (2a)!(2 a)! and (2a+1)!(2 a+1)! are divisible by n=a2n=a^{2}. Since 2a+1<a2−1=n−12 a+1<a^{2}-1=n-1, it follows that nn does not satisfy the desired property.

It remains to settle the case of prime nn. The value n=2n=2 checks; let then n≥3n \geq 3. From Wilson's theorem we have
(n−1)!≡−1( mod n) (n-1)!\equiv-1 \quad(\bmod n)
and then
(n−2)!≡1( mod n). (n-2)!\equiv 1 \quad(\bmod n) .
Since 1!=11!=1 yields remainder 11 at division by nn, it follows n−2=1n-2=1, that is n=3n=3, which checks.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.