4
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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$
    – user37237
    Nov 3, 2017 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, 2017 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, 2019 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, 2019 at 18:47

2 Answers 2

Reset to default
2
$\begingroup$

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
$\endgroup$
6
  • $\begingroup$ Could you please explain the diagrams you drew? $\endgroup$
    – Magne
    Apr 24, 2019 at 16:53
  • $\begingroup$ I expanded on the explanation so that it hopefully explains the diagrams more clearly now. $\endgroup$
    – Magne
    Apr 25, 2019 at 13:38
  • $\begingroup$ Can these examples be tied to the "FizzBuzz" computer programming exercise? $\endgroup$
    – Jasper
    Apr 25, 2019 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, 2019 at 11:57
  • $\begingroup$ @Jasper FizzBuzz is defined terms of modular arithmetic with primes 3 and 5, so: yes! $\endgroup$
    – Adam
    Apr 26, 2019 at 12:02
0
$\begingroup$

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
$\endgroup$
1
  • 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, 2017 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.