HW #4 due Friday May 9 (back on schedule)
In the below you're only allowed to discuss gcd using the definition from class, not stuff you might know about it related to e.g. prime factorization. We haven't proven that yet.
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).
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.
3. Prove that nn > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.
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.
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).
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.
3. Prove that nn > n! * 1000 (meaning n * (n-1) * ... * 3 * 2 * 1 * 1000), for all n at least 10.
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.
posted by Allen Knutson @ 6:22 AM
0 Comments:
Post a Comment
<< Home