NumberthonNumberthon

SolveFire POTW

Bronze
number_theory
5/25/2026
Problems sourced from solvefire.net
Problem
Let SS be the set of positive integers n<2026n<2026 such that n∣2n+1n\mid2^n+1. Find the remainder when the sum of all elements of SS is divided by 1000.
Solution ApproachShow

Step-by-step approach

If n∣2n+1n\mid2^n+1 then 2n≡−1(modn)2^n\equiv-1\pmod n. In particular 22n≡1(modn)2^{2n}\equiv1\pmod n. So ordp(2)∣2n\text{ord}_p(2)\mid2n but ∤n\nmid n for each prime p∣np\mid n. This means ordp(2)\text{ord}_p(2) is even with v2(ordp(2))>v2(n)v_2(\text{ord}_p(2))>v_2(n)... Enumerate valid nn: n=1n=1 works (1∣31\mid3). Check small odd values and products.

Ready for more competition problems?

Practice the full SolveFire course and compete in ranked math battles — free to play.