5

Suppose $(a,b)=1$. Let $d=(2a+b,a+2b)$.

Then $d=(2a+b)u+(a+2b)v=a(2u+v)+b(2v+u)$ where $u,v \in \mathbb{Z}$.

Since $(a,b)=1$, then $a(2u+v)+b(2v+u)=1$.

I'm not sure if I'm going in the right direction to solve this problem.

Martin Sleziak
  • 53,687
emka
  • 6,494

4 Answers4

9

Hint:

Let $d=(a+2b,2a+b)$, so $d|3a$ since $d|2(2a+b)-(a+2b)$ and $d|3b$ since $d|2(a+2b)-(2a+b)$.

Therefore $d|(3a,3b)$.

user84413
  • 27,211
  • I'm stuck trying to figure out how to compute $2(2a+b)-(a+2b)$. I may be applying the Euclidean algorithm incorrectly...or are you eyeballing it? – emka Jan 24 '14 at 01:45
  • Note: $, 3a = 2(2a+b)-(a+2b) = 2A-B,$ can be discovered algorithmically by inverting the linear map - see my answer (where $a,b$ are written $x,y)$. – Bill Dubuque Jan 24 '14 at 01:51
  • @nhru if $d|a+2b$ then $d|-(a+2b)$ and if $d|2a+b$ then $d|2(2a+b)$ . By the comments you can infer now that $d|2(2a+b)-(a+2b)$. – taue2pi Jan 24 '14 at 02:14
5

Hint $\ $ Specialize the method below: $\rm\,(x,y)\mapsto (2x+y,x+2y) =: (X,Y)\,$ has $\, \det = 3,\,$ i.e.

$\qquad\begin{pmatrix} 2 & \rm 1 \\\\ \rm 1 & \rm 2 \end{pmatrix}\ \begin{pmatrix} x \\\\ \rm y \end{pmatrix}\ =\ \begin{pmatrix} X \\\\ \rm Y\end{pmatrix}\ \ \ \Rightarrow\ \ \ \begin{array} \rm\ 3\ x\ \ \ =\ \ \ \rm 2\ X \ - \ Y \\\\ \rm 3\ y\ =\ \rm\ - X + 2\ Y \end{array} $

Theorem $\ $ If $\rm\,(x,y)\overset{A}\mapsto (X,Y)\,$ is linear then $\: \rm\gcd(x,y)\mid \gcd(X,Y)\mid \Delta \gcd(x,y),\,\ \Delta = \det A$

Proof $\ $ Inverting the linear map $\rm\,A\,$ by Cramer's Rule (multiplying by the adjugate) yields

$$\rm \begin{eqnarray} a\ x\, +\, b\ y &=&\rm X\\ \\ \rm c\ x\, +\, d\ y &\ =\ &\rm Y\end{eqnarray} \quad\Rightarrow\quad \begin{array} \rm\Delta\ x\ \ \ =\ \ \ \rm d\ X\, -\, b\ Y \\\\ \rm\Delta\ y\ =\ \rm -c\ X\, +\, a\ Y \end{array}\ ,\quad\ \Delta\ =\ ad-bc\qquad $$

Hence, by RHS system, $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\:x,\:\Delta\:y\ \Rightarrow\ n\ |\ gcd(\Delta\:x,\Delta\:y)\ =\ \Delta\ gcd(x,y)\:.$
In particular $\rm\ n = \gcd(X,Y) \mid \Delta\, \gcd(x,y).\ $

Further, by LHS system $\rm\,n\mid x,y\ \Rightarrow\ n\mid X,Y\ \Rightarrow\ n\mid\gcd(X,Y).$
In particular $\rm\ n = gcd(x,y)\mid \gcd(X,Y).\ \ \ $ QED

Bill Dubuque
  • 272,048
  • I haven't seen using determinant here, could you explain how the determinant is 3? or what is the matrix that you are taking the determinant of? –  Jan 24 '14 at 01:10
  • @Wishingwell I added further details. – Bill Dubuque Jan 24 '14 at 01:39
  • This answer might also be related to Smith normal form: the hypothesis implies that the map $\begin{bmatrix} a & b \end{bmatrix} : \mathbb{Z}^2 \to \mathbb{Z}$ is surjective, and then we want to know something about the image of $\begin{bmatrix} a & b \end{bmatrix} \begin{bmatrix} 2 & 1 \ 1 & 2 \end{bmatrix}$. By writing $A = \begin{bmatrix} 2 & 1 \ 1 & 2 \end{bmatrix}$ in the form $P D Q$ where $P, Q \in SL_2(\mathbb{Z})$ and $D$ is diagonal, we can conclude the image of $x^t A$ equals the image of $x^t P D$; and there's an obvious relation between the entries of $D$ and $\det A = \det D$. – Daniel Schepler Jul 09 '20 at 21:00
2

Direct manipulation of gcd

$\gcd(a+2b,2a+b) = \gcd(a+2b,(2a+b)-2(a+2b)) = \gcd(a+2b,-3b)$

$ | \gcd(a+2b,3) \gcd(a+2b,b) | 3 \gcd((a+2b)-2(b),b) = 3 \gcd(a,b) = 3$

user21820
  • 57,693
  • 9
  • 98
  • 256
1

Let $$d=\gcd(a+2b, 2a+b).$$ $$\Rightarrow d|a+2b, d|2a+b.$$ $$\rightarrow d|2(a+2b), d| 2a+b.$$ Now use this result that if $d=\gcd(a, b), d|a, d|b\ \text{then}\ d|a\pm b$. So, $$d|2a+4b-2a-b.$$ $$\Rightarrow d|3b.$$ Also $$\Rightarrow d|3a.$$ $$\therefore d|(3a, 3b) \Rightarrow d= 1\ \text{or} \ 3. (\because (a, b)=1.)$$

Kns
  • 3,165