# Find the smallest positive integer that satisfies the system of congruences $N \equiv 2 \pmod{11}, N \equiv 3 \pmod{17}.$

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!

## 4 Answers

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

• But, how wil you program it. – jiten Jan 18 '18 at 17:35

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

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.

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

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.