Answers to HW #4

1. We claimed several properties of gcds when stating the Euclidean algorithm. Prove them all:

a. gcd(a,b) = gcd(-a,b) = gcd(a,-b)

b. gcd(0,a) = a

c. gcd(a,b) = gcd(b,a).

A. Let's do (b) first.
Plainly a|0 and a|a, since 0 = 0*a and a = 1*a.
If b|0 (which it always does) and b|a, then b|a.
So we've checked that a is indeed a gcd of 0 and a.

Now (a) and (c). Let g be any of gcd(a,b), gcd(-a,b), gcd(b,a) (as the proofs are similar).
Then g|a and g|b. (If g|-a, then g|a, etc.)
So it is a common divisor.
Now let c be such that c|a and c|b.
Then we argue that c|g. (If g = gcd(b,a) this is easy; otherwise we use c|a <=> c|-a, etc.)
Hence g is a gcd of a and b.

2. Prove gcd is in some sense associative, in that gcd(a,gcd(b,c)) = gcd(gcd(a,b),c) for all a,b,c in Z.

A. Each one boils down to g|a, g|b, g|c, and for any h such that h|a, h|b, h|c, one has h|g.
At that point the proof becomes the same as the one showing that gcds are unique, as we did in class.

3. Prove that nⁿ > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.

A. Check the case n=10 by computer: 10! ~ 3.6 million < 10⁷, so 10! * 1000 < 10¹⁰.
Now assume n>10. We know
(n-1)^n-1 > (n-1)! * 1000 by induction.
Multiply both sides by n:
n * (n-1)^n-1 > n! * 1000
and observe that the left side is smaller than
n * n^n-1 = nⁿ.

4. For all a,b,c, show that gcd(ab,c) | gcd(a,c) gcd(b,c), and give an example where they are unequal.

A. Actually I don't know how to do this without prime factorization; with that it becomes easy.
Really I assigned it to make people appreciate prime factorization once we have it.

For an example, take a=b=c=2. Then it says 2 | 4.