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}$. Romania
Problem
Source: JBMO 1999, Problem 2
Tags: modular arithmetic, number theory, greatest common divisor
31.10.2005 02:07
$A_0=35$, but $A_1$ is not a multiple of $5$ so it is either $7$ or $1$. Since $5^6=3^6=2^3=1 \pmod 7$, we have that $7$ divides every number so the gcd is $7$.
08.07.2012 22:51
26.05.2016 07:37
for n=0, we get A0=35. if n=1, we get A1=397194. so the greatest common divisor of A0, A1, A2,.....,A1000 is either 1 or 7, assume the answer is 7, so we will prove it. we know that 2^3n is equal to 8^n which is congruent to 1 mod 7, and 3^6n+2 is equal to 9^3n+1 which is congruent to 2^3n+1 mod 7, similarly we get 5^6n+2 is congruent to 4^3n+1 mod 7. we have 2^1 congruent to 2 mod 7, 2^2 is congruent to 4 mod 7, 2^3 is congruent 1 mod 7, 2^4 is conruent to 2 mod 7, etc. so 2^3n+1 will be congruent to 2 mod 7, analogously, we get 4^3n+1 will be congruent to 4 mod 7, so the answer is 7.
23.08.2019 03:53
Notice that $A_0=2^0+3^2+5^2=1+9+25=35.$ Then, the greatest common divisor must be one of the factors of $35,$ namely $1,5,7$ or $35.$ Next, notice that $A_1=2^3+3^8+5^8=8+3(3^7)+5(5^7)\equiv 8+3\cdot 3+5\cdot 5 \equiv 42\equiv 0 \mod 7.$ This means that $A_1$ is a multiple of $7.$ However, $A_1= 2^3+3^8+5^8\equiv 8+6561 \equiv 3+1=4\mod 5.$ As a result, since $5\nmid A_1,$ the greatest common divisor must not be a multiple of $5,$ so it needs to be $1$ or $7$ from before. Then, we will show that for all integers $n\ge 0,$ $7\mid A_n.$ Our base case is $A_0 =35\equiv 0 \mod 7,$ which we calculated before. Next, assume that $2^{3n}+3^{6n+2}+5^{6n+2}\equiv 0\mod 7.$ We then have\begin{align*}A_{n+1}&=2^{3(n+1)}+3^{6(n+1)+2}+5^{6(n+1)+2}\\ &=2^{3n+3}+3^{6n+8}+5^{6n+8}\\ &=2^{3n}2^3+3^{6n+2}3^6+5^{6n+2}5^6\end{align*}By FLT, $3^6\equiv 1 \mod 7$ and $5^6\equiv 1\mod 7.$ So, we then have \begin{align*}A_0&\equiv 2^{3n}(8)+3^{6n+2}(1)+5^{6n+2}(1)\\ &\equiv 2^{3n}+3^{6n+2}+5^{6n+2} \equiv 0 \mod 7.\end{align*}by our inductive hypothesis. So, $7\mid A_{n+1},$ meaning that $7$ divides all elements $A_n$ and so $\gcd(A_0,A_1,\dots, A_{1999})=7.$ $\square$
25.09.2024 17:29
A_0=5*7, A_1=2*3*7^3*193 -> gcd(A_0,A_1,...,A_1999)|7 A_n=2^3n+3^6n+2+5^6n+2 =0 (mod7) -> gcd(A_0.A_1,...,A_1999)=7