1
$\begingroup$

This is from a Youtube video on the Chinese Remainder Theorem -https://www.youtube.com/watch?v=ru7mWZJlRQg

enter image description here

The value at each column is the product of the mod of the two other columns(so moding will reduce to one value)
The author is currently on the step to ensure x, which is composed of a sum of congruences, is
$\equiv$ 2(mod 4). Once he applied modulus 4 to all the congruences, he was left with x $\equiv$ 3(mod 4) which isn't the same as x $\equiv$ 2(mod 4). To do this the author recommended taking an approach of converting 3 (mod 4) to 1(mod 4) then to 2 (mod 4). Why doesn't the author go straight from 3 mod 4 to 2 mod 4 by multiplying the 15 by 2? That way x $\equiv$ 6 $\equiv$ 2 mod(4). Is there a reason he chose this roundabout approach and not the direct approach?

$\endgroup$
3
$\begingroup$

As you’ve observed, in the demonstration problem there really isn’t any need for the two-step approach; he’s recommending it with an eye towards messier problems of the same kind.

In general we have a congruence $x\equiv a\pmod m$, and what we actually want is $x\equiv b\pmod m$. With small $a,b$, and $m$ we can use trial and error to find $c$ such that $ac\equiv b\pmod m$ just about as easily as we can use it to find $c$ such that $ac\equiv 1\pmod m$. Then we can multiply $x\equiv a\pmod m$ by $c$ to get $cx\equiv ac\equiv b\pmod m$, and $cx$ is the number that we wanted. That’s what you’re doing when you notice that if $a=3$ and $b=2$, we can take $c=2$ and get the desired result.

If, however, $a,b$, and $m$ are larger, as in the example that he mentions at the end of the video, trial and error can be painful. Fortunately, it turns out that there’s a rather simple mechanical procedure, the extended Euclidean algorithm, for finding $c$ such that $ac\equiv 1\pmod m$ without any trial and error. When you have that, you know that $cx\equiv 1\pmod m$, and the final step of multiplying by $b$ to get $bcx\equiv b\pmod m$, is trivial.

In other words, the two-step procedure that he recommends replaces what could be a long process of trial and error with a straightforward algorithmic step, something that can be done mechanically with considerable efficiency, followed by a simple multiplication.

$\endgroup$
  • 1
    $\begingroup$ Thus spoke @zarathustra. $\endgroup$ – Daniel W. Farlow Feb 14 '15 at 8:42
  • $\begingroup$ @crash: No, no, no: Also sprach @zarathustra! :-) (Apparently my fingers are more accustomed to typing efficient than to typing efficiency; I’m glad that someone caught it. $\endgroup$ – Brian M. Scott Feb 14 '15 at 8:52
  • $\begingroup$ I saw the opportunity and I had to run with it! :-) This is kind of off-topic, but I thought you might be interested in a question I posted just a little while ago--I thought you might find it interesting given your teaching background. It addresses some very funky calculator behavior. Possibly something to use for a class or two in the future! $\endgroup$ – Daniel W. Farlow Feb 14 '15 at 8:59
  • $\begingroup$ @crash: That is rather strange behavior; I’ll have to take a closer look. Pretty pictures, though! (I confess that I never bothered to learn to use a graphing calculator. My weapon of choice when I needed more than mental arithmetic in the classroom was my trusty old HP-$11$c, which had the added virtue of being almost unborrowable: RPN was completely foreign to the overwhelming majority of students!) $\endgroup$ – Brian M. Scott Feb 14 '15 at 9:08
  • $\begingroup$ Thanks for the response! The unborrowable factor can certainly come in handy! Yes, the behavior completely confounds me simply because of just how many functions seem to be involved. Honestly, I haven't used a calculator myself in quite some time, but I figured it would be fun to get back to some "elementary" things but to spruce them up (if that made any sense--so used to dealing in the abstract I thought it would be nice to "come back down" and toy around with my calculator). Math...such a truly beautiful art. :-) $\endgroup$ – Daniel W. Farlow Feb 14 '15 at 9:12

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.