Maths Olympiad Prep

Library / /10 of 22

Number theory Difficulty 5.6 AIME, harder Prove it Turkey

Find all positive integers nn satisfying 2n+7n!12n + 7 \mid n! - 1.

Solution

The answer is 11, 55 and 88.

Checking by hand for n=1,2,,6n = 1, 2, \ldots, 6, we see that 11 and 55 work. For n7n \ge 7, 2n+72n + 7 should be a prime number. Because, otherwise there exists a prime divisor of 2n+72n + 7 which is less than or equal to nn since 2n+72n + 7 is odd, but it divides n!n!.

Now let 2n+7=p212n + 7 = p \ge 21 where pp is a prime number. Then the condition is equivalent to (p72)!1(modp)\left(\frac{p-7}{2}\right)! \equiv 1 \pmod{p}. Wilson's theorem gives that (p1)!1(modp)(p-1)! \equiv -1 \pmod{p}. On the other hand
(p1)!(1)p72(p72)!2p52p32p12p+12p+32p+52(1)p1222564(modp) (p-1)! \equiv (-1)^{\frac{p-7}{2}} \cdot \left(\frac{p-7}{2}\right)!^2 \cdot \frac{p-5}{2} \cdot \frac{p-3}{2} \cdot \frac{p-1}{2} \cdot \frac{p+1}{2} \cdot \frac{p+3}{2} \cdot \frac{p+5}{2} \equiv (-1)^{\frac{p-1}{2}} \frac{225}{64} \pmod{p}
Thus we obtain 225(1)p+1264(modp). \text{Thus we obtain } 225 \equiv (-1)^{\frac{p+1}{2}} 64 \pmod{p}.
If p1(mod4)p \equiv 1 \pmod{4}, then p225+64=172p \mid 225 + 64 = 17^2 but p21p \ge 21, no solution exists.
If p3(mod4)p \equiv 3 \pmod{4}, then p22564=723p \mid 225 - 64 = 7 \cdot 23. As p21p \ge 21 we have p=23p = 23, that is n=8n = 8 and it satisfies the condition.

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.