Midterm 1 Study Guide

1. Provide definitions for the terms and statements for the theorems:
   1. An integer \(a\) divides another integer \(b\).
   2. Two integers \(a\) and \(b\) are congruent modulo \(n\).
   3. An integer \(d\) is a common divisor of \(a\) and \(b\).
   4. The greatest common divisor of \(a\) and \(b\).
   5. Division Algorithm.
   6. Well-ordering axiom.
   7. \(a\) and \(b\) are relatively prime.
2. State in mathematical terms and either prove or provide a counterexample:
   1. If a number divides two other numbers then it also divides their sum.
   2. If a number divides another number, then it also divides any multiple of that number.
   3. If a number divides the sum of two numbers then it also divides one of them.
   4. If a number divides the product of two numbers then it also divides one of them.
   5. \(1\) divides every number.
   6. Every number is divisible by \(1\).
   7. Every number divides \(1\).
   8. Every number divides \(0\).
   9. Congruence is a transitive relation.
   10. Congruence is a reflexive relation.
   11. Congruence is a symmetric relation.
   12. Divisibility is a symmetric relation.
   13. Divisibility is a transitive relation.
   14. Divisibility is a reflexive relation.
   15. If two numbers are congruent modulo \(n\), then so are their \(k\)-th powers.
   16. Two numbers are relatively prime if and only if we can write \(1\) as a linear combination of them.
   17. \(a\) and \(b\) are both relatively prime to \(n\) if and only if their product \(ab\) also is.
   18. Two numbers can be relatively prime only if at least one of them is even.
   19. Two numbers can be relatively prime only if at least one of them is odd.
   20. If two relatively prime numbers both divide \(n\) then their product also divides \(n\).
   21. If two numbers both divide \(n\) then their product also divides \(n\).
   22. The relation of being relatively prime is reflexive.
   23. The relation of being relatively prime is symmetric.
   24. The relation of being relatively prime is transitive.
3. Prove:
   1. If \(a\) is congruent to \(b\) modulo \(n\), then \(a+c\) is congruent to \(b+c\) modulo \(n\) and \(ac\) is congruent to \(bd\) modulo \(n\).
   2. If \(a\) is congruent to \(b\) modulo \(n\), then \(a-b\) is congruent to \(0\) modulo \(n\).
   3. If \(a\) is congruent to \(b\) modulo \(n\), and \(c\) is congruent to \(d\) modulo \(n\), then \(ac\) is congruent to \(bd\) modulo \(n\) and \(a+c\) is congruent to \(b+d\) modulo \(n\).
   4. For given integers \(n, m\) with \(n\) non-zero, there is at most one pair of integers \(q, r\) with \(r\) in the range from \(0\) to \(n-1\) such that \(m = nq + r\).
   5. If \(a\) divides \(bc\), and \(a\) and \(b\) are relatively prime, then \(a\) must divide \(c\).
4. Be able to follow the algorithm for finding the greatest common divisor of two numbers and express it as a linear combination of those numbers.