2016 USAMO Problems/Problem 2
Problem
Prove that for any positive integer
is an integer.
Solution
Define for all rational numbers
and primes
, where if
, then
, and
is the greatest power of
that divides
for integer
. Note that the expression(that we're trying to prove is an integer) is clearly rational, call it
.
, by Legendre. Clearly,
, and
, where
is the remainder function(we take out groups of
until there are less than
left, then we have
distinct values, which the minimum is attained at
to
). Thus,
, as the term in each summand is a sum of floors also and is clearly an integer.
See also
2016 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |