# How to show that $\gcd(a,b) = ax+by \implies \gcd(x,y)=1$?

Assume that $$\gcd(a,b)=ax+by$$ for some $a, b, x, y \in \mathbb Z$. How do I show that $\gcd(x,y)=1$? (Hint: contradiction.)

-
What do you mean with "syt"? – ulead86 Sep 5 '11 at 10:46
You have asked many questions and accepted few answers. Yet you ask another question. This does not compute. – Gerry Myerson Sep 5 '11 at 10:52
Short answer: you can't. Or at least, just because the gcd can be expressed in that form doesn't mean that it is 1. – Josh Chen Sep 5 '11 at 10:55
@Josh: I think you misread the question. You are asked to show that $\gcd(x,y)=1$, not $\gcd(a,b)=1$. (Perhaps you are seeing the same formatting error that I see -- the LaTex expression $\gcd(x,y)=1$ is above the first line instead of below it.) – TonyK Sep 5 '11 at 11:37
@alvoutila: I am not sure by the way the question is put whether you know the answer to the question and are giving me a hint, or whether the question comes with a hint, and you have not been able to solve it. In case it helps, the hint suggests assuming that there is a number c > 1 which divides both $x$ and $y$. – Mark Bennet Sep 5 '11 at 13:20
show 2 more comments

Suppose $\gcd(a,b) = ax + by = d$. Then $\exists \ u, v \in \mathbb{N}$ such that $a = u \cdot d$ and $b = v \cdot d$. So then $d = ax + by = d (u x + v y)$, or in other words $u x + v y = 1$ with $u,v \in \mathbb{N}$. So $\gcd(x,y) = 1$.

-

HINT $\rm\ \ \ (a,b)\:|\:a,b,\ \ c\:|\:x,y\ \Rightarrow\ (a,b)\:c\ |\ a\ x + b\ y\: =\: (a,b)\ \Rightarrow\ c\:|\: 1\:.\:$ Put $\rm\ c = (x,y)\:.$

-
When I saw this question in the feed, I thought: "Shouldn't Bill be the one giving hints ?!?!" :) – The Chaz 2.0 Sep 5 '11 at 14:14
@The Only when SE has neural RSS feed I can be FGITW while asleep! – Gone Sep 5 '11 at 14:24
I'm sure Skynet is working on it! – The Chaz 2.0 Sep 5 '11 at 14:57
@Bill: What exactly is the hint-part of your answer? You left it to the reader to prove that if $(x,y)|1$ then $(x,y) = 1$? :) – TMM Sep 5 '11 at 15:04
@Thi I've slightly altered the presentation. If this doesn't answer your query please let me know. – Gone Sep 5 '11 at 15:15

A proof by contradiction: Suppose $\gcd(x,y) = d > 1$. Then $\exists \ u,v \in \mathbb{Z}$ such that $x = u \cdot d$ and $y = v \cdot d$. So then $\gcd(a,b) = ax + by = d(au + bv)$, so $au + bv = \gcd(a,b)/d < \gcd(a,b)$ with $u, v \in \mathbb{Z}$. But this contradicts the fact that $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$. Therefore our assumption $d > 1$ was wrong, and $\gcd(x,y) = 1$.

-
Setting up a proof by contradiction seems unnecessarily complicated here, so I'm not sure why they would give that hint. – TMM Sep 5 '11 at 13:42
I don't get the point. Why do you get that gcd(a,b) isn't the greatest common divisor? How gcd(a,b)/d<gcd(a,b) indicates that gcd(a,b) isn't the greatest common divisor? – alvoutila Sep 5 '11 at 15:41
As found on Wikipedia: "...$\gcd(a, b)$, where $a$ and $b$ are not both zero, may be defined alternatively and equivalently as the smallest positive integer $d$ which can be written in the form $d = ap + bq$ where $p$ and $q$ are integers...". In other words, $\gcd(a,b) = \min_{d \in \mathbb{N} \setminus \{0\}} \{\exists \ p,q \in \mathbb{Z}: ap + bq = d\}$. So it is impossible that $0 < au + bv < \gcd(a,b)$ with $a,b,u,v \in \mathbb{Z}$. – TMM Sep 5 '11 at 16:03
In other words, you just use fact that gcd(a,b) is as follows( definition) to conclude contradiction with the assumption(antithesis)? – alvoutila Sep 5 '11 at 16:33
Yes. The only assumption made was that $\gcd(x,y) > 1$, which led to the contradiction that $0 < au + bv < \gcd(a,b)$ with $a,b,u,v \in \mathbb{Z}$, which conflicts with the definition of $\gcd(a,b)$. Therefore the assumption is wrong and $\gcd(x,y) = 1$. – TMM Sep 5 '11 at 18:56