Feedback on hw 9

Problem 6.5

Remember that from gcd (a,b) with a < b, the Euclidean algorithm goes directly to gcd (a, r), where 0 ≤ r < a is the remainder of the division of b by a.

It is true that gcd (a,b) = gcd(a, b - a), and computing the gcd using this method would work, but this is not how the Euclidean algorithm operates.

Problem 6.17

Most of you got this one right.

Problem 6.28

An easy way to solve this was to consider the prime factorization of a and b, and use the fact they are completely disjoint, i.e. no prime appears in both of them. It was also possible to give a proof from the definition of dividing and gcd. Be careful when using the definition of dividing though: a divides b if there is an integer k such that b = ka (and not the other way around: a is potentially smaller than b).

Problem 6.35

Except for some off-by-one errors (a few of you gave only n - 1 consecutive non-prime integers), most of you had the correct idea.

Problem 6.39

I went over this in recitation. Most of you correctly wrote that if n is not prime, then 2n - 1 = ab for some integers a and b.

By itself, this doesn't prove anything, since one could have e.g. a = 1 and b = 2n - 1, so you shouldn't forget to argue that both a and b are greater than 1.