# Modular Numbers and Cryptography

## Modular Equations

Solve $$(4 + x) \equiv 5 \pmod{7}$$

A modular system \pmod{n} allows only a fixed set of remainder values, $$0,1,2,\ldots,n-1$$. One practical approach to solving modular equations, at least when n is reasonably small, is to simply try all these integers. For each solution found, other can be found by adding multiples of the modulus to it.

Because dividing 5 by 7 yields a remainder 5, the criterion for congruence is that the given equation is true only if dividing $$4+x$$ by 7 also yields remainder 5. In other words, find all values of x such that, a remainder of 5 is the result when $$4+x$$ is divided by 7.

Since modulo 7 has residues $$0,1,2,3,4,5,6$$, let's test each of them.

 $$x=0: (4+0) \equiv 5 \pmod{7}$$ is false. The remainder is 4. $$x=1: (4+1) \equiv 5 \pmod{7}$$ is true. The remainder is 5. $$x=2: (4+2) \equiv 5 \pmod{7}$$ is false. The remainder is 6. $$x=3: (4+3) \equiv 5 \pmod{7}$$ is false. The remainder is 0. $$x=4: (4+4) \equiv 5 \pmod{7}$$ is false. The remainder is 1. $$x=5: (4+5) \equiv 5 \pmod{7}$$ is false. The remainder is 2. $$x=6: (4+6) \equiv 5 \pmod{7}$$ is false. The remainder is 3.

$$\therefore x =1$$  is a solution of the equation $$(4 + x) \equiv 5 \pmod{7}$$. We can find other solutions by adding the modulus 7.

$1+7=8, 8+7=15, 15+7=22, \ldots$

The set of all nonnegative solutions of $$(4 + x) \equiv 5 \pmod{7}$$ is $$\{1,8,15,22,29,\ldots\}$$ or $$1+7n,n\in\mathbb{Z}$$. There are infinite many solutions stemming from the residue 1 in $$\mod{7}$$. However, there can be more than one residue as the solution.

Solve $$(3x + 2) \equiv 5 \pmod{9}$$

When we test the residues we find,

$$x=1: (3+2) \equiv 5 \pmod{9}$$ is true. The remainder is 5.

$$x=4: (3+2) \equiv 5 \pmod{9}$$ is true. The remainder is 5.

$$x=7: (3+2) \equiv 5 \pmod{9}$$ is true. The remainder is 5.

So the solution is when $$x = 1+9n,4+9n,7+9n, n\in\mathbb{Z}$$.

Solve $$2x \equiv 3 \pmod{6}$$

When we test all the residues, none of them will have a remainder of 3, that is because every value gets doubled and becomes an even number. Thus, there is no solution.