I started by saying that there exists an $x,y$ such that $1 = ax +by$ but I really don't know where else to go with this. Any hints?
Asked
Active
Viewed 58 times
2
-
1Once you know that there exists $x$ and $y$ so that $ax+by=1$, then the gcd divides $1$, but since $1$ is the smallest positive integer, you're done! – Michael Burr Mar 22 '16 at 18:33
-
1HINT: $1=a-bc$, so $(a,b)$ divides $1$. – Crostul Mar 22 '16 at 18:33
3 Answers
3
If $d$ is any common divisor of $a$ and $b$ then it also divides their difference $a-b$. Then also the difference of $a-b$ and $b$ thus $a-2b$. Continuing like this, we get that $d$ is a common divisor of all integers $a-\kappa b$, for any integer $\kappa$. Thus, $d$ will be a divisor of $a-bc=1$. Consequently, $d=1$. Thus, $(a,b)=1$.
KonKan
- 7,344
1
Whenever you find two integers $x$ and $y$ such that $1=ax+by$, you can conclude that $\gcd(a,b)=1$. Indeed, if some integer $d>0$ divides both $a$ and $b$, we have $$ a=du,\quad b=dv $$ so $$ 1=ax+by=d(ux+vy) $$ and therefore $d\mid 1$, hence $d=1$.
If you choose $x=1$ and $y=-c$, you have $$ ax+by=a-bc=1 $$
egreg
- 238,574
0
More generally, if $a_1a_2...a_n =b_1b_2...b_m\pm 1 $, then $\gcd(a_i, b_j) = 1 $ for every choice of $i$ and $j$.
The proof is identical to the others here: If $k$ divides both $a_i$ and $b_j$, then $k$ divides both $a_1a_2...a_n$ and $b_1b_2...b_m$ so that it divides their difference which is $\pm 1$.
Even more generally, if $a_1a_2...a_n =b_1b_2...b_m\pm c $, then $\gcd(a_i, b_j) $ divides $c$ for every choice of $i$ and $j$.
The proof is identical.
marty cohen
- 107,799