MathGoldMedalist

Sign In Register

← USAMO 2026 ← Problems

USAMO 2026 (Problem 6)

Let

a

and

b

be positive integers such that

\varphi(ab+1)

divides

a^2+b^2+1

. Prove that

a

and

b

are Fibonacci numbers.

Note: Euler's totient function

\varphi(n)

is the number of positive integers less than or equal to

n

that are relatively prime to

n

.

Assume

m=2

, so

n=ab+1=p^2

.

\varphi(ab+1)\mid a^2+b^2+1

\varphi(p^2)\mid a^2+b^2+1

p(p-1)\mid a^2+b^2+1.

ab+1=p^2\Longrightarrow ab\equiv-1\pmod p.

a^2+b^2+1\equiv0\pmod p.

Multiply by

a^2

:

a^4+a^2b^2+a^2\equiv0\pmod p

a^4+(-1)^2+a^2\equiv0\pmod p

a^4+a^2+1\equiv0\pmod p.\qquad(2)

(a^2-1)(a^4+a^2+1)\equiv0\pmod p

a^6-1\equiv0\pmod p

a^6\equiv1\pmod p.

Let

d=\operatorname{ord}_p(a)

. Then

d\mid 6

, so

d=1,2,3

, or

6

.

\phantom{\rule{0pt}{1pt}}

By Fermat's little theorem,

a^{p-1}\equiv1\pmod p.

So

d\mid p-1.

Case 1:

d=1

or

2

.By (2),

a^4+a^2+1\equiv0\pmod p

1+1+1\equiv0\pmod p

3\equiv0\pmod p

p\mid3\Longrightarrow p=3.

ab+1=3^2=9\Longrightarrow ab=8.

\Longrightarrow(a,b)=(1,8),(2,4)\quad\text{(up to order)}.

\varphi(ab+1)\mid a^2+b^2+1.

(a,b)=(1,8):\quad6=\varphi(9)\mid1^2+8^2+1=66\quad\checkmark

1=F_1,\qquad8=F_6.

(a,b)=(2,4):\quad6=\varphi(9)\nmid2^2+4^2+1=21\quad\times

Case 2:

d=3

or

6

.

d\mid p-1

3\mid p-1

p-1\mid a^2+b^2+1

3\mid a^2+b^2+1.\qquad(3)

ab=p^2-1=(p-1)(p+1)

3\mid ab

3\mid a\text{ or }3\mid b.

a^2+b^2+1\equiv1\text{ or }2\pmod3.

By (3),

a^2+b^2+1\equiv0\pmod3\quad\times