SOME TYPES OF PROOFS YOU SHOULD BE ABLE TO WRITE

· a proof by induction

· a proof using the well-ordering principle

· elementary divisibility, gcd, and lcm properties

· the “ax+by = gcd(a,b)” theorem

· Euclid’s Lemma

· elementary proofs related to prime/composite numbers

· there are infinitely many primes

· there are arbitrarily large gaps between primes

· elementary congruence properties

· if ca ≡ cb (mod n) and gcd(c,n)=1 then a ≡ b (mod n)

· various divisibility criteria (e.g. a number is divisible by 3 iff the sum of its digits is)

· “a” has a multiplicative inverse modulo n iff gcd(a,n)=1

· Various divisibility statements that use Fermat’s Little Theorem

· Wilson’s Theorem and its converse

· Various statements about factorials mod p

· n is prime ↔ τ(n) = 2 ↔ σ(n) = n+1

· n is a square ↔ τ(n) is odd

· various properties of the greatest integer function

· various properties of the φ function

· Euler’s Theorem *** NEW ***