Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2025 USAJMO Problems/Problem 6

Problem

Let $S$ be a set of integers with the following properties:

$\bullet$ $\{ 1, 2, \dots, 2025 \} \subseteq S$.

$\bullet$ If $a, b \in S$ and $\gcd(a, b) = 1$, then $ab \in S$.

$\bullet$ If for some $s \in S$, $s + 1$ is composite, then all positive divisors of $s + 1$ are in $S$.

Prove that $S$ contains all positive integers.

Solution 1

We will show that if $\{1, 2, 3, \dots, n\}\in S$, then $n+1\in S$. Note that if $n+1$ is composite, we are done, so we assume that $n+1$ is an odd prime.

Case 1: $n+1\ne 2^k\pm 1$ for some integer $k>2$. Since $n+2\ne 2^k$, we have that $2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\le n\implies 2^{v_2 (n+2)}, \frac{n+2}{2^{v_2 (n+2)}}\in S\implies n+2\in S$. Either $v_2(n)=1$ or $v_2(n+2)=1$, so $2^{v_2(n)+v_2(n+2)}=2^{1+\max(v_2(n), v_2(n+2))}=2\cdot 2^{\max(v_2(n), v_2(n+2))}\le 2\cdot \frac{n+2}{3}\le n\implies 2^{v_2(n)+v_2(n+2)}\in S$. Since $\gcd(n, n+2)=2$, we have that $\gcd\left(\frac{n}{2^{v_2(n)}}, \frac{n+2}{2^{v_2(n+2)}}\right)=1$, so \[2^{v_2(n)+v_2(n+2)}\cdot \frac{n}{2^{v_2(n)}}\cdot \frac{n+2}{2^{v_2(n+2)}}=n(n+2)\in S\implies n(n+2)+1=(n+1)^2\in S\implies n+1\in S.\]

Case 2: $n+1=2^k+1$ for some integer $k>2$. Note that $k$ must be even, otherwise $2^k+1\equiv 0\pmod 3$. Then we have the following: \[\left(2^{\frac{k}{2}}+1\right)^2-1=2^{\frac{k}{2}}\left(2^{\frac{k}{2}}+2\right)=2^{\frac{k}{2}+1}\left(2^{\frac{k}{2}-1}+1\right)\in S \implies\left(2^{\frac{k}{2}}+1\right)^2\in S\] \[\implies 2^{\frac{k}{2}-1}\left(2^{\frac{k}{2}}+1\right)^2 = \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)-1\in S\implies \left(2^{\frac{k}{2}-1}+1\right)\left(2^k+1\right)\in S\implies 2^k+1\in S,\] as desired.

Case 3: $n+1=2^k-1$ for some integer $k>2$. Let $x<k$ be a positive integer. Then \[(2^x-1)(2^k-1)-1=2^x\left(2^k-2^{k-x}-1\right)\in S\implies 2^k-1\in S,\] as desired.

Hence, since $\{1, 2, 3, \dots, n\}\in S\implies n+1\in S$, the set $S$ spans all positive integers.

-mop

See Also

2025 USAJMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_USAJMO_Problems/Problem_6&oldid=245836"