204211-src-51-1

Planed

• การนับ
  • นับเบื้องต้น เส้นตรง, วงกลม, nCr, nPr
  • inclusion-exclusion techniques
    • bijections
  • advanced counting (placing rods)

• Proof Techniques
  • logics
  • direct proof
  • indirect proof
  • proof by contradiction

• Advanced proof techniques
  • mathematical induction
    • basic induction
    • strong induction
    • examples used: tiling, placing dominoes, induction on matrices, Fibonacci numbers
    • recursive thinking $
  • Pigeon-Hole Principle $
  • diagonalization

• Number theory
  • divisibility
  • congruence
  • gcd, extended gcd
  • modular arithematics
  • Fermat's Little Theorem
  • polynomials $
  • secret sharing, coding $
  • RSA $

$ --- absence, to be covered

Actual

10 ส.ค. 51

• • review basic induction & counting.
  • inclusion-exclusion principles.
  • using bijection in counting. (without actually define what a bijection is)
    • a bijection between subsets and bitstrings
    • a bijection between odd-sized subsets and even-sized subsets
      • gave out idea of the bijection without proof: will be in homework
    • proof of the inclusion-exclusion principle (sketch)

17 ส.ค. 51

• • diagonalization
  • advanced counting: placing rods

24 ส.ค. 51

• • review of modular arithmatics
    • basic identities
    • if $\gcd(a,b)=1$ then $a^{-1}{\pmod {p}}$ exists.
      • the proof didn't use the fact that a pair $x,y$ such that $ax+by=\gcd(a,b)$ exists
  • RSA, Euler's Theorem, and Fermat's Little Theorem (without proofs)
  • TODO: (Homework) RSA by hand, Proof of Fermat's Little Theorem
  • NEXT: Proof of Euler's Theorem and correctness of RSA