1
$\begingroup$

I need to find minimal $x\in\Bbb N$ that solves the linear congruences:

$6x \equiv 2 \pmod {\!4}$

$3x \equiv 6 \pmod {\!9}$

$x \equiv 15 \pmod {\! 17}$

I divided the first congruence by $2$ and the second congruence by $3$, then used the Chinese remainder theorem.

I got $x\equiv 393 \pmod {2\cdot 3\cdot 17} $

I checked that this solution actually solves the 3 equations.

But is it the smallest one? If so, then why ?

Thanks.

$\endgroup$
2
  • 2
    $\begingroup$ $393$ doesn't satisfy the second or third congruence. $\endgroup$
    – paw88789
    Jun 13, 2015 at 14:31
  • $\begingroup$ If $x$ is a solution of the system, so is $x+tm$ where $m$ is the modulus (in this case $2\cdot 3\cdot 17$ and $t$ is an integer, positive, negative, or $0$. $\endgroup$
    – André Nicolas
    Jun 13, 2015 at 14:32

2 Answers 2

Reset to default
2
$\begingroup$

Your congruences may be reduced to

$x\equiv 1\pmod{2}$

$x\equiv 2 \pmod{3}$

$x\equiv 15 \pmod{17}$

We have $\mod {17}$, $x\equiv 15\equiv 32\equiv 49 \equiv 66 \equiv 83$.

And we note that $83$ satisfies the other two congruences.

The general solution is then $x\equiv 83 \pmod{102}$

$\endgroup$
4
  • 2
    $\begingroup$ Simpler: $\,{\rm mod}\ 17\!:\ 15\equiv -2\equiv -19,\,$ and $\ {-}19\equiv 1\pmod 2,\, $ $\, -19\equiv 2\pmod 3\ \ $ $\endgroup$
    – Bill Dubuque
    Jun 13, 2015 at 14:42
  • $\begingroup$ In fact we have to add/subtract to $\,15\,$ multiples of $\,34\,$ (not $\,17)\,$ to keep it odd, so subtracting finds it on the first try. $\endgroup$
    – Bill Dubuque
    Jun 13, 2015 at 14:46
  • $\begingroup$ but isn't there a simple way that always works? like the chinese therom? $\endgroup$
    – user2993422
    Jun 13, 2015 at 15:00
  • $\begingroup$ if Id have many equations and bigger number and i need to find the smalest solution . how do i do it? $\endgroup$
    – user2993422
    Jun 13, 2015 at 15:01
1
$\begingroup$

From the comments you're interested in using Chinese Remainder Theorem in general. Here is one algorithm you can use.

Inbetween, instead of using clever manipulations, you can use EEA, etc. as explained below.

$x\equiv 1\pmod{\! 2}\iff (x=2k+1$ for some $k\in\Bbb Z)$.

$\,\bmod{3}\!:\ \ \ x\equiv 2\iff \color{#00F}2k+1\equiv 2\iff \color{#00F}{-1}k\equiv 1\iff k\equiv -1\equiv 2$

$\iff (k=3n+2$ for some $n\in\Bbb Z)\iff x=2(3n+2)+1=6n+5$.

$\,\bmod{17}\!:\ \ \ x\equiv 15\equiv -2\iff 6n+5\equiv -2\iff 6n\equiv -7\equiv -24$

$\stackrel{:6}\iff n\equiv -4\equiv 13\iff n=17m+13$ for some $m\in\Bbb Z$.

$\iff x=6(17m+13)+5=102m+83$.

We've used clever manipulations here. If you want to solve it algorithmically in a short time, the numbers are huge and you don't see a simple solution to $ax\equiv b\pmod{\! m}$ using manipulations like those above, then use either Extended Euclidean algorithm or what Bill Dubuque calls Gauss's algorithm. Here is how you apply EEA:

$$ax\equiv b\pmod{\! m}\iff ax+mk=b$$ for some $k\in\Bbb Z$. This has a solution $(x,k)$ iff $(a,m)\mid b=:(a,m)h$ (see here).

Using EEA you find $x_1,k_1\in\Bbb Z$ such that $$ax_1+mk_1=(a,m)\iff a(x_1h)+m(k_1h)=b$$

So $x\equiv x_1h\pmod{\! m}$ is your solution.

$\endgroup$

You must log in to answer this question.

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