1999 JBMO Problems/Problem 2
For each nonnegative integer we define . Find the greatest common divisor of the numbers .
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 .
|1999 JBMO (Problems • Resources)|
|1 • 2 • 3 • 4|
|All JBMO Problems and Solutions|