0
$\begingroup$

Find all solutions to the congruences $x \equiv 1 \pmod 4, x \equiv 0 \pmod 3$, and $x \equiv 5 \pmod 7$.

I got $M =m_1 * m_2 * m_3 = 4*3*7 = 84$

$M_1 = 21, M_2 = 28, M_3 = 12$

So I get $x = 21*u + 28*v + 12*w$

Now I don't know how to get $u, v$, and $w$. I know that I am supposed to use Chinese Remainder Theorem and Euler's algorithm but I don't know how to use them here. Can someone please help me. Or suggest me something easier.

$\endgroup$
6
  • $\begingroup$ Just apply extended euclidean algorithm to two of the congruences, then to the result apply the third. $\endgroup$ Commented Oct 31, 2018 at 2:18
  • 1
    $\begingroup$ Do you know, Pratyush, what $u,v,w$ stand for? how they are defined? No good "knowing" a formula, if you don't know what the letters mean. Also, when you write "Euler", chances are you mean "Euclid". $\endgroup$ Commented Oct 31, 2018 at 2:30
  • $\begingroup$ @GerryMyerson I do know what they mean. $\endgroup$ Commented Oct 31, 2018 at 2:31
  • $\begingroup$ @RushabhMehta so would I first solve x = 21u + 28v and then solve for w later? $\endgroup$ Commented Oct 31, 2018 at 2:32
  • $\begingroup$ Good. So, tell us, Pratyush: what do they mean? $\endgroup$ Commented Oct 31, 2018 at 2:34

2 Answers 2

2
$\begingroup$

By CRT $\, x\, \equiv\, 1\cdot 21\,(\color{#c00}{21^{-1}}\!\bmod 4) + 0\cdot 28\,(28^{-1}\!\bmod 3) + 5\cdot12\,\color{#0a0}{(12^{-1}}\!\bmod 7)\ \ \pmod{84}$

$\quad \bmod 4\!:\,\ \color{#c00}{21^{-1}}\equiv 1^{-1}\equiv \color{#c00}1$

$\quad \bmod 7\!:\,\ \color{#0a0}{12^{-1}}\equiv (-2)^{-1}\equiv 1/(-2)\equiv 8/(-2)\equiv -4\equiv\color{#0a0}{ 3}$

Therefore $\ x\,\equiv\, 1\cdot 21\cdot\color{#c00} 1\, +\, 0\, +\, 5\cdot 12\cdot\color{#0a0} 3\equiv 201\equiv 33\pmod{84}.\ \ $ Aternative below.


$\!\bmod 3\!:\,\ x\equiv 0\iff x = 3j$

$\!\bmod 7\!:\,\ x = 3j \equiv 5 \equiv 12\iff j \equiv 4\iff x = 3(4+7k) = 12+21k$

$\!\bmod 4\!:\,\ 1\equiv x = 12+21k\equiv k\iff x = 12+21(1+4n) = 33+84n$

$\endgroup$
0
$\begingroup$

We have $x\equiv 0 \pmod 3.$

Since $\gcd(3,4)=1,$ the set $\{0+3n:1\leq n\leq 4\}$ is a complete residue system modulo $4.$ So just one member $(0+3\cdot 3=9)$ is congruent to $1$ mod $4.$ So $x\equiv 9 \pmod {3\cdot 4}.$

Since $\gcd(3\cdot 4,7)=1$ the set $\{9+12m: 1\leq m\leq 7\}$ is a complete residue system modulo $7.$ So just one member $(9+12\cdot 2=33)$ is congruent to $5$ mod $7.$ So $x\equiv 33 \pmod {3\cdot 4\cdot 7}.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .