Proofs Involving Greatest Common Divisors

  • Thread starter Ateowa
  • Start date
  • Tags
    Proofs
In summary, the homework statement is true- (a,b)=1 and (a,c)=1. However, the attempt at a solution does not seem to be going well. The student is having trouble with the basic proof steps and may need to review some of the pre-req material before continuing.
  • #1
Ateowa
25
0
I'm not sure if it goes here or the section beyond calculus, so I'm just putting it here because it doesn't involve any calculus.

Homework Statement


Suppose that (a,b)=1 [Greatest Common Divisor=1] and (a,c)=1. Does (bc, a)=1?


Homework Equations


(a,b)=d=au+bv, where u and v are integers and d is the greatest common divisor of a and b.


The Attempt at a Solution



OK, so I'm taking both of the facts I already know, that (a,b)=1 and (a,c)=1 and turning them into a useful equation:
1=au+bv, and 1=am+cn where u,v,m, and n are all integers. I know that my end goal is to find a(q)+bc(r)=1 However, I can't seem to find a way to get there. The closest I've gotten is by setting the two equal:
au+bv=am+cn, and them multiplying by bc to get:
abcu-abcm=bc2n+b2cv
Then I factor and move them to the same side to find:
0=a(bcm-bcu)+bc(cn+bv)
Which is not what I need.

Am I going about this the completely wrong way? I have a feeling I'm mistaking a basic part of the proof, as a similar problem is also giving me trouble.
 
Physics news on Phys.org
  • #2
Just think about prime factors. Do a and b have any prime factors in common? Do a and c have any prime factors in common? What does that tell you about a and bc?
 
  • #3
I know that they all share no prime factors. If they did, they would have a GCD other than one. However, I don't know how to incorporate that (Or much at all) into a proof. I'm having a bit of trouble because I skipped into this course without taking the pre-req where you learn a lot of proof techniques. I ordered a book the professor recommended but I haven't gotten it yet... I feel like that's what I'm missing, but maybe not?
 
  • #4
Try a contradiction, let a number k (not 1) divide bc and a, and let (a,b)=1 and (a,c)=1. Without loss of generality let k be prime. Use the definition of a prime (if a prime divides bc then it divides b or c). You should be able to derive a contradiction from that easily.
 
  • #5
The answer is yes and to show it by using the fact that the gcd of two numbers can be represented as a linear combination of the numbers, the key was to multiply instead of setting them equal (the hint is that 1*1 = 1). But that's not very elegant so we can be more clear.

From the given info, we have that [tex]ax_0 + by_0 = 1 = ax_1 + cy_1[/tex]. Thus [tex](by_0)(cy_1) = (1 - ax_0)(1 - ax_1) = 1 - ax_2[/tex] where [tex]x_2 = x_1 + x_0 - ax_0x_1[/tex]. Rearranging, we have [tex]bcy_0y_1 + ax_2 = 1[/tex]. Hence, [tex](bc, a) = 1[/tex].
 
  • #6
Ateowa said:
I know that they all share no prime factors. If they did, they would have a GCD other than one. However, I don't know how to incorporate that (Or much at all) into a proof. I'm having a bit of trouble because I skipped into this course without taking the pre-req where you learn a lot of proof techniques. I ordered a book the professor recommended but I haven't gotten it yet... I feel like that's what I'm missing, but maybe not?
Any integer has a unique prime factorization. If a and b have gcd 1, then they have no prime factors in common- if they did their gcd would be be divisible by those prime factors. Similarly a and c have no prime factors in common. But bc is just the product of the prime factors of b and c. None of the prime factors of bc can divide a because none of the prime factors of b and c separately did.
 
  • #7
Thanks guys! I really appreciate your help.
 

FAQ: Proofs Involving Greatest Common Divisors

1. What is a greatest common divisor (GCD)?

A greatest common divisor (GCD) is the largest positive integer that divides evenly into two or more integers. In other words, it is the biggest number that can divide into all of the given numbers without a remainder.

2. How do you find the GCD of two or more numbers?

The most common method for finding the GCD of two or more numbers is to use the Euclidean algorithm. This involves repeatedly dividing the larger number by the smaller number until the remainder is 0. The last non-zero remainder is the GCD.

3. Can the GCD of two numbers be greater than one of the numbers?

Yes, the GCD can be greater than either of the two numbers. For example, the GCD of 12 and 18 is 6, which is greater than both numbers.

4. How are GCDs used in mathematics?

GCDs are used in mathematics to simplify fractions, find common factors, and solve equations involving multiples. They are also important in number theory and cryptography.

5. Can the GCD of two numbers be negative?

No, the GCD is always a positive integer. However, if one or both of the numbers are negative, the GCD will be the same as if they were both positive.

Back
Top