Maths Olympiad Prep

Library / /57 of 120

Number theory Difficulty 5.3 AIME, harder Prove it Saudi Arabia

Find all integers nn, n2n \geq 2, such that the numbers 1!1!, 2!2!, \ldots, (n1)!(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<ab1<a \leq b. If a<ba<b, then n=abn=a b divides b!b! and (b+1)!(b+1)!. Since b<b+1<n1b<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<a21=n12 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 n3n \geq 3. From Wilson's theorem we have
(n1)!1(modn) (n-1)!\equiv-1 \quad(\bmod n)
and then
(n2)!1(modn). (n-2)!\equiv 1 \quad(\bmod n) .
Since 1!=11!=1 yields remainder 11 at division by nn, it follows n2=1n-2=1, that is n=3n=3, which checks.

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

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.