Examples of methods for solving modular equations
Simple mod questions. Can you show example to do such things?
- $x+40 \equiv 1 \pmod{88}$.
- $x \cdot 40 \equiv 1 \pmod{88}$.
- $5a+3b \equiv 1 \pmod{11}$ and $2a+b \equiv 7 \pmod{11}$.
Thank you.
$\endgroup$ 21 Answer
$\begingroup$Solving modular equations is mostly just like solving ordinary equations.
How do you solve $7x + 6 = 20$?
$$\begin{align}7x+6 &= 20 \\ 7x &= 20 - 6 = 14 \\ x &= 14 \cdot \frac{1}{7} = 2 \hspace{15.4em} \end{align}$$
Now, how do you solve $7x+6 = 20 \bmod 29$?
$$\begin{align}7x+6 &\equiv 20 & \pmod{29} \\ 7x &\equiv 20 - 6 \equiv 14& \pmod{29} \\ x &\equiv 14 \cdot \frac{1}{7} \equiv 14 \cdot 25 \equiv 350 \equiv 2 & \pmod{29} \end{align}$$
(or, in this case, just note that $14/7 = 2$, although the calculation usually isn't so obvious)
One of the main differences is that you can't use long division, and need to use a new algorithm to divide: e.g. you can use the extended euclidean algorithm to compute the reciprocal of any element. Presumably your book has shown you this.
Although with such small numbers, trial and error works fine too.
$\endgroup$ 6
