MHB GCD of a and b: Proving $gcd(a',b')=1$

  • Thread starter Thread starter karush
  • Start date Start date
karush
Gold Member
MHB
Messages
3,240
Reaction score
5
$\textsf{Let $d = gcd(a,b)$
If $a=da'$ and $b=db'$,
show that $gcd(a',b')=1$}$
$\textsf{it would follow that then}$
$$d=gcd(da',db')$$
$\textsf{ok I would assume that $a'=1$ and $b'=1$ then}$
$$gcd(1,1)=1$$
$\textit{bk has no answer}$:(
 
Last edited:
Physics news on Phys.org
$d=gcd(a,b)$, assuming $d,a,b > 0$
Then there are integers $r$ and $s$ such that $d=ra+sb$

If $a=da'$ and $b=db'$ then $d=rda'+sdb'$
Dividing by d gives: $1=ra'+sb'$

Thus $gcd(a',b')=1$

$d=gcd(a,b)$
$a=da'$ and $b=db'$
If $a'=b'=1$, then $a=b=d$
thus $gcd(d,d)=d$ and $gcd(1,1)=1$

Who is 'bk'?
 
karush said:
$\textsf{Let $d = gcd(a,b)$
If $a=da'$ and $b=db'$,
show that $gcd(a',b')=1$}$
$\textsf{it would follow that then}$
$$d=gcd(da',db')$$
$\textsf{ok I would assume that $a'=1$ and $b'=1$ then}$
$$gcd(1,1)=1$$
$\textit{bk has no answer}$:(

Your book should have this important result:

If $\gcd(a,b)=d$, there exist integers $r,s$ such that $ra+sb=d$.​

Note that the converse is not true: if we can integers $r,s$ such that $ra+sb=d$, we can’t conclude that $d$ is the gcd of $a,b$; all we can say is the the gcd divides $d$. However, if $d=1$, then the converse is also true: in other words,

$a,b$ are relatively prime integers if and only if there exist integers $r,s$ such that $ra+sb=1$.​
 
steenis said:
$d=gcd(a,b)$, assuming $d,a,b > 0$
Then there are integers $r$ and $s$ such that $d=ra+sb$

If $a=da'$ and $b=db'$ then $d=rda'+sdb'$
Dividing by d gives: $1=ra'+sb'$

Thus $gcd(a',b')=1$

Erm... you're using Bézout's identity and its specialized converse here (edit: as Olinguito has just explained).
... but I don't expect the OP to be familiar with those...

And we don't really need those identities.
It suffices to start with: suppose $\gcd(a', b')=e>1$, then...
This leads to a contradiction, proving the statement.
 
I like Serena said:
Erm... you're using Bézout's identity and its specialized converse here (edit: as Olinguito has just explained).
... but I don't expect the OP to be familiar with those...

And we don't really need those identities.
It suffices to start with: suppose $\gcd(a', b')=e>1$, then...
This leads to a contradiction, proving the statement.

I start the class today
I just stuck my toes in the kiddie pool

oh
bk=text book

anyway MHF has kept me alive:cool:

- - - Updated - - -

steenis said:
Who is 'bk'?

text book
 
Back
Top