2022 USAJMO Problems/Problem 1

Problem

For which positive integers $m$ does there exist an infinite arithmetic sequence of integers $a_1,a_2,\cdots$ and an infinite geometric sequence of integers $g_1,g_2,\cdots$ satisfying the following properties?

$\bullet$ $a_n-g_n$ is divisible by $m$ for all integers $n>1$ ;

$\bullet$ $a_2-a_1$ is not divisible by $m$ .

Solution

Let the arithmetic sequence be $\{ a, a+d, a+2d, \dots \}$ and the geometric sequence to be $\{ g, gr, gr^2, \dots \}$ . Rewriting the problem based on our new terminology, we want to find all positive integers $m$ such that there exist integers $a,d,r$ with $m \nmid d$ and $m|a+(n-1)d-gr^{n-1}$ for all integers $n>1$ .

Note that $m | a+nd-gr^n \; (1),$ $m | a+(n+1)d-gr^{n+1} \; (2),$ $m | a+(n+2)d-gr^{n+2} \; (3),$

for all integers $n\ge 1$ . From (1) and (2), we have $m | d-gr^{n+1}+gr^n$ and from (2) and (3), we have $m | d-gr^{n+2}+gr^{n+1}$ . Reinterpreting both equations,

$m | gr^{n+1}-gr^n-d \; (4),$ $m | gr^{n+2}-gr^{n+1}-d \; (5),$

for all integers $n\ge 1$ . Thus, $m | gr^k - 2gr^{k+1} + gr^{k+2} = gr^k(r-1)^2 \; (6)$ . Note that if $m|g,r$ , then $m|gr^{n+1}-gr^n$ , which, plugged into (4), yields $m|d$ , which is invalid. Also, note that (4) $+$ (5) gives

$m | gr(r-1)(r+1) - 2d \; (7),$

so if $r \equiv \pm 1 \pmod m$ or $gr \equiv 0 \pmod m$ , then $m|d$ , which is also invalid. Thus, according to (6), $m|g(r-1)^2$ , with $m \nmid g,r$ . Also from (7) is that $m \nmid g(r-1)$ .

Finally, we can conclude that the only $m$ that will work are numbers in the form of $xy^2$ , other than $1$ , for integers $x,y$ ( $x$ and $y$ can be equal), ie. $4,8,9,12,16,18,20,24,25,\dots$ .

~sml1809

Solution 1

$m$ satisfies the conditions precisely when $m$ is not squarefree.

Consider three consecutive terms of the arithmetic sequence modulo $m$ : $x - d$ , $x$ , and $x + d$ . To satisfy the given conditions, the arithmetic and geometric sequences must match modulo $m$ . Thus, $(x - d)(x + d) \equiv x^2 \pmod{m}$ which simplifies to $x^2 - d^2 \equiv x^2 \pmod{m} \implies d^2 \equiv 0 \pmod{m}.$

If $m$ is squarefree, the congruence $d^2 \equiv 0 \pmod{m}$ implies $m \mid d$ , so the conditions are not satisfied. Thus, no solution exists for squarefree $m$ , and it remains for us to construct a solution for all other values of $m$ that are not squarefree.

Suppose $m$ is divisible by some prime square $p^2$ . Consider the arithmetic sequence $1,\quad 1 + \frac{m}{p},\quad 1 + 2\frac{m}{p},\quad \dots$ and the geometric sequence $1,\quad 1 + \frac{m}{p},\quad \left(1 + \frac{m}{p}\right)^2,\quad \dots$ For the geometric sequence, the first two terms in the binomial expansion of each entry match the corresponding terms in the arithmetic sequence and subsequent terms are 0 mod m because $\frac{m}{p}$ raised to a power greater than 1 contains enough $p$ 's in its factorization to ensure that it is a multiple of $m$ . Therefore the construction works and as originally stated, solutions exist precisely when $m$ is not squarefree.

2022 USAJMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2022 USAJMO Problems/Problem 1

Contents

Problem

Solution

Solution 1

See Also