# Find a number $x \in \mathbb{Z}_{355213}$ such that $x = 2 \pmod {71}$ and $x = 13 \pmod {5003}$.

As the title says, my problem is this:

Find a number $x \in \mathbb{Z}/{355213}\mathbb{Z}$ such that $x = 2 \mod 71$ and $x = 13 \mod 5003$.

I know that $71\cdot 5003 = 355213$. I also know that $71$ and $5003$ are prime.

I solved this with programming ($x=235154$), but I naively searched through all possibilities. I'd like to know how to solve this without programming.

• Ignore the $\mathbb Z_n$ stuff and solve it with the chinese remainder theorem. Then see what it is equal to modulo n. – David Peterson Sep 21 '16 at 2:55
• Thanks @DavidP! This is for a cryptography class and we have not yet covered the Chinese Remainder Theorem. But as it is popping up a lot, could you link me to somewhere that teaches this theorem? The Wikipedia page was a bit beyond my comprehension. – Tyler Durden Sep 21 '16 at 2:57
• youtube.com/watch?v=ru7mWZJlRQg – David Peterson Sep 21 '16 at 2:59
• @TylerDurden you might find the cut the knot page a bit more accessible. – Omnomnomnom Sep 21 '16 at 2:59

The first equation shows that $x = 2 + 71n$ for some $n \in \mathbb{Z}$.

The second equation is that $x = 13 + 5003m$ for some $m \in \mathbb{Z}$.

So we must find integers n and m such that $2 + 71n = 13 + 5003m$, or $71n - 5003m = 11$.

The Extended Euclidean Algorithm can be used to find them.

Start by dividing $-5003$ by $71$: $$-5003 = (-71)*71+38$$ Then continue by dividing each quotient by remainder: \begin{align} 71 &= 1*38+33 \\ 38&=1*33+5 \\ 33&=6*5+3 \\ 5&=1*3+2 \\ 3&=1*2+1 \\ \end{align}

Now go back up the chain to write $gcd(-5003,71)=1$ in terms of $-5003$ and $71$: \begin{align} 1&=3-1*2 \\ &=3-1*(5-1*3) \\ &=2*3-5 \\ &=2*(33-6*5)-5 \\ &=2*33-13*5 \\ &=2*33 - 13*(38-33) \\ &=15*33-13*38 \\ &=15*(71-38)-13*38 \\ &=15*71-28*38 \\ &=15*71-28*(-5003+71*71) \\ &=-1973*71-28*(-5003)\\ \end{align}

Multiply both sides of the equation $1 = -1973*71 - 28*(-5003)$ by $11$ to get $11 = -21703*71-308*(-5003)$. So $n=-21703$ is one solution, which gives $x = 2 + 71(-21703) = -1 540 911$ in $\mathbb Z_{355213}$ which is equivalent to your solution of $235154$.

https://en.wikipedia.org/wiki/Fight_Club_2

This method is called a Continued Fraction.

$$5003/71 \approx 70.4647$$ $$70.4647, \; 2.1515, \; 6.5999, \; 1.6666, \; 1.4999, 2.0000$$

$$\begin{array}{cccccccccccccc} & & 70 & & 2 & & 6 & & 1 & & 1 & & 2 & \\ \frac{0}{1} & \frac{1}{0} & & \frac{70}{1} & & \frac{141}{2} & & \frac{916}{13} & & \frac{1057}{15} & & \frac{1973}{28} & & \frac{5003}{71} \end{array}$$

$$5003 \cdot 28 - 1973 \cdot 71 = 1$$