The basis the degree and the module divided at least by one gap

Let's consider one of tasks often meeting in arithmetics and the theory of numbers which can be expressed several examples.

What rest the following numbers will have

$2^{31}\\\\-57^{321}\\\\101^{999921441}$

if to try to divide them into number 31?

And if the first example can be solved on the calculator, so to speak "in a forehead, without thinking", then as you will solve the third example, it for some very not a trivial task.

What is the rest? The rest in this case is such number (on absolute value less module!), which having taken away from initial number, the received result will be is divided totally into the module (in our example the module this number 31)

That is, if we designate the rest a letter X we will receive (in the first example) that the number $2^{31}-X$  is divided totally (without the rest) into the module

Or in another, record more habitual

$2^{31}modM=X$ where M - the module

How to solve similar problems?

For this purpose we should know several properties from the theory of numbers which we will show on the second example  $-57^{321}$

1. $-57^{321}mod31=-1^{321}57^{321}mod31$

Even to explain a reluctance, we put-1 outside "brackets" (a separate multiplier) and we can count at once. If degree of number (321) even the result is equal 1 if odd-1.

2.$(-1)57^{321}mod31=(-1)mod31*57^{321}mod31$

If number it is possible to present that in the form of two and more factors, the rest from this number will be equal to the work of the remains from factors on the same module.

3.$-1*57^{321}mod31=-1*(57-31-31)^{321}mod31=-1*(-5)^{321}mod31$

Having added or having taken away the whole number of the module from any factor - the rest will not change.

4. $-1*(-5)^{321}mod31=-1*(-5^3)^{\frac{321}{3}}mod31=-1*(-5^3)^{107}mod31$

Too nothing difficult, just transformed degree. Usual property of degrees.

5. $-1*(-5^3)^{107}mod31=-1*(-125)^{107}=-1*(-125+31+31+31+31)^{107}mod31$

Here we cubed-5 and used the 3rd rule, having added to it 4 times the module

6. $-1*(-125+124)^{107}mod31=-1*(-1)^{107}mod31=-1*-1mod31=1$

That is we can claim that $\frac{-57^{321}-1}{31}$ there is an integer.

7.The last rule says that is formal, there are always two rests and they are equivalent. In our example it is 1 and-30 as $\frac{-57^{321}+30}{31}$  too an integer.

I hope it a small example of analysis, gave you a technique of the solution of similar tasks.

And the boat which is created will help you to learn easily correctness of the solution of similar tasks or if you the teacher, easily and precisely to generate tasks for pupils.

Each element may contain up to 19 figures (in general I do not know on what length, there can be mistakes, but at (to) 19 symbols everything works well)

therefore there is nothing terrible to find the rest here from such "monster"

$-5239009213117^{100445342321}mod6576500111123$

who wants can multiply on the calculator:)

INTERESTING FACTS

It is claimed that if P - that a prime number is carried out here such equality

$2^{P-1}modP=1$

This condition necessary (that is it is applicable to all prime numbers) but not sufficient (that is there are composite numbers for which this formula is valid too)

Beautiful expression was found so far tested the boat (for 2014):)

$666^{777}mod2014=666$

$666^{777}mod777=666$

For May 31, 2018 still there was something interesting

You look

$1331^{56}mod171=134$

$1331^{2*any\ number}mod171=134$

$133000..000001^{2*any\ number}mod171=134$

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