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

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

## closed as off-topic by Matthew Conroy, Sami Ben Romdhane, Davide Giraudo, Yiorgos S. Smyrlis, TooOldForMathMar 2 at 19:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Matthew Conroy, Sami Ben Romdhane, Davide Giraudo, Yiorgos S. Smyrlis, TooOldForMath
If this question can be reworded to fit the rules in the help center, please edit the question.

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! –  Bill Dubuque 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. –  Bill Dubuque 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$.
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
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