1999 JBMO Problems/Problem 2
Revision as of 13:30, 25 August 2018 by Rockmanex3 (talk | contribs) (Solution to Problem 2 -- GCD with modular arithmetic)
Problem
For each nonnegative integer we define
. Find the greatest common divisor of the numbers
.
Solution
Note that , so the GCD must be a factor of 35. The prime factorization of
is
, so we need to check if
and
are factors of the rest of the numbers.
Note that . Taking both sides modulo 5 yields
, and taking both sides modulo 7 yields
. That means
couldn't be the GCD, but
could be the GCD.
To confirm that is the GCD of the 2000 numbers, note that by Euler's Totient Theorem,
. That means
and
. Also, since
, we have
. Thus,
, making
a multiple of 7.
In summary, the greatest common divisor of the numbers is
.
See Also
1999 JBMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 | ||
All JBMO Problems and Solutions |