To find number on a remainder of division

Module (gap) rest (comma) Module (gap) rest, etc.

The received number
The received number

One ancient Chinese task was:

"Find the number that, when divided by 3, gives the remainder of 2, when divided by 5, gives the remainder of 3, and when divided by 7, gives the remainder of 2"

To solve such problems, we will do the following

The source number from the source data can be expressed like this

remainder theorem example

Where k are integers

We write out the series changing k from 0 in increasing

series of values

It is easy to see that 23 is found in all three rows.

This is our answer, the next number (128) will meet only after 105 = 3 * 5 * 7 samples. Since these numbers are coprime, we simply take their product.

And so the general answer to our problem is

X = (23) mod (105)

An easy algorithm to understand, isn't it?

But it is not entirely inconvenient when large numbers are encountered, and again, when composing the elements of a series, one can make a mistake.

There is another way

Let us be given a system of comparisons

x = (c_1) mod (m_1), x = (c_2) mod (m_2) .... x = (c_k) mod (m_k)

Where ? m_1, m_2, ...., m_k are positive pairwise mutually prime integers.

Let x_1, x_2, ...., x_k - the roots of auxiliary comparisons of the form

comparison system

We can already solve such equations Comparisons of 1 degree. Number theory

Having learned these roots, we can calculate our initial number by the formula

X = (m_2m_3 ... m_kx_1c_1 + m1m_3 ... m_kx_2c_2 + .... + m_1m_2 ... m_ {k-1} x_kc_k) mod (m_1m_2 ... m_k)

For our example, the source data looks like this

x = (2) mod (3), & x = (3) mod (5), x = (2) mod (7)

Then the comparison system will have the form

(35x_1) mod (3) = 1 \\\\ & (21x) mod (5) = 1 \\\\ (15x) mod (7) = 1

Solving them we get

x_1 = 2, x_2 = 1, x_3 = 1

And our solution has the form

x = 35 * 2 + 21 + 15 = 106

Or the same as

x = (233) mod (105) = (233-105-105) mod (105) = 23mod (105)

As you can see, the answer is the same.

Our bot solves such problems using the PHP GMP library. Therefore, to the accuracy of calculations and restrictions on the length of the values, this is for them :)

Although it has its own materials in particular: Calculation of the value of the Euler function , the remainder of the number in power modulo and the Diophantine equation with three unknowns

Important: It is logical and this should be taken into account when entering numbers, in a pair of numbers (module-remainder), the module (always!) Is larger than the remainder.

The second important point. The module is always (!) A positive number, the remainder can be negative, but it’s better to bring it to a positive number.

How to do it? All links to related materials have already been given.

Example

Find out what number is guessed if the remainder when dividing by 37 is 11, when dividing by 9 is 4, when dividing by 7 is 1, and when dividing by 100, the remainder is 25.

Note that the modules, that is, the numbers (37, 9, 7, 100) into which we divide the unknown number, are pairwise coprime. That is, we do not have a single pair of these numbers, so that they would have a common divisor.

If so, then we can solve a similar problem by the method described above. Enter in the input field

37 11, 9 4, 7 1, 100 25

In an instant we get the answer

Received number
Received number
 
Good luck!
 

Copyright © 2020 AbakBot-online calculators. All Right Reserved. Author by Dmitry Varlamov