1999 JBMO Problems/Problem 2

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}$ .

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

Page

Toolbox

Search

1999 JBMO Problems/Problem 2

Problem

Solution

See Also