[From previous lecture:
What is the running time of mergesort?]
Compare n, n log n, n^2, n^3, 2^n  for n=10,100,1000,2000

  [Ian: potiential hw problem:
   characterize f(x) = x^k in terms of f(2n) vs f(n)?]



Division

Defn: a|b

Th'm: a|b, a|c ↠ a|(b+c) 
Corrolary: a|b, a|c ↠ a|(b-c) 

For a base d, any integer a can be written
   a=q*d+r   [1]
where r "remainder" is 0 ≤ r < d; call q "quotient".
   q = a div m
   r = a mod m

Self-exercise:
In your favorite programming language, what are the
quotient- and remainder-like functions?
(Some languages have a couple of options which differ
  on negative integers.)
What is a (logic) formula (like [1] above) which captures the relation
  between the functions?
Does real-number (floating-point) division function
  share a name with integer division function in this language?
  (If so, have you ever had a bug regarding this? Was it easy to debug?
   Do you think overloading the name is the best approach to designing
   a language, in this particular instance?  Is operator overloading
   always error-prone like this?  
   Is it the same as polymorphism -- a function "/" defined for numbers
   but then subclassed with specialized behavior for integers?)


Modular arithmetic
Seven o'clock + 6hrs ≡  1 o'clock.
Seven o'clock + 50hrs ≡ 9 o'clock.
This is mod 12 arithmetic (or, mod 12 +1, since
we go from 1..12 rather than 0..11.

Well, 0:00..23:59 back to 0:00

  [Note a 12hr clock inconsistency: 
   midnight = 12:00am, but 1:00am is just after --
   that is, 12am < 1am, even though 12 isn't < 1.
   The off-by-one bug in pop culture, sigh.]


(Using mod 12 to represent months -- a good idea?
  month+num okay, but month*num, month+month etc should be disallowed.)


Congruences:

We say 13 ≡ 1, mod 12.
2 ≡ 14 ≡ 26 ≡ 38 ≡ 2 ≡ -10, mod 12.
  (Other notations: div,mod;   quotient,remainder,  /,% )


a ≡ b mod 12, if 12|(a-b).
This is equivalent to: a mod 12 = b mod 12.

We call this structure "Z/12" or "Z12".
Note that Z/12 partitions Z into 12 "equivalence classes" --
  partition:   disjoint sets which cover the entire space
  equivalence: membership in the set is reflexive,symmetric,transitive
               (similar like equality)

Alternate, equivalent def'n of "mod":
"1  (mod 12)" can be viewed as the entire set {...,-11,1,13,25,...}
   = { 12k+1 | k in N }
Similarly
"10 (mod 12)" can be viewed as the entire set {...,-2,10,22,34,...}

Note that we usually do think of 18 mod 12 as its "canonical representive"
element, 6.  We also say two numbers are congruent if they
are in the same equivalence class, mod m.
We usually stay in [0,m) or (when helpful) (-m,m).

Here's why we can conveniently just consider a representative:

What is 123 (mod 12) + 366 (mod 12)?
What is 57345 - 23423, mod 10?
What is 57345 - 23423, mod  2?

So to add numbers mod n, replace each number with something congruent
(mod n), and do the addition in regular ol' N.
This phrasing of modular-addition raises a question: Is it well-defined?
That is, do we get different answers depending on which elements
a0,b0 we choose congruent to a,b?

Th'm: addition mod 12 is well defined.  Well, we'll phrase this as:
Th'm:  If a≡a0 (mod n), and b≡b0 (mod n),
       then a+b &equiv a0+b0 (mod n).




What is 123*366, mod 12?
What is -2*96, mod 12?
What is -2*97, mod 12?
  All these, mod 2?
   Note: ⟨Z/2,+,*⟩ is isomorphic to ⟨B,xor,and⟩;
       "or" corresponds to "max" (within Z/2).
Note that maxZ/2 isn't the extension of maxZ --
we can't do our same arithmetic.





[Reached here 03.mar.19]
------------------------

Inverses?  Division (that is, the inverse of multiplication) is different!



What is 3^2, 3^4, 3^8 mod 7?
What is 3^13 mod 7?




(Dis)Prove with your neighbor: a*Z/12b ≡ ab mod 12.
is well-defined.

(Dis)Prove with your neighbor: a^Z/12b ≡ a^b mod 12.
is well-defined.

2^3 vs 2^15 mod 12 -- 8 vs 1024*32 ≡ (960+64)*(-4) ≡ 4*(-4) ≡ -4≡8
3^1 vs 3^13 mod 12:  3^13 ≡ 3*3^12≡3*(3^2)^6 ≡ 3*(-3)^6
  ≡ 3*(-3^2)^3 ≡ 3*9^3 ≡ 3*(-3)^3 ≡ 


9^2 ≡ 81 ≡ 12*6+9





Applications: parity check; hash: ssn mod 10^4.



Later: 
gcd, euclid's algorithm, runtime of euclid's alg (needs fibonacci bound)