Maths Olympiad Prep

Library / /951 of 1394

, 2024

Number theory Difficulty 5.4 AIME, harder Prove it United States

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

Solution

Solution:
We claim that if n10n \geq 10, then 2n+32n!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+32n!12 n+3 \mid 2^{n!}-1. By Fermat's Little Theorem, 2n+322n+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+3221=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+2n!2 n+2 \mid n!, so 2n+32n!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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.