Solve $79x \equiv 1 \pmod {90}$

Question

This is an example in my lecture notes and I am a little confused as to how my lecturer has gone about doing this. In my notes, it says

$90 = 2 \times 3^2 \times 5$. So we can now say that solving $79x \equiv 1 \pmod {90}$ is equivalent to solving

$$79x \equiv 1 \pmod 2$$ $$7x \equiv 1 \pmod 9$$ $$4x \equiv 1 \pmod 5$$

...

How has she got the $79, 7$ and $4$ in the equivalent set of equations?

Answer 1

to solve the problem $79x \equiv 1 \pmod{90}$ you can use the Chinese Remainder Theorem to obtain the answer. For this way you need to factorize the 90 so the factors are pairwise coprimes (like the modules in the congruences your lecturer made), then you need to transform the congruences to the form:

$$ \left\{ \begin{aligned} x & \equiv b_1 \pmod{a_1} \\ x & \equiv b_2 \pmod{a_2} \\ \vdots & \\ x & \equiv b_r \pmod{a_r} \end{aligned} \right. $$

For this particular case we have that $90 = 2 \cdot 5 \cdot 9$ is a good factorization because the three factors are coprimes pairwise, so we need to fix the congruences to match the structure above:

The first congruence is in mod 2, so we can simplify it because $79 \equiv 1 \pmod 2$, so:

$ 79 \cdot x \equiv 1 \cdot x \pmod{2} \quad \Rightarrow \quad x \equiv 1 \pmod{2} $

Second congruence is $4x \equiv 1 \pmod{5}$. The multiplicative inverse of 4 in mod 5 is the same number: $ 4 \cdot 4 = 16 \equiv 1 \pmod{5}$ and taking product by 4 on the congruence:

$ 4 \cdot 4 \cdot x \equiv 4 \cdot 1 \pmod{5} \Rightarrow x \equiv 4 \pmod{5} $

In the last congruence $7x \equiv 1 \pmod{9}$ the inverse of 7 is again 4. Using this inverse we obtain an equivalent congruence:

$ 4 \cdot 7 \cdot x \equiv 4 \cdot 1 \pmod{9} \Rightarrow x \equiv 4 \pmod{9} $

Now resolve the initial problem is equivalent to find x that $$ \left\{ \begin{aligned} x & \equiv 1 \pmod 2 \\ x & \equiv 4 \pmod 5 \\ x & \equiv 4 \pmod 9 \end{aligned} \right. $$

Now x can be obtained using the theorem (check http://en.wikipedia.org/wiki/Chinese_remainder_theorem for more information about this). To find x is convenient to express in a linear combination of the $b_i$:

$ x = \sum_{1 \le i \le r} m_i b_i \pmod{n} $

In this case we must search for the coefficients:

$ \begin{align} m_1 & \quad \text{coefficient for mod 2} \\ m_2 & \quad \text{coefficient for mod 5} \\ m_3 & \quad \text{coefficient for mod 9} \end{align} $

This coefficients are obtained using the expression $ m_i = s_i \cdot \frac{n}{a_i} $, where $s_i = \left(\frac{n}{a_i}\right)^{-1}$ in mod $a_i$.

For this problem $n = 90$ and $ \begin{align} a_1 & = 2 \\ a_2 & = 5 \\ a_3 & = 9 \end{align} $

Inverses are:

$ \begin{align} s_1 = \left(\frac{90}{2}\right)^{-1} \pmod 2 = 1 \\ s_2 = \left(\frac{90}{5}\right)^{-1} \pmod 5 = 2 \\ s_3 = \left(\frac{90}{10}\right)^{-1} \pmod 9 = 1 \end{align} $

and the coefficients in mod 90:

$ \begin{align} m_1 = s_1 \cdot \frac{90}{2} = 1 \cdot 45 = 45 \\ m_2 = s_2 \cdot \frac{90}{5} = 2 \cdot 18 = 36 \\ m_3 = s_3 \cdot \frac{90}{10} = 1 \cdot 10 = 10 \end{align} $

Value of x is obtained evaluating the linear combination:

$ x = \sum_{1 \le i \le 3} m_i \cdot b_i = 45 \cdot 1 + 36 \cdot 4 + 10 \cdot 4 = 229 \equiv 49 \pmod{90} $

We can check that $x = 49$ satisfies the three congruences:

$ \begin{align} 49 & \equiv 1 \pmod 2 \\ 49 & \equiv 4 \pmod 5 \\ 49 & \equiv 4 \pmod 9 \end{align} $

and the initial problem:

$ 79 \cdot 49 = 3871 \equiv 1 \pmod 90 \quad (\text{because } 3871 = 90 \cdot 43 + 1)$

There is a CRT calculator in this page http://davidwees.com/chineseremaindertheorem/ Hope this could be useful.

Answer 2

Note that $79\equiv 7\pmod 9$, so $79x\equiv 7x\pmod 9$, and solving $79x\equiv 1\pmod9$ is the same as solving $7x\equiv1\pmod9$. Similarly, $79\equiv4\pmod5$, so solving $79x\equiv 1\pmod5$ is the same as solving $4x\equiv1\pmod5$.

Answer 3

Congruences descend to factors of the modulus as follows: $\rm\ a\equiv b\,\ (mod\ mn)\:\Rightarrow\: a\equiv b\,\ (mod\ n),\:$ because $\rm\:m\,n\mid a-b\:\Rightarrow\:n\mid a-b.\:$ Thus, for example $\rm\:79x\equiv 1\,\ (mod\ 90)\,$ $\Rightarrow$ $\rm\,79x\equiv 1\,\ (mod\ 9).\:$ Notice $\rm\:mod\ 9\!:\ 79\equiv 7,\:$ so $\rm\:1\equiv 79x\equiv 7x.\,$ Ditto for the other factors of $90$. In this case a simpler way is to solve it mod $9$ and $10,$ then combine to a solution mod $\rm\,lcm(9,10) = 90,\:$ as follows:

$\rm mod\ 10\!:\ 1 \equiv 79x\equiv -x,\:$ so $\rm\:x = -1\!+\!10n.\:$ $\rm\:mod\ 9\!:\ 1 \equiv 79x\equiv -2x\equiv -2(-1\!+\!10n)\equiv 2\!-\!2n,\:$ so $\rm\:2n\equiv 1\equiv 10,\:$ so $\rm\:n\equiv 5,\:$ i.e. $\rm\:n = 5\!+\!9k.\:$ Thus $\rm\: x = -1\!+\!10n=-1\!+\!10(5\!+\!9k) = 49\! +\! 90k.$

Alternatively $\rm\: mod\ 45\!:\ 1\equiv 79x\equiv -11\:\Rightarrow\: x\equiv 1/(-11)\equiv 4/(-44)\equiv 4/1,\:$ so $\rm\:x = 4+45n.\:$ $\rm\:mod\ 2\!:\ 1 \equiv 79x\equiv x = 4\!+\!45n\equiv n,\:$ so $\rm\:n = 1\!+\!2k\:\Rightarrow\:x = 4\!+\!45n = 4\!+\!45(1\!+\!2k)= 49\!+\!90k.$

Beware $\ $ One can employ fractions $\rm\ x\equiv b/a\ $ in modular arithmetic (as above) only when the fractions have denominator $ $ coprime $ $ to the modulus $ $ (else the fraction may not uniquely exist, $ $ i.e. the equation $\rm\: ax\equiv b\,\ (mod\ m)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

Answer 4

$\,90=2\cdot3^2\cdot5\,\Longrightarrow 79x=1\pmod{90}\Longrightarrow x=1\pmod{2,3^2,5}$ , so

$$79x=1\pmod 2\Longleftrightarrow x=1\pmod 2$$

$$79x=1\pmod 9\Longleftrightarrow7x = 1\pmod 9\,\,\,\text{, since}\,\,\,79=7\pmod 9$$

$$79x=1\pmod 5\Longleftrightarrow4x=1\pmod 5\,\,\text{, since}\,\,\,79=4\pmod 5$$

Added: Another, more direct, approach. The following arithmetic is done modulo $\,90\,$:

$$79=-11\;\;,\;\;11^{-1}=41\Longrightarrow 79^{-1}=(-11)^{-1}=-41=49\Longrightarrow$$

$$79x=1\pmod {90}\Longrightarrow x=79^{-1}\pmod {90}=49\pmod{90}$$