-1

Find $\gcd(3^{20} + 3, 3^{21} +6)$

I am honestly so confused, I know $3$ divides both terms but am unsure if that's the $\gcd$.

Asaf Karagila
  • 393,674
  • 8
    $3\cdot(3^{20}+3)-(3^{21}+6)=?$ – egreg Nov 01 '18 at 13:08
  • 5
    Related to the first comment: $\gcd\left(a,b\right) = \gcd\left(a,b-a\right)$. – Sam Streeter Nov 01 '18 at 13:10
  • @egreg the answer to that is 3, but why did you multiply the first term by 3? –  Nov 01 '18 at 13:19
  • 1
    Do you know the Euclidean Algorithm? – Mark Bennet Nov 01 '18 at 13:22
  • 1
    Euclid's algorithm – Hagen von Eitzen Nov 01 '18 at 13:22
  • @MarkBennet not really, no –  Nov 01 '18 at 13:25
  • If $g\mid3^{20}+3$ and $g\mid3^{21}+6$, then $g\mid\left[3\left(3^{20}+3\right)-\left(3^{21}+6\right)\right]$; that is, $g\mid3$. – robjohn Nov 01 '18 at 13:26
  • That is something you should perhaps look up if you are dealing with several problems of the same kind - it is a systematic way of doing what may become obvious in a case like this. Here if $d$ is a factor of both $a$ and $b$ it is a factor of any linear combination of $a$ and $b$, so you take the combination which cancels out the high powers of $3$ to get a small number. Only the factors of that small number need then be considered. – Mark Bennet Nov 01 '18 at 13:44

2 Answers2

4

Hint: if $d$ divides $a$ and $b$, it also divides $pa+qb$, for every $p$ and $q$; thus the gcd will divide $$ 3(3^{20}+3)+(-1)(3^{21}+6) $$ Why $p=3$ and $q=-1$? Because doing so will remove the powers of $3$.

egreg
  • 238,574
0

Alternatively, without explicitly eliminating the powers of $3$

$\qquad \gcd(\underbrace{ 3^{20}\!+\!3}_{\large a},\, 3(\underbrace{3^{20}\!+\!2)}_{\large a\ -\ 1}) = \gcd(a,3(a\!-\!1)) = \gcd(a,3)=3,\,$ by $\,a,a\!-\!1$ coprime

Bill Dubuque
  • 272,048