Number theory - gcd and linear diophantine equations

In summary, the conversation discusses finding a necessary and sufficient condition for a solution to the equation ax + by = c, where gcd(a,b) = 1 and x0, y0 are any integer solutions with x > 0 and y > 0. The solution involves finding a value of k that satisfies the equations x1 - x0 = kb and y1 - y0 = -ka, which can be used to find a solution with x > 0 and y > 0.
  • #1
reb659
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?
 
Physics news on Phys.org
  • #2
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.
 

1. What is a greatest common divisor (gcd)?

A greatest common divisor, or gcd, is the largest positive integer that evenly divides two or more given integers.

2. How is the gcd of two numbers calculated?

The gcd of two numbers can be calculated using Euclid's algorithm, which involves continuously dividing the larger number by the smaller number until the remainder is 0.

3. What is a linear diophantine equation?

A linear diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers and x and y are variables. The goal is to find integer solutions for x and y that satisfy the equation.

4. How can the gcd be used to solve linear diophantine equations?

The extended Euclidean algorithm can be used to find the gcd and also the coefficients x and y that satisfy the equation ax + by = gcd(a,b). These coefficients can then be used to find all integer solutions for the original linear diophantine equation.

5. What are some practical applications of number theory and linear diophantine equations?

Number theory and linear diophantine equations have many practical applications, including cryptography, computer science, and engineering. They are also used in various fields such as finance, physics, and chemistry for solving problems involving integers.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
19
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
829
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
815
Back
Top