A proof involving the greatest common divisor

  • Thread starter Jamin2112
  • Start date
  • #1
986
9

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.
 

Answers and Replies

  • #2
362
0
hmm, you can multiply both side by n, since integer are well defined
 
  • #3
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,623
630
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
986
9
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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,623
630
Why does a number dividing na and nb have to be a or b? Your final conclusion is wrong, gcd(na,nb)=n
 
  • #6
986
9
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
362
0
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
986
9
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
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
4,623
630
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
986
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

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
362
0
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
120
1
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:

Related Threads on A proof involving the greatest common divisor

Replies
7
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
24
Views
3K
  • Last Post
Replies
2
Views
895
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
19
Views
5K
Replies
2
Views
1K
Top