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

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?

-
$79\equiv 7\pmod{9}$, and $79\equiv 4\pmod{5}$. – André Nicolas Mar 2 '13 at 17:10

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.

-

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$.

-

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).

-
What happened to your LaTex?? – DonAntonio Mar 2 '13 at 18:03

$\,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}$$

-
Just added the missing "$=1$" following $7x$ in the second-to-last line. – amWhy Mar 2 '13 at 17:37
Thanks @amWhy , I didn't even see that one. – DonAntonio Mar 2 '13 at 17:39
The "Added" part does not explain how you derived $\rm\,11^{-1} \equiv 41\,\ (mod\ 90).\:$ But that is essential here, since computing that inverse is trivially equivalent to solving the posed equation. – Math Gems Mar 2 '13 at 18:20
Everything is trivial here, @MathGems...once you know this stuff, as it is only arithmetic. One can try and err with multiples of $\,90\,$ and add one, or better: use Euclides Algorithm and backwards to get: $$90=8\cdot 11 +2\Longrightarrow 2=90-8\cdot 11\\11=5\cdot 2+1\Longrightarrow 1=11-5\cdot 2$$ thus, going backwards: $$1=11-5\cdot 2=11-5(90-8\cdot 11)=41\cdot 11+(-5)\cdot 90\Longrightarrow$$ $$11\cdot 41=1\pmod {90}\Longrightarrow 11^{-1}=41$$ But, of course, if the OP knows about searching the inverse modulo $\,90\,$ then he probably knows the above... – DonAntonio Mar 2 '13 at 18:58
@Don While modular inversion may be trivial to your or I, given the question, the OP probably doesn't "know this stuff". As such, I was puzzled why you thought it helpful to effectively pull the inverse out of a hat. It seems that you used the extended Euclidean algorithm. It would be helpful to explicitly say that in your answer. Else readers may be misled into thinking that the inversion must be immediate, and may waste time looking for the (nonexistent) immediate method of computing the inverse (as did I). – Math Gems Mar 2 '13 at 19:33