Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

closed as off-topic by Matthew Conroy, Sami Ben Romdhane, Davide Giraudo, Yiorgos S. Smyrlis, Your Ad Here Mar 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, Your Ad Here
If this question can be reworded to fit the rules in the help center, please edit the question.

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

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer

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

share|improve this answer
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
@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$.

share|improve this answer
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? –  laovultai Sep 5 '11 at 15:41
In other words, you just use fact that gcd(a,b) is as follows( definition) to conclude contradiction with the assumption(antithesis)? –  laovultai Sep 5 '11 at 16:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.