GCD proof

  • Thread starter mathrocks
  • Start date
  • #1
106
0
I'm having trouble with gcd proofs in general, but here is a specific problem.

Let a and b be integers, not both zero, and let d be a positive integer that divides both a and b. Then there exists a1 and b1 such that a=a1*d and b=b1*d.
Prove that d=gcd(a,b) if and only if 1=gcd(a1,b1)

What I have so far:

Pf: Let a and b be integers and since d|a and d|b then d|gcd(a,b) by definition. So let d*k=gcd(a,b) for some integer k. Then dk=ma+nb where m,n are integers. (I'm not sure if I can do that last statment). Now dk=m(a1*d)+n(b1*d) where a=a1*d and b=b1*d. So dk=d(m*a1+n*b1) and therefore d|(m*a1+n*b1) ....

I'm not sure if I'm heading in the right direction, but after that point I don't know how to get to 1=gcd(a1,b1).

For the second part of the proof I have"

Now assume a and b are integers such that 1=gcd(a1,b1). So there exists m and n that are integers such that 1=ma1+nb1. (Now I multiple by a integer d). Then d=md*a1 + nd*b1, and d=ma+nb where a1*d=a and b1*d=b.

Again, I'm stuck after this point.
 

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
4
I think you're making it far too complicated.

Let's do this way: suppose that gcd(a1,b1)=e and e is different from 1. Then a1=ea2 and b1=eb2 for some integers a2 and b2, then a=a2ed, and b=b2ed.

So, if d is the gcd, then e cannot be different from 1 as claimed, or de divides both a and b.

For the second part, if ass ume gcd(a1,b1)=1 we can indeed conclude that d=am+bn, but this tells us that gcd(m,n) divides d, since the gcd divides the terms on the right. So d is less than gcd(a,b) since it is some divisor of a and b, and is also divisible by the gcd so it must equal the gcd.
 
  • #3
1,266
11
This was mathrocks' question: [tex]a,b \in Z[/tex] [tex]a,b \neq 0[/tex], and [tex]d=gcd(a,b)[/tex]. If [tex]a=da_1[/tex] and [tex]b=db_1[/tex] for some [tex]a_1, b_1 \in Z[/tex] then you want to show that [tex]gcd(a_1,b_1) = 1[/tex].

I can't follow matt grime's proof but I know that there is a theorem which states:

Let [tex]d=gcd(a,b)[/tex]. Then there exists integers x and y such that [tex]d=ax+by[/tex].

I want to know how we can prove the problem above using this theorem.

[tex]d=gcd(a,b)[/tex]

[tex]d=ax + by[/tex] and since [tex]a=da_1[/tex] and [tex]b=db_1[/tex],

[tex]d=(da_1)x + (db_1)y = (dx)a_1 + (dy)b_1[/tex]

I'm stuck at this point. Can anyone help please?
 

Related Threads on GCD proof

  • Last Post
Replies
10
Views
902
  • Last Post
Replies
14
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
5
Views
4K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
12
Views
10K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
16
Views
4K
Top