$$7 \times 14 \mod 10 = 8$$

Is there a theorem or procedure that optimizes a way to find 7 and 14 given 8 and mod 10?

Brute force is the obvious approach here, such as finding all multiples of 8, then 8 + 10, then 8 + 20, etc. but it seems like there ought to be a way to derive this without brute force.


Expanding on this a little.

What do you want 7 and 14 to satisfy?

Lets say I have a way of knowing when the right numbers are found. I have equations that I can plug candidates into to determine if they are the original multiples.

Also, this example is greatly simplified. I'm actually dealing with 256-bit numbers that are very large with a 256-bit mod, so any sort of brute force that involves incriminating by mod is impracticable.

It's very likely the large numbers that 7 and 14 represent are co-prime, so any sort of enumeration that yields candidates (that satisfy the equation) will have such a small search space that it might be practical. But this only works if each iteration produces a valid set and the effort of producing the sets are $O(n)$.

For example, the source code of the Extended Euclidean algorithm enumerates with a valid set of numbers each cycle.

Is there an equivalent function that can perform some operation each cycle to produce valid numbers that satisfy $x \times y \mod 10 = 8$ that I can loop through until I find the numbers that satisfy my other verification equations?

  • 2
    $\begingroup$ What do you want 7 and 14 to satisfy? The fact that their product is equivalent to 8 mod 10 is not enough to uniquely identify them: the same is true of 8 and 1, for instance. $\endgroup$ – Alex Nolte Jul 2 '18 at 12:25
  • 2
    $\begingroup$ Or $49$ and $2$, or $98$ and $1$. Suppose we remove the "mod 10" part: I tell you I've got two integers whose product is $64$ and ask what they are...can you tell me? If you can't solve that problem, then you can't solve the one posed here. $\endgroup$ – John Hughes Jul 2 '18 at 12:30
  • 1
    $\begingroup$ Emm. $7 \times 14$ isn't difficult. For example if you have something like $107 \times 114$, then the standard method is to reduce $\pmod{10}$. So $107 \equiv 7 \pmod{10}$ and $114 \equiv 4\pmod{10}$, so $107 \times 114 \equiv 7 \times 4 \equiv 28 \equiv 8\pmod{10}$. The same method works for product of higher numbers. Note: The standard trick is $\textbf{keep reducing mod 10}$. $\endgroup$ – crskhr Jul 2 '18 at 12:32
  • 1
    $\begingroup$ Your $14$ is just the same as $4$ since your are working modulo $10$. If we work $\mod 10$, we might as well restrict ourselves to the "representatives" $0,1,2,\ldots,9$. So in how many ways can we write $8$ as a product of two of those? Brute force for me gives $$\begin{align}1\cdot 8\\ 2\cdot 4\\ 2\cdot 9\\ 3\cdot 6\\ 4\cdot 7\\ 6\cdot 8\end{align}$$ The fifth one of these is your example. Is this what you are after? $\endgroup$ – Jeppe Stig Nielsen Jul 2 '18 at 12:38
  • 1
    $\begingroup$ Sometimes, instead of using the ten representatives $0,1,2,\ldots,9$ as above, it is easier to look at $0,\pm 1,\pm 2,\pm 3,\pm 4,5$ instead. The wanted product is $-2$. Then my six solutions from the comment above become instead:$$\begin{align} (+1)\cdot(-2) = 1\cdot 8\\ (-1)\cdot(+2) = 9\cdot 2\\ (+2)\cdot(+4) = 2\cdot 4\\ (-2)\cdot(-4) = 8\cdot 6\\ (+3)\cdot(-4) = 3\cdot 6\\ (-3)\cdot(+4) = 7\cdot 4\\ \end{align}$$ These six solutions may be condensed into three lines with the notation:$$\begin{align} (\pm 1)\cdot(\mp 2)\\ (\pm 2)\cdot(\pm 4)\\ (\pm 3)\cdot(\mp 4)\\ \end{align}$$ $\endgroup$ – Jeppe Stig Nielsen Jul 2 '18 at 12:58

Your Answer

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

Browse other questions tagged or ask your own question.