Maths Olympiad Prep

Library / /649 of 860

Number theory Difficulty 5.3 AIME, harder Find the answer

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.

A number or a short expression. Spacing and $ signs are ignored.

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 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\operatorname{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+2n2 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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.