On the Subject of Diophantine Equations
People in ancient Greece were able to solve this, can you?
The module consists of a display, a number pad and a submit button.
A display will show an equation in the form
Ax + By + Cz + Dw = N,
where A, B, C, D and N are all whole numbers.
To solve the module input a specific set of 4 numbers solving the equation.
Finding an infinite family of solutions
We have an equation in the form: Ax + By + Cz + Dw = N
Compose a 5 by 4 matrix in the following form, where A, B, C, and D are equal to the digits neighbouring x, y, z, and w respectively.
A | B | C | D |
1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 0 | 0 | 1 |
For each step of the algorithm:
1). Pick the left-most closest number to zero that isn’t zero from the top row, call it M.
2). Pick the left-most non-zero element from the top row from a different than M column, call it K.
3). Find an integer Q, such that K = Q * M + R, where R is non-negative and less than the absolute value of M.
4). Multiply the values of the column that M belongs to by Q. Subtract this column from the column that K belongs to. Make sure that after this, column M is not altered.
Run the algorithm several times until you have a matrix, the top row of which contains a single non-zero number in one of the columns, call it L.
. . . . . . L . . . . . . | |||
a1 | b1 | c1 | d1 |
a2 | b2 | c2 | d2 |
a3 | b3 | c3 | d3 |
a4 | b4 | c4 | d4 |
[1] To subtract one column from another, subtract the number from one column from the number of another column in each row.
[2] To multiply a column of a matrix by a number, multiply every number of the column by that number.