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

  • MHB
  • Thread starter karush
  • Start date
In summary, we are given that $d = gcd(a,b)$ and $a=da'$, $b=db'$, and want to show that $gcd(a',b') = 1$. Using the fact that $d = gcd(da', db')$, we can assume that $a' = b' = 1$. This implies that $a = b = d$, which means that $gcd(a,b) = gcd(d,d) = d$ and $gcd(a',b') = gcd(1,1) = 1$. We also discussed the converse of Bezout's identity and how it leads to a contradiction if $\gcd(a', b') > 1$, proving the statement.
  • #1
karush
Gold Member
MHB
3,269
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
  • #2
$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'?
 
  • #3
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$.​
 
  • #4
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.
 
  • #5
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
 

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

What is the GCD of two numbers?

The GCD (Greatest Common Divisor) of two numbers is the largest positive integer that divides both numbers without a remainder.

How do you prove that the GCD of two numbers is 1?

To prove that the GCD of two numbers, a and b, is 1, you need to show that there is no common factor other than 1 between the two numbers. This can be done by finding the prime factors of both numbers and checking if they have any common factors.

Why is it important to prove that the GCD of two numbers is 1?

Proving that the GCD of two numbers is 1 is important because it shows that the two numbers are relatively prime or coprime. This means that they have no common factors other than 1, making them useful in many mathematical calculations and applications.

Can the GCD of two numbers be greater than 1?

Yes, the GCD of two numbers can be greater than 1. In fact, the GCD of two numbers will always be greater than 1 if the two numbers are not relatively prime. For example, the GCD of 12 and 18 is 6, which is greater than 1.

How do you use the Euclidean Algorithm to find the GCD of two numbers?

The Euclidean Algorithm is a method of finding the GCD of two numbers by repeatedly dividing the larger number by the smaller number and using the remainder as the new divisor. This process is repeated until the remainder is 0, at which point the last non-zero remainder is the GCD of the two numbers.

Similar threads

Replies
2
Views
1K
Replies
3
Views
2K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
2
Views
2K
Replies
2
Views
1K
Replies
1
Views
1K
Back
Top