29
$\begingroup$

I want to show that for $\gcd(a,b) = 1$ $a,b \in Z$ $\gcd(a+b, a-b) = 1$ or $\gcd(a+b, a-b) = 2$ holds.

I think the first step should look something like this:

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

From here I tried to proceed with two cases.
1: $a-b$ is even, which leads to $\gcd(a+b, a-b) = 2$
2: $a-b$ is odd, which leads to $\gcd(a+b, a-b) = 1$

My main problem I think is, that I do not know how I should include $\gcd(a,b) = 1$ in the proof.

Any help is appreciated. Thx in advance.
Cherio Woltan

$\endgroup$
1
  • 1
    $\begingroup$ $x=(a-b,2b)=(a-b,2a)\,\Rightarrow\, x=(a-b,2(a,b))=(a-b,2)\mid 2$. $\endgroup$
    – user236182
    Sep 18, 2015 at 16:32

6 Answers 6

40
$\begingroup$

Let $d$ be a common divisor of $a+b$ and $a-b$, then $d$ divides their sum $2a$ and difference $2b$. If a number divides two numbers it also divides their gcd, thus $d$ divides $2\gcd(a,b) = 2$. That implies that every divisor (including the greatest common divisor) is a divisor of $2$.


The same argument again in symbols:

Let $d \mid a+b, a-b$, then $d \mid (a+b)+(a-b) = 2a$ and $d \mid (a+b)-(a-b) = 2b$ so $d \mid \gcd(2a,2b) = 2$.

$\endgroup$
1
  • $\begingroup$ Great! I had to think a little about your prove but hopefully now I got it. Thx again... $\endgroup$
    – Woltan
    Apr 13, 2011 at 13:02
16
$\begingroup$

Here's a computational proof, similar to the second proof quanta gave. Since $(x,y) = 1$, there are integers $a,b$ such that $ax+by = 1$. Therefore $$ (a+b)(x+y) + (a-b)(x-y) = 2ax + 2by = 2. $$ Thus $(x+y,x-y)\mid 2$.

$\endgroup$
1
13
$\begingroup$

Hint $\, \ \begin{vmatrix} \rm \color{#0af}{x\!+\!y} & \rm u\!+\!v \\ \rm \color{#0af}{x\!-\!y} & \rm u\!-\!\,v\end{vmatrix}\,$ $=\, \color{#0a0}{\begin{vmatrix} 1 & 1 \\ -1 & 1\end{vmatrix}}$ $\begin{vmatrix}\rm y &\rm v \\ \rm x &\rm u\end{vmatrix}\ $ and $\rm \ \overbrace{\color{#c00}1 = u\,y\!-\!v\,x}^{\text Bezout},\,$ by $\rm\,1=\gcd(x,y)\,$

take $\,\rm det\Rightarrow (u\!-\!v)(\color{#0af}{x\!+\!y})-(u\!+\!v)(\color{#0af}{x\!-\!y}) = \color{#0a0}2\cdot\color{#c00}1$ $\rm \Rightarrow \gcd(\color{#0af}{x\!+\!y,x\!-\!y}) \mid\color{#0a0}2$

i.e. it's true simply because $\,\color{#0a0}{\Delta \!=\! 2}=$ determinant of linear map $\rm\: (x,y)\,\mapsto\, (\color{#0af}{x\!-\!y,\, x\!+\!y}).\,$


Generally inverting linear $\rm (x,y)\overset{A}\mapsto (X,Y)$ by Cramer's Rule, i.e. $\rm\color{0a0}{scale}$ by $\rm\color{#c00}{adjugate},\,$ yields

$$\begin{align} \rm\color{#c00}{\begin{bmatrix}\rm\ \, d &\!\!\! \rm -b \\ \!\!\rm -c & \rm a \end{bmatrix}} \color{#0a0}\times&\, \left\{\, \begin{bmatrix}\rm a & \rm b \\ \rm c & \rm d \end{bmatrix} \begin{bmatrix} \rm x \\ \rm y \end{bmatrix} \,=\, \begin{bmatrix}\rm X \\ \rm Y\end{bmatrix}\, \right\}\\[.2em] \Longrightarrow\!\!\!\!\!\!\!\!\!\!\!\!\! &\,\qquad\qquad\, \begin{array}\ \rm\Delta\ x\ =\, \ \ \rm \color{#c00}d\ X \color{#c00}{- b}\ Y \\ \rm\Delta\ y\ = \rm \color{#c00}{-c}\ X + \color{#c00}a\ Y \end{array}^{\phantom{|}} ,\ \ \ \ \rm \Delta\ :=\ \color{#c00}{ad-bc} \end{align}\qquad$$

Hence $\rm\ n\ |\ X,Y\ \Rightarrow\ n\ |\ \Delta\,x,\Delta\,y\ \Rightarrow\ n\ |\ gcd(\Delta\,x,\Delta\,y)= \Delta\ gcd(x,y)\,$ by here & here.

In particular, if $\rm\:gcd(x,y) = 1\:$ and $\rm\,\Delta\,$ is prime, we conclude that $\rm\:gcd(X,Y) = 1\:$ or $\rm\:\Delta$.

Your problem is simply the special case $\rm\ a = c = d = 1,\ b = -1\ \Rightarrow\ \Delta = ad\!-\!bc = 2$.

Remark $ $ By above we infer $\rm \,n:=\gcd(X,Y)\mid \Delta \gcd(x,y).\,$ Further we have $\rm\ \gcd(x,y)\mid X,Y\,\Rightarrow\, \gcd(x,y)\mid \gcd(X,Y)^{\phantom{|^|}}$ hence

Theorem $\rm\,\ (x,y)\overset{A}\mapsto (X,Y)\,$ linear $\,\Rightarrow\, \bbox[7px,border:1px solid #c00]{\rm\gcd(x,y)\mid \gcd(X,Y)\mid det(A) \gcd(x,y)}$

Worth emphasis: this has a nice arithmetical interpretation in Gaussian integer arithmetic, where the linear map is simply multiplication by $\rm 1 + \it i.\:$ See my other answer here for details.

The above can also be viewed more geometrically in terms of lattices.

$\endgroup$
5
  • $\begingroup$ This is interesting. If I am not mistaken, part of this means that in general, matrices of $GL(A)$ for $A$ a gcd domain preserve the gcd. $\endgroup$
    – Evariste
    Apr 13, 2019 at 9:36
  • $\begingroup$ @Evariste Yes, that's correct. $\endgroup$ Apr 13, 2019 at 13:22
  • $\begingroup$ @BillDubuque : I am surprised that you think what I wrote in the last comment you replied to is not relevant. It appears to me to be the central point. $\endgroup$ May 31, 2021 at 18:24
  • $\begingroup$ @Michael $\ g(a,b) = 1\,$ or $\,2\!\iff\! g(a,b)\mid 2.\,$ The question does not ask when $\,g(a,\,b) = 2\ \ $ $\endgroup$ May 31, 2021 at 18:33
  • 2
    $\begingroup$ This linear algebra + number theory approach looks so interesting. Where can I learn it? Can you recommend an elementary book about it? $\endgroup$
    – Red Banana
    Jun 27, 2022 at 22:23
7
$\begingroup$

I advise not doing a proof by cases. That was my initial attempt, but I found myself going through a logical rabbit hole with no end in sight. I suggest attempting to show that the common divisor, call it $d$, satisfies $d\leq2$, which implies that $d=1$ or $2$.

Here is a proof using the above strategy. Here are a few lemmas that will assist us in our deductions.

I adopt the notation $\gcd(a,b) = (a,b)$.

$\enspace$$\enspace$Lemma 1 If $a \mid b$ and $b\neq0$, then $|a| \leq |b|$

$\enspace$$\enspace$Lemma 2 If $a \mid b$ and $a \mid c$, then for every integer $m$ and $n$, $a\mid(mb+nc)$

$\enspace$$\enspace$Lemma 3 For every integer $a$,$b$ and $c$, $(a+bc,b)=(a,b)$

$\enspace$$\enspace$ Lemma 4 For every integer $a$ and $b$, if $(a,b)=1$, there are integers $x$ and $y$ such that $ax+by=1$

Now for the proof.

Proof: Suppose $(a,b)=1$. Then from lemma 4, there are integers $x$ and $y$ such that

$$ax+by=1 \tag{1}$$

Let $d=(a+b,a-b)$ (Recall that $d>0$ by definition.

From lemma 3, we can write

$$d=(2a,a-b)$$ $$d=(2b,a-b)$$

Since $d$ is the greatest common divisor of $2a$, $a-b$, and $2b$, it follows that $d$ also divides each of them. In particular, $d\mid 2a$ and $d\mid2b$. Hence, from lemma 2, we know that $d\mid(2am+2bn)$ for arbitrary integers $m$ and $n$.

By lemma 1, we can translate $d\mid(2am+2bn)$ into the inequality

$$d \leq 2(am+bn) \tag{2}$$

Since equation $(2)$ is true for every integer $m$ and $n$, we can allow $m$ and $n$ to represent particular integers by universal instantiation*

In our case, let $m=x$ and $n=y$. Then $am+bn = ax+by$, which allows us to conclude from $(1)$ that $am+bn = 1$.

Therefore, we substitute $am+bn=1$ into $(2)$ to conclude that

$$d \leq 2 \tag{3}$$

which implies that $d=1$ or $d=2$.

  • Universal instantiation is the rule of inference that allows us to conclude that a proposition for a particular element in a domain is true given that that the statement is true for every element in the domain. For example, if the statement, "All women are wise" is true, then the statement "Kaity is wise" is also true.
$\endgroup$
6
$\begingroup$

If $\gcd (a,b)=1$, then both $a$ and $b$ can't be even simultaneously. Now two cases arise, Case $1$. Both $a$ and $b$ are odd In this case, both $a+b$ and $a-b$ will be even, so their gcd must be an even number, and so $\gcd (a+b, a-b) = \gcd (2a, a-b) = 2$, as $a-b$ is even. Case $2$. One of the $a$ and $b$ is even and the other is odd In this case, both $a+b$ and $a-b$ will be odd, so their $\gcd$ must be an odd number, and in this case $\gcd (a+b, a-b) = \gcd (2a, a-b) = 1$, as $a-b$ is odd. Note: $\gcd (a, a-b)$ can't exceed $1$ as $a$ and $b$ are relatively prime.

$\endgroup$
5
$\begingroup$

As I mentioned in a similar question, this is obvious when viewed in Gaussian integer arithmetic.

$$\begin{align}\rm Notice\quad &\rm n\mid a\!-\!b,a\!+\!b\, \Rightarrow\, n\mid a\!-\!b + (a\!+\!b)\ {\it i} = (1\!+\!{\it i})\ (a\!+\!b\, {\it i}),\,\ {\rm so}\,\ n,a,b\in\Bbb Z\\[0.7em] \rm\implies \quad &\rm n\mid \underbrace{(1\!-\!{\it i})\ (1\!+\!{\it i})}_{\large\color{#c00} 2}\, (a\!+\!b\,{\it i})\, \Rightarrow\, n\mid 2a,2b\,\Rightarrow\, n\mid (2a,2b)\!=\!2(a,b) \!=\! \color{#c00}2 \end{align}$$

Remark $\, $ Compare to the method in my other answer: $ $ here we employ the norm $\rm\, N(1 + {\it i}) = \color{#c00}2\ $ vs. there we employ the determinant $ = \color{#c00}2\:$ of the linear map $\rm\ x\to (2+3\ {\it i})\ x$.

Obviously we can generate infinitely many similar exercises by replacing $\rm\ 1+{\it i}\ $ by any nonreal Gaussian integer. For example, via $\rm\ (2+ 3\ {\it i})\ (a+b\ {\it i})\, =\, 2a-3b + (3a+2b)\ {\it i}\ $ we deduce the analogous divisibility result that if $\rm\ gcd(a,b) = 1\ $ then $\rm\ gcd(2a-3b,\, 3a + 2b) = 1\,$ or $\,\color{#c00}{13}.$

$\endgroup$
1
  • $\begingroup$ See also here where we prove $\,(a,b)=1\,\Rightarrow\, (ab,a^2+b^2) = 1\,$ using Gaussian integers. $\endgroup$ May 31, 2019 at 13:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .