Maths Olympiad Prep

Library / HMMT February /770 of 1302

HMMT February

Number theory Difficulty 5.3 AIME, harder Find the answer

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.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

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 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\operatorname{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∣n2 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: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.