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

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. triangular number
  3. prime, composite
  4. prime counting function
  5. twin prime
  6. converse
  7. contrapositive
  8. least element
  9. divides, divisor, factor, multiple
  10. even/odd
  11. threven/throdd-one/throdd-two
  12. base $b$ expressions
  13. greatest common divisor, [mutually/pairwise] relatively prime
  14. congruent mod $n$
  15. linear congruence [in one variable]
  16. Diophantine equation
  17. inverse mod $n$
  18. equivalence relation: reflexive, symmetric, transitive
  19. equivalence class and representative of an equivalence class
  20. congruence class mod $n$, $\ZZ/n\ZZ$
  21. Euler's $\phi$ or totient function

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

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 quiz and 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 six out of a collection of eight 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 or computational things to do. These will be similar from homeworks and maxiquizzes.

There will be a total of well more than 100 points worth of problems, but the maximum score you can earn on the test will be 100. You should therefore be able to choose only to do the problems you know best and still earn a full score.