0

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.

Community
  • 1
pradha
  • 1
  • "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$." Note that while in this case this method happens to give the correct answer, it is not generally so. Consider, for example, $\gcd(19+1,2)$. – JiK Dec 11 '14 at 11:07

5 Answers5

4

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.

Jef
  • 3,821
1

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

Bill Dubuque
  • 272,048
0

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

Thumbnail
  • 563
0

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

0

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

bof
  • 78,265
  • And for those who, like me, find that computing $2^{15}$ is too much effort, use $$\gcd(2^{15},12)=\gcd(4\cdot2^{13},4\cdot3)=4\cdot\gcd(2^{13},3^1)=4\cdot1,$$ which requires only to know that $2$ and $3$ are distinct primes. Or, even more directly, $$\gcd(2^a\cdot3^b,2^c\cdot3^d)=2^{\min(a,c)}\cdot3^{\min(b,d)}.$$ – Did Dec 11 '14 at 11:21
  • @Did Good one! But I'm sure every mathematician knows that many powers of $2$ by heart. Anyway there's a good mnemonic for $2^{15}$: subtract $1$ from the Fermat prime $65537$ and divide by $2$. – bof Dec 11 '14 at 11:31
  • You would be surprised (or maybe your remark is tongue-in-cheek?). :-) – Did Dec 11 '14 at 11:32