How to calculate 'n' given basic operations like '(n + x) mod p = r' where 'x', 'p', and 'r' are known?

Question

Is it possible to calculate n for a given x, p, r in different scenarios with basic operations such as (n * x) mod p = r OR (n + x) mod p = r OR (n - x) mod p = r, where n,x,p,r are large numbers?

For example, how to find n if:

(n * 6) mod 10 = 8

solution: n = 3

or

(n + 6) mod 10 = 8

solution: n = 12

or

(n - 6) mod 10 = 8

solution: n = 24

Thanks!

Answer 1

You need Modular arithmetic

[$x=y$ mod a] means that the remainder when x is divided by a is equal to the remainder when y is divided by a. Equivalently, it means (x-y) is divisible by a. That is, there exists an integer k such that (x-y)=k.

So if $x=4$ (mod 5), then $(x-4)=5k$ for some. Any k is good. So if we let k=1, then $x-4=5$ which implies $x=9$. If we let $k$ be 3, then $(x-4)=15$, so x=19. So our solutions are any x for which there exists a satisfactory $k$.

$(aX+b)$ mod $m=c$

can be reworked as :

$(aX+b)=c \ ($mod m)

Both statements are equivalent to :

$[(aX+b)-c]$ is divisible by m.

with an example:

$6n = 8$ (mod 10)

There are some slightly different ways of solving for n.

The exact meaning of that statement is $(6n-8)=10k$ for some integer k. You can divide both sides by 2 to get $(3n-4)=5k$ for some integer k. So we can go back to the modular form of the expression to get $3n=4$ (mod 5).

When we are worrying about remainders with respect to a prime number some algebraic techniques are available.

To divide by a number in modular arithmetic, you multiply by the inverse, that is to say $m$ is the inverse of $n$ if $m \cdot n$=1. Our coefficient for $n$ in $3n-4$ is 3. So 2 is the inverse since $2\cdot 3=1$ (mod 5).

So we can proceed as follows:

$3n=4$ mod(5)

$ 2\cdot[3n=4 $ (mod 5) $]$

$n=8 $ (mod 5)

But 8 can be replaced by anything it is congruent to among the numbers 0,1,2,3,4.

We take 3 since $8=3$ (mod 5).

So $n=3$ (mod 5) is our solution.

So our solutions are all n's which are three more than a multiple of 5. When we are working in modulo 10, numbers ending in both 3 and 8 satisfy this criterion.

So the solution for the original problem is $n=3$ (mod 10) and $n=8$ (mod 10).

You can also solve systems of modular equations with the Chinese Remainder Theorem