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)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

For each nonnegative integer $n$ we define $A_n = 2^{3n}+3^{6n+2}+5^{6n+2}$. Find the greatest common divisor of the numbers $A_0,A_1,\ldots, A_{1999}$.

Solution

Note that $A_0 = 2^0 + 3^2 + 5^2 = 35$, so the GCD must be a factor of 35. The prime factorization of $35$ is $5 \cdot 7$, so we need to check if $5$ and $7$ are factors of the rest of the numbers.


Note that $A_1 = 2^3 + 3^8 + 5^8$. Taking both sides modulo 5 yields $A_1 \equiv 2^3 + 3^8 \equiv 4 \pmod{5}$, and taking both sides modulo 7 yields $A_1 \equiv 1 + 3^8 + 5^8 \equiv 1+2+4 \equiv 0 \pmod{7}$. That means $5$ couldn't be the GCD, but $7$ could be the GCD.


To confirm that $7$ is the GCD of the 2000 numbers, note that by Euler's Totient Theorem, $3^6 \equiv 5^6 \equiv 1 \pmod{7}$. That means $3^{6n+2} \equiv (3^6)^n \cdot 3^2 \equiv 2 \pmod{7}$ and $5^{6n+2} \equiv (5^6)^n \cdot 5^2 \equiv 4 \pmod{7}$. Also, since $2^3 \equiv 1 \pmod{7}$, we have $2^{3n} \equiv (2^3)^n \equiv 1 \pmod{7}$. Thus, $2^{3n} + 3^{6n+2} + 5^{6n+2} \equiv 1+2+4 \equiv 0 \pmod{7}$, making $A_n$ a multiple of 7.


In summary, the greatest common divisor of the numbers $A_0,A_1,\ldots, A_{1999}$ is $\boxed{7}$.

See Also

1999 JBMO (ProblemsResources)
Preceded by
Problem 1
Followed by
Problem 3
1 2 3 4
All JBMO Problems and Solutions