When a number is divided by $13$, the remainder is $11$. When the same number is divided by $17$, then remainder is $9$. What is the number?

Question

When a number is divided by $13$, the remainder is $11$. When the same number is divided by $17$, then remainder is $9$. What is the number?

How to solve it without checking for all the numbers that satisfy the below equation.

$$13p + 11 = 17q + 9$$

Edit : I tried solving above eqn by making an eqn as

$$13(q-p) + 4q = 2$$

And then tried solving using different combinations of $p$ and $q$ and getting the results as

$9 \quad(p = 2,\,q = 1)$

$5 \quad(p = 3,\, q = 2)$

$3 \quad(p = 5,\, q = 4)$

$7 \quad(p = 6,\, q = 5)$

Since the closest value to $2$ is $3$ for $p = 5, \,q = 4$, I increased $p = 6$ and kept $q = 4$ but that resulted to $10$, couldn't figure out the values of $p$ and $q$ to satisfy the eqn.

Answer 1

You want to solve the system $$x\equiv11\pmod{13}\\x\equiv9\pmod{17}.$$

Since $13\times17=221$, we need only go up to that value.

For the first congruence, we have $$x=11,24,37,50,63,76,89,102,115,\color{red}{128},141,154,167,180,193,206,219,\cdots$$ and for the second congruence, we have $$x=9,26,43,60,77,94,111,\color{red}{128},\cdots$$

Answer 2

First write the simultaneous congruences you wish to solve:

$x \equiv 11 \pmod{13} \implies x \equiv -2 \pmod {13}$ (not strictly necessary, just done to keep the numbers a bit smaller at every stage, a good practice).

and

$x \equiv 9 \pmod {17}$

From the first, we can write $x = 13k -2$ where $k$ is an integer.

Substitute that into the second to get

$13k - 2 \equiv 9 \pmod{17}$

$13k \equiv 11 \pmod{17}$

$-4k \equiv -6 \pmod{17}$ (again keeping the numbers a bit smaller)

$k \equiv (-6)(-4)^{-1} \pmod{17}$

where $(-4)^{-1}$ is the modular multiplicative inverse of $-4$ modulo $17$. That sounds complicated, but it's basically finding a number $n$ such that $-4n \equiv 1 \pmod{17}$. That's easy because we know that $(4)(4) = 16 \equiv -1 \pmod{17}$, so $(-4)(4) \equiv -16 \equiv 1 \pmod {17}$. So $(-4)^{-1} \equiv 4 \pmod{17}$

Going back to where we left off,

$k \equiv (-6)(4) \pmod{17}$

$k \equiv -24 \equiv 10 \pmod{17}$, so you can now write $k = 17t + 10$, where $t$ is an integer.

So $x = (13)(17t + 10)-2 = 221t + 128$ and we can write the final solution as:

$x \equiv 128 \pmod{221}$

This, of course, is not a single solution, but an infinite number of solutions that are all $128$ modulo $221$.

Answer 3

We can think that $17q-13p = 2$ and $p, q$ are both even or both odd. So (first one) $$p=2x, q= 2y$$ and $$17y-13x=1$$

Since $13$ and $17$ are coprime, we can use Extended Euclid Algorithm and find $x$ and $y$. $$x=-4, y=-3$$ $$p=-8, q=-6$$

So our number is $-93$, or $-93 + 13\times 17=128$

Answer 4

Note: $$a=13p + 11 = 17q + 9 \Rightarrow 13p-17q=-2;\\ 17=13\cdot 1+4 \\ 13=4\cdot 3+1 \Rightarrow \\ 1=13-4\cdot 3=13-3(17-13\cdot 1)=13\cdot 4-17\cdot 3 \Rightarrow \\ -2=13\cdot (-8)-17\cdot (-6)\\ p=-8+17n; \\ q=-6+13n.\\ a=13(-8+17n)+11=17(-6+13n)+9>0 \Rightarrow \\ n=1, a=13(-8+17\cdot 1)+11=128.$$ Hence: $$128 \equiv 11 \pmod{13} \ \text{and} \ 128\equiv 9 \pmod{17}.$$ Note: for $n=2$, $a=13(-8+17\cdot 2)+11=349$: $$349 \equiv 11 \pmod{13} \ \text{and} \ 349\equiv 9 \pmod{17}.$$