Maths Olympiad Prep

Library / HMMT February /887 of 1302

HMMT February, 2024

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:
Compute the sum of all positive integers nn such that 50≤n≤10050 \leq n \leq 100 and 2n+32 n+3 does not divide 2n!−12^{n!}-1.

Solution

Solution:
We claim that if n≥10n \geq 10, then 2n+3∤2n!−12 n+3 \nmid 2^{n!}-1 if and only if both n+1n+1 and 2n+32 n+3 are prime.

If both n+1n+1 and 2n+32 n+3 are prime, then assume 2n+3∣2n!−12 n+3 \mid 2^{n!}-1. By Fermat's Little Theorem, 2n+3∣22n+2+12 n+3 \mid 2^{2 n+2}+1. However, since n+1n+1 is prime, gcd⁡(2n+2,n!)=2\gcd(2 n+2, n!)=2, so 2n+3∣22−1=32 n+3 \mid 2^{2}-1=3, a contradiction.

If 2n+32 n+3 is composite, then φ(2n+3)\varphi(2 n+3) is even and is at most 2n2 n, so φ(2n+3)∣n!\varphi(2 n+3) \mid n!, done.

If n+1n+1 is composite but 2n+32 n+3 is prime, then 2n+2∣n!2 n+2 \mid n!, so 2n+3∣2n!−12 n+3 \mid 2^{n!}-1.

The prime numbers between 50 and 100 are 53,59,61,67,71,73,79,83,89,9753,59,61,67,71,73,79,83,89,97. If one of these is n+1n+1, then the only numbers that make 2n+32 n+3 prime are 53, 83, and 89, making nn one of 52, 82, and 88. These sum to 222.

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.