Question 1019656: Solving linear diophantine equation where c is greatly larger. (ax+by=c)
3x + 4y = 478
This seems pretty impossible to find the x and y using euclids algorithm..
Is it possible?
Answer by mathmate(429)   (Show Source):
You can put this solution on YOUR website!
Question:
Solving linear diophantine equation where c is greatly larger. (ax+by=c)
3x + 4y = 478
This seems pretty impossible to find the x and y using euclids algorithm..
Is it possible?
Solution:
Since GCF(3,4)=1, and 1|478, yes, there are infinite solutions.
One possible solution by inspection is x=-478, y=478, which gives in general
x=-478+4k
y=478-3k
We see that k≥478/4=120 and k≤478/3=159 for both x and y to be non-negative.
Hence the valid values for x and y are 120≤k≤159.
For example,
k=120, x=2, y=118
k=121, x=6, y=115
k=122, x=10, y=112
...
k=159, x=158, y=1
are all solutions to the given problem.
For a more detailed explanation, see answer to problem 1019647, or
http://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c
|
|
|
