# A proof involving the greatest common divisor

1. Aug 20, 2010

### Jamin2112

1. The problem statement, all variables and given/known data

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

2. Relevant 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.

3. The attempt at a solution

It just seems so intuitive ... I don't know where to start.

2. Aug 20, 2010

### annoymage

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

3. Aug 20, 2010

### Office_Shredder

Staff Emeritus
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. Aug 20, 2010

### Jamin2112

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. Aug 20, 2010

### Office_Shredder

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

6. Aug 21, 2010

### Jamin2112

Whoops! I meant my final conclusion to be gcd(na,nb)=n. All the work up to that point is correct.

7. Aug 21, 2010

### annoymage

i don't get it too, T_T, do you mind explain it?

8. Aug 21, 2010

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

9. Aug 21, 2010

### Office_Shredder

Staff Emeritus
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. Aug 21, 2010

### Jamin2112

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. Aug 21, 2010

### annoymage

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

12. Aug 23, 2010