I want to explain Chinese remainder theorem to master level computer science students. There are two versions of CRT one is number theoretic and second requires the definition of ideals, groups etc. Although students know about these definitions, but I think I should explain these definitions again.

My question is from where I should start and how to motivate them. Should I start with examples or first definition and then example. What are the good examples I should give them. I don't want to confuse my students with lots of symbols and notation. Please note that target audience is master level computer science students.

The name of the course is Algebraic Computation, it is mostly related computational group theory etc.

  • $\begingroup$ A good example to start with and to motivate can be found here: en.wikipedia.org/wiki/Chinese_remainder_theorem and also here: de.wikipedia.org/wiki/Chinesischer_Restsatz (German, but look at the mathematics). $\endgroup$ – Otto Nov 3 '17 at 7:59
  • $\begingroup$ Why do they need to know this? What specific applications do you want to explain to them, if any? Answer this and I think you'll make progress on answering your own question. $\endgroup$ – Will R Nov 4 '17 at 6:02
  • 1
    $\begingroup$ It would be better to call the result "Sun-Ze's theorem", rather than the somewhat bizarre-ethnocentric "Chinese remainder theorem", I think. $\endgroup$ – paul garrett Apr 26 '19 at 13:55
  • $\begingroup$ Do you need to cover the "ideals" version of the theorem? Unless the students are unusually smart and unusually theoretically-oriented, I'd just forget that I ever heard of ideals and teach the number-theoretic version (starting with Fizz-Buzz as in some comments under Adam's answer). $\endgroup$ – Andreas Blass Apr 26 '19 at 18:47

I would start with motivation first. Since these are CS students, it should be an application. You can use anything that would broadly be considered useful. (i.e. not minutiae of your research.) Motivate why you would like a theorem like the CRT before you state it.

Do a few toy cases visually. For example, here are residues modulo 3 and 5:

residues modulo 3 and 5

and here are residues modulo 3 and 6:

residues modulo 3 and 6

Note that not all of the latter's lattice points are hit.

After that, you can dive into computational aspects. Avoid the version with ideals until the end; if you can get them to understand the usual version of the CRT, the principle ideal version should be a homework exercise. i.e. once you know what it means for two ideals to be relatively prime, the proof looks identical to the usual one.

| improve this answer | |
  • $\begingroup$ Could you please explain the diagrams you drew? $\endgroup$ – Magne Apr 24 '19 at 16:53
  • $\begingroup$ I expanded on the explanation so that it hopefully explains the diagrams more clearly now. $\endgroup$ – Magne Apr 25 '19 at 13:38
  • $\begingroup$ Can these examples be tied to the "FizzBuzz" computer programming exercise? $\endgroup$ – Jasper Apr 25 '19 at 19:55
  • $\begingroup$ @Magne I have rejected this edit because it corrected no errors and, quite honestly, you made it sound like I didn't know what the CRT was. $\endgroup$ – Adam Apr 26 '19 at 11:57
  • $\begingroup$ @Jasper FizzBuzz is defined terms of modular arithmetic with primes 3 and 5, so: yes! $\endgroup$ – Adam Apr 26 '19 at 12:02

I assume that these CS students know how to encrypt using RSA. It can be shown that combining RSA with the Chinese Remainder Theorem can speed up the decryption of messages. This might be good motivation with a CS focus.

| improve this answer | |
  • 3
    $\begingroup$ Thanks for the answer it partially answer my question but if possible add more content to the answer to make a full answer. $\endgroup$ – ddd Nov 4 '17 at 5:43

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.