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
which are just permutations of numbers
to
until there are less than
left, then we have
distinct values, which the minimum sum 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 |