# Find the multiplicative inverse of $17 \bmod 55$ using the Chinese remainder theorem

I understand that this amounts to solving the following system of linear congruences:

$$17x \equiv 1 \pmod 5$$

$$17x \equiv 1 \pmod {11}$$

but then my course notes go on to equate this system with

$$2x \equiv 1 \pmod 5$$

$$6x \equiv 1 \pmod {11}$$

which I don't understand at all.

Any help would be much appreciated, thanks.

As $17\equiv2\pmod 5$, then $17x\equiv 2x\pmod 5$ whenever $x$ is an integer. Therefore $17x\equiv1\pmod 5$ is equivalent to $2x\equiv1\pmod5$ etc.

$\ \ \ \ \ \ \ \ \ 17x \equiv 1 \ (mod \ 5)$

$\implies 17x = 5k+1\ \ \ \ \ \ \ k\ \in \mathbb{Z}$

$\implies 15x+2x= 5k+1\ \ \ \ \ \ \ k\ \in \mathbb{Z}$

$\implies 2x= 5(k-3x)+1\ \ \ \ \ \ \ k\ \in \mathbb{Z}$

$\implies 2x= 5k'+1\ \ \ \ \ \ \ k'\ \in \mathbb{Z}$

$\implies 2x \equiv 1 \ (mod \ 5)$

Basic idea is that $15x$ will leave $0$ remainder with $5$, irrespective of the value of $x$.

It is a common practice to reduce the numbers larger than the modulus in the congruence relation to corresponding remainders.

Modulus also has commutative and associative properties with addition and multiplication, which further help in simplifying the congruence relations.

• Try \pmod 5 to get $\pmod 5$. I'd do it for you but my arthritis is kicking up. – Mr. Brooks Jun 26 '17 at 20:43

Hint $\ {\rm mod}\ 5\!:\,\ \color{#c00}{17\equiv 2}\,\Rightarrow\,1\equiv \color{#c00}{17}x\equiv \color{#c00}2x\$ by the Congruence Product Rule.

More conceptually $\ A\equiv a\,\Rightarrow\, A^{-1}\equiv a^{-1}\$ (by special case product $\equiv1$ in Product Rule).

Hence the above is $\,17\equiv 2\,\Rightarrow\, 17^{-1}\equiv 2^{-1}\$ from this viewpoint.

I am inclined to say

$17\cdot 3 = 51\\ 17^{-1} \equiv 3\pmod 5$

$17\cdot 2 = 34\\ 17^{-1} \equiv 2\pmod {11}$

$17^{-1} \equiv 13\pmod {55}$