1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can start by reducing the coefficients mod 11. ;) $\endgroup$ – fkraiem Feb 1 '14 at 22:10
  • $\begingroup$ Thanks for the prompt reply! How do I go about reducing the coefficients mod 11? $\endgroup$ – user80979 Feb 1 '14 at 22:12
  • $\begingroup$ 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) $\endgroup$ – ir7 Feb 1 '14 at 22:14
  • $\begingroup$ In that case, 91x≡1 mod(11) right? $\endgroup$ – user80979 Feb 1 '14 at 22:19
3
$\begingroup$

Reducing mod 11 gives

$$3x \equiv 1\ (mod\ 11)$$

which has the solution x = 4. You do not need the inverse of 91 because the inverse of 3 is the same and much easier to calculate.

$\endgroup$
  • 1
    $\begingroup$ So with the same method, I've used it to reduce the second linear congruence 91x ≡ 419 mod(8) to x ≡ 1 mod(8). Is this correct? $\endgroup$ – user80979 Feb 1 '14 at 22:37
3
$\begingroup$

${\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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.