# A proof involving the greatest common divisor

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

## Answers and Replies

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

Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
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)

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
Staff Emeritus
Science Advisor
Gold Member
Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n

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.

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?

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
Staff Emeritus
Science Advisor
Gold Member
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

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.

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

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: