CS 173, Fall 2014: Skills list for second examlet
- Number Theory
- Quote back definitions, decide if simple statements
involving them are true, understand the corresponding shorthand
- a divides b, b is a multiple of a,
- x is odd, x is even
- x is prime, x is composite
- x is a perfect square
- x is a rational number
- x and y are relatively prime
- Special cases for divides:
zero is even, zero divides itself
but not any other integer, and every integer divides zero.
- Prime numbers, factoring a number into primes.
(Where we only consider numbers >= 2.)
- Special cases for prime: 0 and 1 are not prime (primes must
be greater than or equal to 2).
- Know the definitions of gcd(a,b) and lcm(a,b) and
be able to compute gcd(a,b) and lcm(a,b) for specific (smallish) values
of a and b.
- Write any (small) positive integer as a product of primes.
- Know that sqrt(2) is not rational.
- Know that there are infinitely many primes.
- Be able to state the Fundamental Theorem of Arithmetic:
Any positive integer can be written as the product of
primes and each integer has only one prime factorization
(except for the order in which you write the factors).
- Define what it means for x and y to be congruent mod k
- Be able to state the "Division Algorithm" theorem.
- Compute the gcd of two larger numbers using the Euclidean algorithm,
i.e. trace the execution of the algorithm. Be able to reproduce
- Prove simple number theory claims using direct proof and the
definitions of the terms involved.
For example, if a divides b and a divides c, then
a divides b+c.
- Logic and Proof techniques.
- Write a simple direct proof, using familiar concepts,
with good mathematical style. Make sure your statements are in logical order,
starting with the given information and ending with what you needed to show.
- Write a proof by cases
- Convert a claim to its contrapositive and prove that using
- Know the following standard ways to approach parts of a proof:
- prove a universal claim by choosing a representative object
of the appropriate type
- prove an if/then statement by assuming whatever's in the
hypothesis and proving the conclusion,
- disprove a universal claim by giving a concrete counterexample.
- prove an existential claim by giving specific values that make
the claim true