Parameters of comparison of the first sort (through a gap)
 The set equality Will be true if x =

In number theory, which deals with the study of integer values, there is another problem that we will try to solve.

$(A*x)mod(B)=C$

if we know A, B, C then for what value of x this equality will be true?

As an example

$(58*x)mod(47)=87$

The solution of such problems is inextricably linked with the Euler function  . Although of course there is an alternative method of solution (according to Euclid), but we will not consider it.

How to solve such equations. Recall that, according to the Fermat-Euler formula, there is the following dependence. If a and m are coprime numbers (i.e. not having common divisors), then

$a^{\phi(m)}mod(m)=1$

Given that the Euler function of a prime m is m-1, we get the famous formula for any prime

$a^{m-1}mod(m)=1$

where, as already mentioned, a must be coprime with m.

Euler’s method for solving similar comparisons in formulas looks like this

$a^{\phi(m)}mod(m)=1 =>a*a^{\phi(m)-1}mod(m)=1$

$a(a^{\phi(m)-1}b)mod(m)=b$

Then, solving the equation $(a*x)mod(m)=b$

find out what is x

$x=ba^{\phi(m)-1}$

Let's try to solve our first example.

$(58*x)mod(47)=87$

$x=87*58^{\phi(m)-1}$

the Euler function for 47 is 46

and the final formula is equal $x=87*58^{46-1}$

If you count "looser" you get a huge number, but we need to find out only $xmod(m)=>xmod(47)$

To solve such a problem, we will use the material The number rest in degree on the module and find out that our solution

equally $x=87*30mod(47)=25$

check by substituting the resulting value

$\frac{(58*25-87)}{(47)}$

completely divided, which means our decision is right.

As you can see, we can also solve a similar problem along the way, which is called the inverse value modulo the residue class and which is expressed by the formula

$(A*x)mod(B)=1$

Good luck!

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