Midterm 2 Study Guide

1. Provide definitions for the terms and statements for the theorems:
   1. A number being prime
   2. A number being composite
   3. Fundamental Theorem of Arithmetic
2. State in mathematical terms and either prove or provide a counterexample:
   1. If two numbers are equal modulo \(n\) when multiplied by a third number, then the numbers are equal modulo \(n\).
   2. Every natural number is either prime or composite (but not both)
   3. Every natural number greater than 1 is divisible by some prime number.
   4. A number is prime if and only if all primes not exceeding its square root don’t divide it.
   5. Two distinct primes are relatively prime.
   6. If a prime number divides a product, then it must divide one of the factors.
   7. A power of a number divides the same power of another number if and only if the first number divides the second.
   8. There are natural numbers that solve the equation \(6n^2=m^2\).
   9. If two numbers divide a third, then their product also divides it.
   10. If two relatively prime numbers divide a third, then their product also divides it.
   11. If two numbers have the property that whenever they divide a third number then their product also divides it, then the numbers must be relatively prime.
   12. A prime number either divides another number or is relatively prime to it.
   13. If a number is relatively prime to two other numbers, then it is also relatively prime to their product.
   14. Any two consecutive integers are relatively prime.
   15. If two numbers are relatively prime, any divisors of them are also relatively prime.
   16. If two numbers are relatively prime, any multiples of them are also relatively prime.
   17. For every integer there is a prime larger than it.
3. Prove:
   1. The equation \(ax+by=c\) has a solution in integer \(x,y\) if and only if \(\gcd(a,b)\) divides \(c\).
   2. If \(a x_0 + b y_0 = c\), then all the solutions to the equation \(ax+by=c\) are given by the formulas \(x=x_0+k\frac{b}{\gcd(a,b)}\), \(y=y_0 - k\frac{a}{\gcd{a,b}}\). (Two questions here: that all these pairs are solutions,for every \(k\), and that any solution has this form).
   3. If \(p\) and \(q_1, \ldots, q_n\) are primes and \(p|q_1\cdots q_n\), then there is an \(i\) such that \(p=q_i\).
   4. If \(n>1\) is a number with the property that whenever \(n|ab\) it follows that \(n|a\) or \(n|b\), then \(n\) must be prime.
   5. If \(\gcd(b,c)=1\) then \(\gcd(a,bc)=\gcd(a,b)\gcd(a,c)\).
   6. If \(a'=\frac{a}{\gcd(a,b)}\) and \(b'=\frac{b}{\gcd(a,b)}\), then \(\gcd(a',b')=1\).