1999 JBMO Problems/Problem 2
Revision as of 12: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 |