﻿ Diophantine Equations — Keep Talking and Nobody Explodes Module ## 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

 To subtract one column from another, subtract the number from one column from the number of another column in each row.
 To multiply a column of a matrix by a number, multiply every number of the column by that number.

If N is not divisible by L, then solution doesn't exist, proceed with Inputting Answer section; else there exists an infinite family of solutions x, y, z, w.

x = T1 * a1 + T2 * b1 + T3 * c1 + T4 * d1
y = T1 * a2 + T2 * b2 + T3 * c2 + T4 * d2
z = T1 * a3 + T2 * b3 + T3 * c3 + T4 * d3
w = T1 * a4 + T2 * b4 + T3 * c4 + T4 * d4

Proceed with Getting Values of T section.

### Getting Values of T

• If L belonged to ith column, then Ti = N / L.
• Else if ith symbol of the serial number is a digit, then Ti = that digit.
• Else if ith symbol of the serial number is a letter, then Ti = alphabetical order of the letter modulo 10.

### Inputting Answer

If solution exists input each number x, y, z and w in order, pressing S for SUBMIT between every separate number. If solution doesn't exists just press S. Inputting an incorrect answer will issue a strike.