Test I Review Sheet for
Colorado State University, Pueblo
Math 319 — Number Theory — Spring 2014

Definitions

You should be able to give careful, complete, formal definitions of — and examples and know theorems involving — the following terms:
  1. [primitive] Pythagorean triple
  2. divides, divisor, factor
  3. even/odd
  4. base $b$ expressions
  5. greatest common divisor, [mutually/pairwise] relatively prime
  6. congruent mod $n$
  7. linear congruence [in one variable]
  8. Diophantine equation
  9. inverse mod $n$
  10. equivalence relation: reflexive, symmetric, transitive
  11. equivalence class
  12. representative of an equivalence class
  13. congruence class mod $n$, $\ZZ/n\ZZ$
  14. Euler's $\phi$ or totient function
  15. prime, composite

Principles, Lemmata, Propositions, Theorems, Corollaries and Algorithms

Please know careful, complete statements of the following:
  1. The Well-Ordering Principle
  2. The First and Second Principles of Mathematical Induction
  3. The Division Algorithm
  4. a Theorem describing $\gcd(a,b)$ as the smallest positive integral linear combination of $a$ and $b$
  5. The [Extended] Euclidean Algorithm
  6. Euclid's Lemma
  7. a Theorem describing how congruence interacts with arithmetic operations
  8. a Theorem telling when linear congruences are solvable and how many solutions they will then have
  9. a Theorem telling when an integer has an inverse mod $n$
  10. The Chinese Remainder Theorem
  11. a Theorem telling the possible relationships of equivalence classes
  12. a Theorem telling the multiplicative property of Euler's totient function
  13. a Theorem telling how large factors must be of a composite number
  14. The Fundamental Theorem of Arithmetic

Things to know how to do

  1. Use the algorithms above.
  2. Find a solution (whose existence is guaranteed by the CRT) to a system in the form of the Chinese Remainder Theorem, given with specific numbers
  3. Proofs like (and including exactly) the homework assignment proofs we've had so far this term.

Format of the test

Be able to state — in full formality and five-part harmony — all the definitions. You will be asked to do so for something like four of the ones listed above. You must also be able to give context, ideas, examples, etc., for each term you define!

You will also be asked to give full and formal statements of the theorems and algorithms mentioned above, as well as an example (or counterexample when some hypothesis is dropped) to which the theorem applies; there will be a choice of four out of six to state, roughly. You will also likely have to use those theorems in proving other statements.

There will then be a choice of about two or three out of five or six proof-y things to do. These will be similar to proofs from homeworks and maxiquizzes.