# 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 2^{n} - 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 = 2^{n} - 1, so you shouldn't forget to argue that *both* a and b are greater than 1.