1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ignore the $\mathbb Z_n$ stuff and solve it with the chinese remainder theorem. Then see what it is equal to modulo n. $\endgroup$ – David Peterson Sep 21 '16 at 2:55
  • $\begingroup$ 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. $\endgroup$ – Tyler Durden Sep 21 '16 at 2:57
  • $\begingroup$ youtube.com/watch?v=ru7mWZJlRQg $\endgroup$ – David Peterson Sep 21 '16 at 2:59
  • $\begingroup$ @TylerDurden you might find the cut the knot page a bit more accessible. $\endgroup$ – Omnomnomnom Sep 21 '16 at 2:59
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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