# 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.)

-

1
What do you mean with "syt"? – ulead86 Sep 5 '11 at 10:46

12
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

1
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

6
@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

1
@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

## 3 Answers

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)\:.$

-

3
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

2
@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$.

-

2
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

1
– 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

1
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 37, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9493737816810608, "perplexity_flag": "middle"}