A proof involving the greatest common divisor

[Jamin2112]

Homework Statement

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

gcd(a,b)=1 \Rightarrow 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.

 

[annoymage]

hmm, you can multiply both side by n, since integer are well defined

 

[Office_Shredder]

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)

 

[Jamin2112]

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.

 

[Office_Shredder]

Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n

 

[Jamin2112]

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.

 

[annoymage]

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?

 

[Jamin2112]

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."

 

[Office_Shredder]

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

 

[Jamin2112]

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=a₁*a₂*a₃*...*a_n, then z divides at least one a_i, 1≤i≤n.

 

[annoymage]

Well, it's a fact that if z divides a number y=a₁*a₂*a₃*...*a_n, then z divides at least one a_i, 1≤i≤n.

that statement is true provided that z is prime, in this case 4 is not prime

 

[dmatador]

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.