Find the greatest common divisor of $8^{10}+12$ and $8^5$ without a calculator.

Question

Find the greatest common divisor of $8^{10} + 12$ and $8^5$

I found the answer using a rather silly method:

I found the GCD of the two numbers by finding the GCD of all the three numbers $8^{10}$, $12$ and $8^5$. Which is $4$.

I feel like there is a more proper way to do it: however, the only other method I could think of is the Euclidean algorithm.

$(8^{10} + 12) ÷ 8^5 = 8^5$ with a remainder of $12$

$8^5 ÷ 12 =\dots$

I am sure I am not suppose to use this algorithm, since I am not allowed to use any calculators.

Answer 1

Since $8^5$ is a factor of $8^{10}$, using the euclidean algorithm,

$$\begin{align} gcd (8^{10} + 12, 8^5) &= gcd (mod(8^{10} + 12, 8^5), 8^5) \\ &= \cdots\end{align}$$

Answer 2

If $d$ divides both $8^{10}+12$ and $8^5$, then $d$ also divides every linear combination of these two, so $$d \mid (8^{10}+12)-8^{5}*8^{5} = 12 $$ So $d$ divides $12$. But $d$ must be a power of $2$ (why?) so $d$ divides $4$. Now you can check that $d=4$ is actually a common divisor.

Answer 3

$d\mid 8^5 \land d\mid 8^{10}+12 \implies d\mid 12 \implies d=4$

Answer 4

Calculators are not allowed, but pen-and-paper arithmetic is allowed, right? $$8^{10}+12=8^5\cdot8^5+12,\text{ so }\gcd(8^{10}+12,8^5)=\gcd(8^5,12)=\gcd(2^{15},12)=\gcd(32768,12)$$ $$32768=12\cdot2730+8$$ $$12=8\cdot1+4$$ $$8=4\cdot2+0$$ $$\gcd(8^{10}+12,8^5)=4$$

Answer 5

You can in fact use the Euclidean algorithm, with only mental arithmetic, as follows

$$\begin{eqnarray} (8^{10}\!+12,\, 8^5)\ &=& (12,\,8^5)\ \ \ {\rm by}\ \ \ 8^{10}\!+12\equiv 12 \pmod{8^5}\\ &=& 4\,(3,\,2\cdot 8^4)\\ &=& 4 \end{eqnarray}$$