# How to reduce the following Linear Congruence: $91x = 419 \pmod{11}$

I am stuck at reducing linear congruences in order to use a system of linear congruences for the Chinese Remainder Theorem. Here is the linear congruence:

$$91x \equiv 419 \pmod{11}$$

Do I have to find an inverse for $91x$? Do I also have to construct a Linear Diophantine equation?

Any help will be greatly appreciated! In particular to the material, linear congruence reduction might be my only hurdle.

• You can start by reducing the coefficients mod 11. ;) – fkraiem Feb 1 '14 at 22:10
• Thanks for the prompt reply! How do I go about reducing the coefficients mod 11? – user80979 Feb 1 '14 at 22:12
• 91x = 88x + 3x (you dont need 88x, as it is a multiple of 11) and 419 = 418 + 1 (you don't need 418, same reason) – ir7 Feb 1 '14 at 22:14
• In that case, 91x≡1 mod(11) right? – user80979 Feb 1 '14 at 22:19

$$3x \equiv 1\ (mod\ 11)$$
${\rm\ mod}\ 11\!:\ 10\equiv -1\,\Rightarrow\, 10^2\equiv 1\,\Rightarrow\, \color{#c00}{419}\equiv 4\!-\!1\!+\!9\equiv \color{#c00}1,\ \ \color{#0a0}{91}\equiv -9\!+\!1\equiv \color{#0a0}3.\,$ Substituting these smaller congruent values yields $\ \color{#0a0}{91}x\equiv \color{#c00}{419}\iff \color{#0a0}3x\equiv \color{#c00}1\ (\equiv 12),\$ so $\ x\equiv\, \ldots$
$91x \equiv 419 \pmod {11}$. Furthermore, $91x = 8(11)x + 3x$ and $418 = 38(11) + 1$, and since we are working $\pmod {11}$ we can reduce the equation to $3x \equiv 1 \pmod {11}$. You should be able to take it from here.