introduce Turing

-------------------------------------------------------------------------------

p > 1 is PRIME if its only positive divisors are 1 and p

   2, 3, 5, 7, 11, 13, 17, 19, 23, ...

-------------------------------------------------------------------------------

Fund Thm of Arithmetic:

For every n >= 1 there EXISTS a UNIQUE product of primes

    p1 p2 ... pj = n   (p1 <= p2 <= ... <= pj)

1 = empty product         15 = 3 * 5 = 1^2 * 3 * 5

-------------------------------------------------------------------------------

Turing's code V1.0

  - Represent message as prime #

     "f  a  l  s  e"
  1  02 01 12 19 05   7
                      ^ pad to make prime

-------------------------------------------------------------------------------

Congruence a == b (mod n) iff n | (a - b)

Ex: 29 == 15 (mod 7) since 7 | (29 - 15)

-------------------------------------------------------------------------------

Congruence mod p partitions integers into p sets
where congruent #'s are in same set.

Ex. p = 3  { ... -6, -3, 0, 3, 6, 9, ... }   #'s like 0 {x | x rem 3 = 0}
           { ... -5, -2, 1, 4, 7, 10, ... }  #'s like 1
           { ... -4, -1, 2, 5, 8, 11, ... }  #'s like 2

   6 == -3 (mod 3)      3 | (6 - (-3))
   6 =/= 2 (mod 3)      3 /| (6 - 2)

-------------------------------------------------------------------------------

SIDEBOARD:

Lemma

  1.  a == a (mod n)
  2.  a == b (mod n) => b == a (mod n)
  3.  a == b (mod n) & b == c (mod n) => a == c (mod n)
  4.  a == b (mod n) -> a + c == b + c (mod n)
  5.  a == b (mod n) -> a c == b c (mod n)
  6.  a == b (mod n) & c == d (mod n) => a c == b d (mod n)

-------------------------------------------------------------------------------

Pf
--

1.  n | 0 => n | a - a => a == a (mod n)
6.  a == b (mod n) => a c == b c (mod n) (by 5)
    c == d (mod n) => b c == b d (mod n) (by 5)
    a c == b c (mod n) (by 3)

-------------------------------------------------------------------------------

SIDEBOARD:

Lemma:

  1. a == (a rem n) (mod n)
  2. a == b (mod n) iff (a rem n) = (b rem n)

Ex:
               by 1
  11 rem 3 = 2 ---> 11 == 2 (mod 3)

                   by 2
  29 == 15 (mod 7) ---> (29 rem 7) = (29 rem 15)
                            = 1         = 1

-------------------------------------------------------------------------------

OPTIONAL

a rem n = a - q n from some q
       n | q n
       n | a - (a - q n)
       a | a - (a rem n)
       a == (a rem n) (mod n)

-------------------------------------------------------------------------------

Lem  If p is prime and p /| k, then there exists an integer k^{-1} in
{1, 2, ..., p 
---

Lemma.  Let p be a prime.  If k is not a multiple of p,
then there exists an integer k^{-1} in {1, 2, ..., p - 1 }
such that:

                k * k^{-1} = 1 (mod p)

Pf.  GCD

-------------------------------------------------------------------------------

Multiplicative inverse of x is a number x^{-1} so:

        x * x^{-1} = 1

DO exist over nonzero reals:            3 * (1/3) = 1
DON'T always exist over integers:       7 * ? = 1
DO exist over integers modulo a prime:  7 * 3 == 1 (mod 5)