1
$\begingroup$

Find the smallest positive integer that satisfies the system of congruences

\begin{align*} N &\equiv 2 \pmod{11}, \\ N &\equiv 3 \pmod{17}. \end{align*}

The only way I know to solve this problem is by listing it all out, and so far, it's not working. Is there a faster way? Thanks for posting a solution!

$\endgroup$
1
$\begingroup$

By the second constraint $N$ is a number of the form $17k+3$.
We may now impose the first constraint: $$ 17k+3\equiv 6k+3 \equiv 3(2k+1) \equiv 2\pmod{11} $$ leading to $2k+1\equiv 8\pmod{11}$, equivalent to $k\equiv 9\pmod{11}$.
It follows that the smallest positive number fulfilling both constraints is given by $$ \color{red}{N}=17\cdot 9+3 = \color{red}{156}.$$

$\endgroup$
  • $\begingroup$ But, how wil you program it. $\endgroup$ – jiten Jan 18 '18 at 17:35
0
$\begingroup$

You have to find a Bézout's relation between $11$ and $17$, either using the Extended Euclidean algorithm or finding an obvious relation. Here, it's easy to find $$2\cdot 17-3\cdot 11=1.$$ Once you have this relation, it's easy to check that a solution to the system of congruences $$\;\begin{cases}N\equiv a\mod11,\\N\equiv b\mod 17\end{cases}\quad \text{is}\quad N\equiv\color{red}{2a\cdot 17-3b\cdot 17\mod 11\cdot 17}.$$

$\endgroup$
0
$\begingroup$

Let's write $$N=11x+2=17y+3$$ or $$11x-17y=1$$ and solve it for $x$ and $y$.

Taking mod $11$, $$5y\equiv 45\pmod{11}$$ For $y=9$ we have $$11x-153=1$$ and $x=14$.

You can also use Bezout's identity.

$\endgroup$
  • $\begingroup$ So is the answer $14$, or are you leaving the reader to fill in missing steps? $\endgroup$ – Oscar Lanzi Sep 7 '16 at 23:17
  • $\begingroup$ The letter $x$ does not mean "answer". The reader should find $N$. $\endgroup$ – ajotatxe Sep 7 '16 at 23:18
  • $\begingroup$ Exactly. Making that explicit will help the rwader quite a lot. :-) $\endgroup$ – Oscar Lanzi Sep 8 '16 at 1:49
0
$\begingroup$

How it can be done using 'Euclid's algorithm': $N\equiv 3$ mod 17 can be written as N= 17i+ 3. Since 17= 11+ 6 is equivalent to 6 mod 11, we can write $N\equiv 2$ (mod 11) as $N\equiv 17i+ 3\equiv 6i+ 3= 2$ (mod 11) which is the sae as $6i= 2- 3= -1= 10$ (mod 11) or, dividing by 2, $3i\equiv 5$ (mod 11).

That is the same as 3i= 5+ 11j or 3i- 11j= 5. Euclids algorithm: 3 divides into 11 three times with remainder 2: 11- 3(3)= 2. 2 divides into 3 once with remainder 1: 3- 2= 1. Replace that "2" with 11- 3(3): 3- (11- 3(3))= 4(3)- 1(11)= 1. Multiplying both sides by 5, 20(3)- 5(11)= 5.

So one solution to 3i- 11j= 5 is i= 20, j= 5. Since we had before N= 17ii+ 3, N= 17(20)+ 3= 340+ 3= 343.

To check: 11 divides into 343 31 times with remainder 2: 343= 2 mod 11. 17 divides into 343 20 times with remainder 3: 343= 3 mod 17.

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