A proof involving the greatest common divisor

In summary, the conversation discusses a problem that seeks to prove the relationship between the greatest common divisor of two numbers and their product. The participants discuss various approaches, including using a theorem about relatively prime numbers and the definition of greatest common divisor. The correct proof is eventually reached, which states that if the greatest common divisor of two numbers is 1, then the greatest common divisor of their product is equal to the product itself.
  • #1
Jamin2112
986
12

Homework Statement



Don't have the book with me, but the problem basically asked me to prove that

gcd(a,b)=1 [tex]\Rightarrow[/tex] gcd(an,bn)=n


Homework Equations



Since gcd(a,b)=1 is a fancy way of saying a and b are relatively prime (or is "a and b are relatively prime" a fancy way of saying gcd(a,b)=1?), I know of a theorem that may prove useful.

Thm.
If a and b are relatively prime then there exist integers m, n such that ma+nb=1.



The Attempt at a Solution



It just seems so intuitive ... I don't know where to start.
 
Physics news on Phys.org
  • #2
hmm, you can multiply both side by n, since integer are well defined
 
  • #3
That's too much machinery. Just go with the definition. gcd(na,nb) is the largest number dividing both na and nb. So two parts:

1)Show that n divides na and nb (I hope this is easy)
2) Show that n is the largest such number (this will require the co-prime part)
 
  • #4
Office_Shredder said:
That's too much machinery. Just go with the definition. gcd(na,nb) is the largest number dividing both na and nb. So two parts:

1)Show that n divides na and nb (I hope this is easy)
2) Show that n is the largest such number (this will require the co-prime part)

Alright.

Proof. Let z be a number that divides na and nb. At least z=n. Now let z=a>n. z divides a but not b; otherwise gcd(a,b) would equal a. Our only other option is z=b>n, but it does not work for the same reason as before. Therefore, if gcd(a,b)=1, then gcd(na,nb)=1.
 
  • #5
Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n
 
  • #6
Office_Shredder said:
Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n

Whoops! I meant my final conclusion to be gcd(na,nb)=n. All the work up to that point is correct.
 
  • #7
Office_Shredder said:
Why does a number dividing na and nb have to be a or b?

i don't get it too, T_T, do you mind explain it?
 
  • #8
If z divides a number, then z divides one of its factors. For example, I know 4|24 because 24=4*6 and 4|4. That's the point behind "if z divides an then z divides a or z divides n."
 
  • #9
But you don't know that it's factored correctly. For example, given 4*6, 12 divides 24 but 12 doesn't divide 4 or 6.

It sounds like you want to word it something like this: we know gcd(na,nb) is greater than or equal to n. Suppose it's greater than n. It has to be divisible by n (since the greatest common divisor is divisible by all divisors of na and nb), so is if of the form gcbd(na,nb)=nx. Now you want to show that x=1
 
  • #10
Office_Shredder said:
But you don't know that it's factored correctly. For example, given 4*6, 12 divides 24 but 12 doesn't divide 4 or 6.

It sounds like you want to word it something like this: we know gcd(na,nb) is greater than or equal to n. Suppose it's greater than n. It has to be divisible by n (since the greatest common divisor is divisible by all divisors of na and nb), so is if of the form gcbd(na,nb)=nx. Now you want to show that x=1

Well, it's a fact that if z divides a number y=a1*a2*a3*...*an, then z divides at least one ai, 1≤in.
 
  • #11
Jamin2112 said:
Well, it's a fact that if z divides a number y=a1*a2*a3*...*an, then z divides at least one ai, 1≤in.

that statement is true provided that z is prime, in this case 4 is not prime
 
  • #12
What about a proof by contraposition? Say the gcd(an, bn) does not equal n. Then there is an integer k greater than n that divides both an and bn. Say an = k * l and bn = k * m, l and m integers, and so a = (k * l) / n and b = (k * m) / n. You know that a and b are integers since you are dividing out a factor. K is greater than n and divides both, so this seems to prove that the gcd of a and b is not 1. It seems like a trivial proof so there must be some gaping holes...

EDIT: I think it is necessary to say that abs(k) > abs(n). Also that n cannot be zero, making it impossible for k = 1.
 
Last edited:

What is the greatest common divisor?

The greatest common divisor (GCD) is the largest positive integer that divides evenly into two or more numbers.

How is the GCD calculated?

The GCD can be calculated using the Euclidean algorithm, which involves finding the remainder after dividing the larger number by the smaller number. This process is repeated until the remainder is 0, and the last non-zero remainder is the GCD.

What is the significance of GCD in mathematics?

The GCD is a fundamental concept in number theory and is used in many mathematical applications, such as simplifying fractions, finding common denominators, and solving equations involving fractions.

Can the GCD of two numbers be greater than either of the numbers?

No, the GCD will always be less than or equal to the smaller of the two numbers. If the GCD is equal to one, the two numbers are said to be relatively prime or coprime.

How is the GCD used in the proof of mathematical theorems?

The GCD is often used as a tool in mathematical proofs to show that two numbers or expressions have a common factor. It can also help to simplify equations and expressions by factoring out the GCD. In some cases, the GCD can also be used to prove the existence of solutions to certain mathematical problems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
2
Views
902
  • Calculus and Beyond Homework Help
Replies
5
Views
978
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
901
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top