Some proofs involving greatest common divisors

  • Thread starter Andrusko
  • Start date
  • Tags
    Proofs
In summary, the conversation discusses three proofs related to number theory. The first proof shows that if the greatest common divisor of two numbers a and b is c, then the gcd of a and a+b is also c. The second proof shows that if the gcd of two numbers a and b is c, and a and b can be expressed as multiples of c, then the gcd of the multiples a' and b' is 1. Lastly, the third proof involves showing that if there exist integers r and s such that rx + sy = 1, then the gcd of x and y is 1.
  • #1
Andrusko
44
0
Hey all, I'm an absolute noob to number theory stuff and I've got this assignment to do with a few proofs.

Homework Statement



Proove that:

i) if gcd(a,b) = c then gcd(a,a+b) = c

ii) if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

iii) if there exists r,s such that rx + sy = 1 then gcd(x,y) = 1

Homework Equations




The Attempt at a Solution



i) pretty sure this is right, I used a contradiction thing at the end:

prove that if gcd(a,b) = c then gcd(a,a+b) = c

c|a and c|b
a = a'c and b = b'c
so a+b = a'c + b'c
= (a' + b')c
implies c|(a+b)

suppose there exists d: gcd(a,a+b) = d, d>=c

we know c|a and c|(a+b)
and d|a and d|(a+b)

thus d|c

d cannot be greater than c

so d = c

------------------------------

ii) this one's a bit shaky:

prove that if gcd(a,b) = c and a = a'c and b = b'c then gcd(a',b') = 1

now c = ra + sb (r,s integers)
so c = r(a'c) + s(b'c)
= ra'c + sb'c
= (ra' + sb')c

dividing through by c gives:

1 = ra' + sb'

and doesn't this imply that gcd(a',b') = 1?

I don't think this is the right way to prove it.

iii) No idea where to start with this. I guess I would use a method as above, but I doubt the validity of it.

Thanks for any help!
 
Physics news on Phys.org
  • #2
The second one is very intuitive: if there were any number d dividing both a' and b', then it would also divide a and b and therefore should be a factor in the gcd (i.e. it is already in c). Perhaps you can use this in your proof (suppose that gcd(a', b') = d, not equal to 1, then c is not the gcd).

For iii) I suggest writing d = gcd(x, y), x = x' d, y = y' d and showing that d must be 1.
 
  • #3


Hi there! It's great that you're tackling these proofs in number theory, as they can be quite challenging but also very rewarding once you understand them. Let me provide some feedback and suggestions for each of the proofs you have attempted.

i) Your proof is correct, but there is one small error in your reasoning. When you say "d cannot be greater than c," this is not necessarily true. It is possible for d to be equal to c, but it cannot be less than c. So your proof should end with "d must be equal to c." Other than that, great job!

ii) Your approach is on the right track, but there are a few things that need to be clarified. Firstly, when you say "now c = ra + sb," this is not necessarily true. This only holds if c is the smallest positive integer that can be written as a linear combination of a and b. So it would be better to say "since gcd(a,b) = c, we know that c is the smallest positive integer that can be written as a linear combination of a and b." Secondly, when you divide through by c, you need to be careful as you are dividing by a variable. This is not allowed in number theory. Instead, you should use the fact that gcd(a,b) = c to cancel out the c's on both sides, leaving you with 1 = ra' + sb'. This does imply that gcd(a',b') = 1, so your proof is almost there!

iii) This proof is a bit trickier, but you're on the right track. You could use a similar approach as in your previous proofs, but instead of working with integers, you'll be working with linear combinations of x and y. Let's say that gcd(x,y) = d. This means that d is the smallest positive integer that can be written as a linear combination of x and y. Now, since rx + sy = 1, we can write 1 as a linear combination of x and y, namely 1 = (r+sy)x + (-r+sx)y. This means that 1 is a multiple of d, and since d is the smallest positive integer that can be written as a linear combination of x and y, this implies that d = 1. Therefore, gcd(x,y) = 1. I hope this helps and good luck with the rest of your assignment!
 

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 given numbers.

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

The most common method to find the GCD of two numbers is using the Euclidean algorithm, which involves continuously 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 larger than both numbers?

No, the GCD of two numbers can never be larger than either number. It can only be equal to or smaller than both numbers.

4. What is the relationship between GCD and prime numbers?

If two numbers share a common prime factor, then that prime factor will also be a factor of their GCD. In other words, the GCD of two numbers is the product of all their common prime factors.

5. How is the GCD used in solving mathematical problems?

The GCD is used in various mathematical problems, such as simplifying fractions, finding the least common multiple, and solving linear Diophantine equations. It is also helpful in determining whether two numbers are relatively prime (have no common factors other than 1).

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
754
  • Precalculus Mathematics Homework Help
Replies
6
Views
846
  • Precalculus Mathematics Homework Help
Replies
5
Views
871
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
921
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
  • Precalculus Mathematics Homework Help
Replies
9
Views
2K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
Replies
1
Views
1K
Back
Top