Your homework is below. Normally, homework is handed in about once a week.

1. Prove the unproved basic propositions about divisibility.
2. Prove that if \(a\) and \(b\) are coprime, and if \(a|bc\), then \(a|c\). Hint: use the Bezout fact again.
3. Find examples that contradict the facts about coprime integers if \(a\) and \(b\) do share a factor greater than \(1\).
4. Write the GCD of 3 and 4 as a linear combination of 3 and 4 in three different ways. (Hint: trial and error.)
5. Use the Euclidean algorithm to find the gcd of 51 and 87, and then to write that gcd as a linear combination of 51 and 87. Do the same thing for 151 and 187. Find another way to write the gcd of one of these pairs as a linear combination.
6. You can define the gcd of more than two numbers as the greatest integer dividing all of the numbers in your set. So, for instance, \(gcd(20,30,70)=10\). Calculate the gcd of some hard-looking sets of three numbers by listing divisors.
7. Find the gcd of the four numbers 1240, 6660, 15540, and 19980 without Sage.
8. Let \(a\) be a positive integer. What is the greatest common divisor of \(a\) and \(a+1\)? What is the greatest common divisor of \(a\) and \(a+2\)?
9. Prove that if \(a\) and \(c\) are coprime, and likewise \(b\) and \(c\) are coprime, then \(ab\) and \(c\) are coprime.
10. If \(gcd(a,b)=d\) and \(k>0\), prove a formula for \(gcd(ka,kb)\).
11. Define the least common multiple of \(a\) and \(b\) to be the smallest positive number which is divisible by both \(a\) and \(b\). Prove that the least common multiple of \(a\) and \(b\) is \(ab\) precisely when \(a\) and \(b\) are coprime.
12. Prove that if the pairs \(a\) and \(c\), and \(b\) and \(c\), are both coprime pairs, then \(ab\) and \(c\) are also coprime. (One way to do these is using Bezout.)
13. Prove that \(gcd(a,a+2)=1\) if \(a\) is odd and \(gcd(a,a+2)=2\) is \(a\) is even.
14. Find the gcd of 151 and 187 using the Euclidean algorithm, then write it as a linear combination of these two numbers in two different ways.
15. Find the gcd of 500000001 and 5000001 in any way you see fit other than asking someone else.
16. Does the pattern you see in the following interact continue? How would you find a counterexample, how might you prove it?
17. Find the gcd of three four digit numbers, none of which is divisible by ten.
18. Prove, by induction, that if \(c\) divides integers \(a_i\) and we have other integers \(u_i\), then \(c\mid \sum_{i=1}^n a_iu_i\).
19. Try proving the division algorithm, but for \(b<0\).
20. You know the Fibonacci numbers \(1,1,2,3,5,8,\cdots\) where \(f_{n+2}=f_{n+1}+f_{n}\). Try applying the Euclidean algorithm to a pair of consecutive Fibonacci numbers? How long does it take compared to how far you are in the sequence?
21. Try the above exercise again, but with a variant of the Fibonacci numbers where \(f_{n+2}=f_{n+1}+2f_{n}\). This would start \(1,1,3,5,11,21,\cdots\).