Discrete and Counting

Ugroups

In this first module about counting modulo, use is made of colour-coding so that the students can get insight in the structure of (abstract) commutative groups.

This notebook is a prerequisite for my material on DFT that will come later.

Some paragraphs use the Euler phi which is introduced in another notebook.

• Ugroups

EulerProgram

The Euler Phi function is reprogrammed from a known result from inclusion-exclusion which can be found in almost all discrete mathematics texts or can be derived from simple counting of elements in the union of 2, 3, 4, ... sets in general position. It is a good first encounter with programming in mathematica.

• Euler Program

RSAExperiment

The RSA text allows students to compute their own encrypted messages. The proof that it actually works involves the little Fermat theorem about (p-1)(q-1) th powers in the case of the groups Un with n = p q. This theorem is not difficult if

- you have studied the Euler phi text

- have seen in the Ugroup text that all "orders" of elements are divisors of the number of elements (either by experimenting, or if a formal proof of Lagrange theorem is already available)

The three notebooks combined can form a basic module in every

• discrete mathematics
• abstract algebra
• number theory
• introductory programming

course.

• RSA Experiments

Examples

Counting Basis

Euler Poly

Factoring

Gambling Shuffles

NonCommunicative Groups

Stirling Number