Maths Olympiad Prep

Library / Team Selection Test for JBMO /9 of 20

Team Selection Test for JBMO

Number theory Difficulty 5.6 AIME, harder Prove it Turkey

Find all positive integers nn satisfying 2n+7∣n!−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 n≥7n \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=p≥212n + 7 = p \ge 21 where pp is a prime number. Then the condition is equivalent to (p−72)!≡1(modp)\left(\frac{p-7}{2}\right)! \equiv 1 \pmod{p}. Wilson's theorem gives that (p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod{p}. On the other hand
(p−1)!≡(−1)p−72⋅(p−72)!2⋅p−52⋅p−32⋅p−12⋅p+12⋅p+32⋅p+52≡(−1)p−1222564(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 p≡1(mod4)p \equiv 1 \pmod{4}, then p∣225+64=172p \mid 225 + 64 = 17^2 but p≥21p \ge 21, no solution exists.
If p≡3(mod4)p \equiv 3 \pmod{4}, then p∣225−64=7⋅23p \mid 225 - 64 = 7 \cdot 23. As p≥21p \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,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.