Intro to Proofs: Greatest Common Divisors

  • Thread starter rdr3
  • Start date
  • #1
5
0

Homework Statement



(a) Let a and b be integers with gcd(a,b)=d, and assume that ma+nb=d for integers m and n. Show that the solutions in Z to

xa+yb=d

are exactly

x=m+k(b/d), y=n-k(a/d)

where k∈Z.

(b) Let a and b be integers with gcd(a,b)=d. Show that the equation

xa+yb=c

has a solution (x,y)∈ ZxZ if and only if d|c.

Z refers to integers.

Homework Equations





The Attempt at a Solution



Ok so I'm pretty sure I figured out part (a).

Part (b) on the other hand is causing me problems. I know since it's an "if and only if" question, I have to prove it both ways.

This is what I have so far.

So we have some x and y, such as

x0a+y0b=d

Then we multiply both sides by some arbitrary element, such as n. Giving us,

(nx0)a+(ny0)b=nd=c

So that's the first part. Now I'm supposed to go the other way with it, showing that
xa+yb=c -> c=nd, n∈ Z.
 

Answers and Replies

  • #2
85
0
How about the contrapositive for the other direction? That might be easier.
 
  • #3
5
0
So maybe this?

Suppose dc...

Then c≠nd

In which case, c≠nd≠(nx0)a+(ny0)b.

So like that? Or am I way off? Sorry I'm not very good at this... The teacher explains things way over everyone's head.
 

Related Threads on Intro to Proofs: Greatest Common Divisors

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