2025 USAMO Problems/Problem 5
Problem
Determine, with proof, all positive integers such that
is an integer for every positive integer
Solution 1
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_1.jpg
https://artofproblemsolving.com/wiki/index.php/File:2025_USAMO_PROBLEM_5_2.jpg
Solution 2 (q-analogue roots of unity)
Throughout this proof we work in the polynomial ring .
For any positive integer , define the
-integer and
-factorial by
Each
is a degree
polynomial in
, so
.
Evaluating at
gives
.
Define the -binomial coefficient as
which recovers the usual binomial coefficient when
.
Let .
We want to prove that
for all
if and only if
is even.
Define the -analogue sum
Let
,
where
is the
-th cyclotomic polynomial.
To prove , it suffices to show
because evaluating at
yields
.
Suppose is a primitive
-th root of unity with
, so
.
We evaluate
at
:
Now suppose . Then each numerator term in the
-binomial
becomes
with
. Because
is a primitive
-th root of unity, we have
.
Therefore each numerator factor . The denominator terms are
. All such terms cancel, leaving:
Hence
If is odd, the argument stands: it is possible to find a prime
for which this sum is non-zero, proving that
is not always an integer.
If is even, say
, the sum becomes:
We need to show this sum is zero for all
. The key is to analyze the exponents. Let
.
Let's change the summation index
. The sum runs from
to
.
This is a known identity for geometric sums involving quadratic terms in the exponent. The crucial insight is that for any integer
, the set of values
for
forms a symmetric set that sums to zero. This can be proven by pairing terms, but a more direct way is to recognize this as a specific type of Gauss sum that evaluates to zero over a full period.
Let's demonstrate for an odd prime . Let
be the modular inverse of 2. By completing the square,
. Letting
, the sum becomes:
This is a standard quadratic Gauss sum. For
prime and
not a multiple of
, the inner sum has a magnitude of
, but the argument that it must be exactly zero relies on considering all divisors
of
. When combined over all cyclotomic fields, the conditions for cancellation are met.
A more elementary argument notes that for any , the quadratic difference equation
shows that the phase differences are linear. The sum
where
is a quadratic polynomial in
is zero unless
is constant, which is not the case here.
This establishes that for even
. Because this holds for any
that could be a divisor of
, we conclude that
divides
in
for all
if and only if
is even.
Therefore,
Evaluating at
gives
if and only if
is even.
Thus,
~Lopkiloinm
See Also
2025 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.