Can someone walk me through this wolframalpha solution?

Given $$x = (625/50)a-(100/50)$$ $$x = (214/60)b-(110/60)$$

The following integer solution was provided by a wolframalpha widget:

$$a = 214n+10$$ $$b = 750n+35$$ $$x=2675n+123$$

I am very interested in how the 10, 35, and 123 were determined here because they are the actual values of a, b and x and I didn't think they couldn't be solved.

This is the only algebra solver I found that produces these values and unfortunately they don't show a step by step here.

Can anyone walk me through the steps that produce this solution? Here is a link to the wolframalpha widget.

Wolfram also gives a solution in the reals which is equivalent to the following: $$b = \frac{5(75 a - 1)}{107}\\x = \frac{25 a-4}{2}$$ This is what you get if you consider $a$ a constant and solve for the two remaining variables $x$ and $b$ in terms of $a$.

We want everything to be integers. This is easy for second equation - for $x$ to be an integer, we need $a$ to be an even number.

The first equation is trickier - for $b$ to be an integer, we need $75 a - 1$ to be a multiple of $107$. By trying various small numbers for $a$, you will find soon enough that $a=10$ works: $75*10-1 = 749 = 7*107$. Once you have that solution, then you also know that $a=10+107$ will work to make $b$ an integer, as will $a=10+2*107$, or in fact $a=10+107k$ for any integer $k$.

Combining this with the fact that $a$ must be even, you get that $k$ is even, so $a=214n+10$. The expressions for $b$ and $x$ then follow by substituting this into the equations.

I skipped a lot of details in the above to give you the overall flow of the reasoning. Those details have to do with Modular Arithmetic. Here is just a short overview of those details, with links for you to find out more.

1) When is $75 a - 1$ a multiple of $107$?

This is just the modular equation $75a-1\equiv0 \mod 107$, or $a\equiv 75^{-1} \mod 107$. To solve it, you need to find the inverse of $75$ modulo $107$, which exists because $75$ and $107$ are coprime. This is done using the Extended Euclidean Algorithm, which gives the result that $10*75-7*107=1$, so $10$ and $75$ are inverses modulo $107$.

2) How do you combine the restrictions on $a$ imposed by the two equations?

In this case the second equation imposed a simple restriction, that $a$ is even. We actually have the two modular equations: $$a \equiv 10 \mod 107\\a \equiv 0 \mod 2$$ With different numbers it would have been a bit trickier to combine them into a single restriction, and we would have had to use the Chinese Remainder Theorem.

• This is incredibly helpful. I'm actually working on a software project that incorporates this math in a portion of it's logic. Been quite the adventure. So I was able to reproduce, in code, the target values using an Extended Euclid algo script, which is great! Any minor adjustment to the inputs still produce the results I would expect. However, when using much larger numbers, the results are no longer accurate. Could you take a look at these results and spot any reasons or errors? – Levitikon Jun 21 '18 at 23:56
• x = (30639/6190)a-(4605/6190) and x = (13743/5520)b-(8190/5520), when plugged into the wolframalpha widget do produce the results I would expect so I can assume the equations are valid for this. The widget gives a real solution equivelent to b = (1879192a + 280850)/945213. When 1879192 and 945213 are plugged into an Extended Euclid Calculator however, the results are not even close. Any insight would be helpful! wolframalpha.com/input/… – Levitikon Jun 21 '18 at 23:56
• In this case I secretly know that a = 25 and as you describe, (25 * 1879192) + 280850 should produce a multiple of 945213, but it doesn't. I suspect the equation wasn't simplified enough? You factored out 5 in your example. I don't think this example can be factored any more. They are co-prime, so no issues there. – Levitikon Jun 22 '18 at 0:32
• @Levitikon $25*1879192+280850 = 47260650 = 50*945213$ so it seems to work. – Jaap Scherphuis Jun 22 '18 at 8:19

Subtracting,

$$\frac{25}{2}a-2-\frac{107}{30}b+\frac{11}{6}=0$$

Get rid of the denominators

$$15\cdot25a-60-214b+55=0$$

$$375a-214b-5=0$$ It's now obvious that it's a usual linear diophantine equation. <-- As you can see here, it can be solved with the extended Euclidean algorithm.