The Fundamental Theorem of Arithmetic: every positive integer can be represented as a product of primes.
Integer division produces a quotient and a remainder. For example, three divided by seven equals zero with a remainder of three. Ten divided by seven is one with a remainder of three. Seventeen divided by seven is two with a remainder of three. In modular arithmetic, it's the remainders that are important.
The notation "a | b" means "a divides b."
Theorem 1: If a divides b and a divides c then a divides b + c. If a divides b then a divides bc for all integers c. If a divides b and b divides c, the a divides c.
Definition 2: prime numbers.
Theorem 2: Fundamental theorem of arithmetic: positive integers can be (uniquely) represented as products of primes.
We normally represent integers as polynomials. If one could find a way to implement Theorem 2 in a computer database, factoring large composites of large primes would be a snap. However, it is fairly easy to prove that this approach is infeasible.
Theorem 3: Any composite has a prime divisor <= the number's square root. (Suppose it didn't. Then any pair of the factors multiplied together would be greater than the number.)
Theorem 4 is not really an algorithm, but a formulation of integer division.
Example 7.
Definition 5. Relative primes.
Definition 6. Pairwise relative primes.
Definition 7. Least common multiple.
Theorem 5: ab = gcd(a, b) * lcm(a, b).
Definition 9.
Theorem 6.
Theorem 7.
Example 19: Pseudorandom numbers.
Example 20.
Example 21.