Number theory - gcd and linear diophantine equations

  • Thread starter reb659
  • Start date
  • #1
64
0

Homework Statement



Suppose that gcd(a, b) = 1 with a, b > 0, and let x0, y0 be any integer solution to the equation ax + by = c. Find a necessary and sufficient condition, possibly depending on a, b, c, x0, y0 that the equation have a solution with x > 0 and y > 0.

Homework Equations





The Attempt at a Solution


I'm pretty lost. Can anyone point me in the right direction?
 

Answers and Replies

  • #2
139
12
Well, if one of [tex] x_0 [/tex] or [tex] y_0 [/tex] is negative, then you have to look for another solution [tex] (x_1, y_1) [/tex] with [tex] x_1, y_1 > 0 [/tex]. By subtracting equations, you get [tex] a(x_1 - x_0) + b(y_1 - y_0) = 0 [/tex]. Can you see why this equation implies that [tex] x_1 - x_0 = kb [/tex] and [tex] y_1 - y_0 = -ka [/tex] for some integer [tex] k [/tex]? Once you do, your problem is reduced to a search for a value of [tex] k [/tex] such that [tex] x_0 + kb > 0 [/tex] and [tex] y_0 - ka > 0 [/tex]. You should be able to take it from here.
 

Related Threads on Number theory - gcd and linear diophantine equations

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
462
  • Last Post
Replies
2
Views
499
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
Replies
2
Views
3K
Top