4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Levitikon Jun 21 '18 at 23:56
  • $\begingroup$ 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/… $\endgroup$ – Levitikon Jun 21 '18 at 23:56
  • $\begingroup$ 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. $\endgroup$ – Levitikon Jun 22 '18 at 0:32
  • $\begingroup$ @Levitikon $25*1879192+280850 = 47260650 = 50*945213$ so it seems to work. $\endgroup$ – Jaap Scherphuis Jun 22 '18 at 8:19
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.