Diophantine Equations With Positive Solutions
----------- --------- ---- -------- ---------
You are to find a strictly positive integral solution
(x,y) to
A*x + B*y = C
given that A, B, C are strictly positive integers.
Polynomial equations with integer coefficients in which
only integer solutions are sought are called Diophantine
equations, so we are asking for positive solutions of
one of the simplest Diophantine equations.
Input
-----
For each of several test cases, a single line of the
form:
A B C
where
10 <= A,B <= 1,000
10 <= C <= 1,000,000
Input ends with an end of file.
Output
------
For each test case, one line of the form
A * x + B * y = C
where all the letters are replaced by non-zero positive
integers so as to make the equation true. The integers
replacing A, B, C are taken from the test case input
line. You must find the solution values of x and y.
Input will be such that there is a unique solution.
Sample Input
------ -----
10 25 100
29 17 300
33 66 99
128 241 34647
128 241 34648
128 241 34649
113 197 21952
113 197 21953
113 197 21954
113 197 21955
113 197 30001
Sample Output
------ ------
10 * 5 + 25 * 2 = 100
29 * 8 + 17 * 4 = 300
33 * 1 + 66 * 1 = 99
128 * 137 + 241 * 71 = 34647
128 * 105 + 241 * 88 = 34648
128 * 73 + 241 * 105 = 34649
113 * 67 + 197 * 73 = 21952
113 * 135 + 197 * 34 = 21953
113 * 6 + 197 * 108 = 21954
113 * 74 + 197 * 69 = 21955
113 * 133 + 197 * 76 = 30001
File: positive.txt
Author: Shai Simonson
Editor: Bob Walton
Date: Thu Oct 4 20:12:03 EDT 2018
The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.