Proving that d=gcd(a,b) iff 1=gcd(a1,b1)

  • Thread starter mathrocks
  • Start date
In summary, the conversation discusses a specific problem involving gcd proofs and how to prove that d=gcd(a,b) if and only if 1=gcd(a1,b1) using the theorem that states that there exists integers x and y such that d=ax+by. The conversation also includes a proposed proof by matt grime and a question about how to use the theorem to prove the problem.
  • #1
mathrocks
106
0
I'm having trouble with gcd proofs in general, but here is a specific problem.

Let a and b be integers, not both zero, and let d be a positive integer that divides both a and b. Then there exists a1 and b1 such that a=a1*d and b=b1*d.
Prove that d=gcd(a,b) if and only if 1=gcd(a1,b1)

What I have so far:

Pf: Let a and b be integers and since d|a and d|b then d|gcd(a,b) by definition. So let d*k=gcd(a,b) for some integer k. Then dk=ma+nb where m,n are integers. (I'm not sure if I can do that last statement). Now dk=m(a1*d)+n(b1*d) where a=a1*d and b=b1*d. So dk=d(m*a1+n*b1) and therefore d|(m*a1+n*b1) ...

I'm not sure if I'm heading in the right direction, but after that point I don't know how to get to 1=gcd(a1,b1).

For the second part of the proof I have"

Now assume a and b are integers such that 1=gcd(a1,b1). So there exists m and n that are integers such that 1=ma1+nb1. (Now I multiple by a integer d). Then d=md*a1 + nd*b1, and d=ma+nb where a1*d=a and b1*d=b.

Again, I'm stuck after this point.
 
Physics news on Phys.org
  • #2
I think you're making it far too complicated.

Let's do this way: suppose that gcd(a1,b1)=e and e is different from 1. Then a1=ea2 and b1=eb2 for some integers a2 and b2, then a=a2ed, and b=b2ed.

So, if d is the gcd, then e cannot be different from 1 as claimed, or de divides both a and b.

For the second part, if ass ume gcd(a1,b1)=1 we can indeed conclude that d=am+bn, but this tells us that gcd(m,n) divides d, since the gcd divides the terms on the right. So d is less than gcd(a,b) since it is some divisor of a and b, and is also divisible by the gcd so it must equal the gcd.
 
  • #3
This was mathrocks' question: [tex]a,b \in Z[/tex] [tex]a,b \neq 0[/tex], and [tex]d=gcd(a,b)[/tex]. If [tex]a=da_1[/tex] and [tex]b=db_1[/tex] for some [tex]a_1, b_1 \in Z[/tex] then you want to show that [tex]gcd(a_1,b_1) = 1[/tex].

I can't follow matt grime's proof but I know that there is a theorem which states:

Let [tex]d=gcd(a,b)[/tex]. Then there exists integers x and y such that [tex]d=ax+by[/tex].

I want to know how we can prove the problem above using this theorem.

[tex]d=gcd(a,b)[/tex]

[tex]d=ax + by[/tex] and since [tex]a=da_1[/tex] and [tex]b=db_1[/tex],

[tex]d=(da_1)x + (db_1)y = (dx)a_1 + (dy)b_1[/tex]

I'm stuck at this point. Can anyone help please?
 

FAQ: Proving that d=gcd(a,b) iff 1=gcd(a1,b1)

What does "d=gcd(a,b)" mean?

"d=gcd(a,b)" means that the greatest common divisor (gcd) of numbers a and b is equal to d. In other words, d is the largest number that can evenly divide both a and b.

What does "1=gcd(a1,b1)" mean?

"1=gcd(a1,b1)" means that the greatest common divisor (gcd) of numbers a1 and b1 is equal to 1. In other words, 1 is the largest number that can evenly divide both a1 and b1.

What does "d=gcd(a,b) iff 1=gcd(a1,b1)" mean?

"d=gcd(a,b) iff 1=gcd(a1,b1)" means that the statement "d=gcd(a,b)" is true if and only if the statement "1=gcd(a1,b1)" is also true. This means that the gcd of a and b is equal to 1 if and only if the gcd of a1 and b1 is also equal to 1.

How can you prove that "d=gcd(a,b) iff 1=gcd(a1,b1)"?

To prove that "d=gcd(a,b) iff 1=gcd(a1,b1)", we can use the property of gcd that states that if a number d is the gcd of numbers a and b, then it must also be the gcd of any multiples of a and b. Using this property, we can show that if d divides both a and b, then it must also divide any multiples of a and b, such as a1 and b1. This means that d is also the gcd of a1 and b1, and since d=gcd(a,b), it follows that 1=gcd(a1,b1) if and only if d=gcd(a,b).

Why is proving "d=gcd(a,b) iff 1=gcd(a1,b1)" important in mathematics?

Proving "d=gcd(a,b) iff 1=gcd(a1,b1)" is important in mathematics because it helps us understand the relationship between the gcd of two numbers and the gcd of any multiples of those numbers. This property is useful in solving various mathematical problems, such as finding the greatest common divisor of a set of numbers or simplifying fractions. It also provides a deeper understanding of the concept of greatest common divisor and its properties.

Back
Top