You are welcome to discuss homework assignments with others, but you must write the solutions by yourself, in your own words. Those words should be clear, grammatical, and (as far as
possible without sacrificing rigor/clarity) concise.
On homework assignments (and tests), you are free to use any theorem that was discussed in class, in the textbook sections that we have covered, or on a homework assignment.
Practice problems
You don’t need to turn in solutions to the following textbook problems, but you should try all of them.
Section 1.1: 2, 5, 7, 8, 9
Section 1.2: 8, 11, 14, 18, 24, 27
Problems to turn in
Suppose n ∈ Z. Let r be the remainder when n2 is divided by 8. What are the possible values of r? (You must prove both that your list contains all possible values and that it does not contain any impossible values – otherwise you could just say that the list 0,1,...,7 definitely contains all the possibilities!)
Suppose a,b ∈ Z with b > Let r be the remainder when a is divided by b. Prove that (a,b) = (b,r).
If a,b,c are nonzero integers, let (a,b,c) denote the greatest common divisor of a, b, and c. [That is, (a,b,c) is the greatest integer which divides all of a, b, and c.] Prove that (a,b,c) = ((a,b),c).
Note: This means that if we have an efficient algorithm to compute the gcd of two integers, then we can efficiently compute the gcd of three integers by using the algorithm twice. In fact, there is such an algorithm, as we’ll see later.
Suppose a,b,c ∈ Z such that a | c and b | c. Prove that ab | c(a,b).
Note: An especially important special case is when (a,b) = 1. In that case, the theorem says that if a | c, b | c, and (a,b) = 1, then ab | c.
Suppose a,b,c ∈ Z such that (a,c) = (b,c) = 1. Prove that (ab,c) = 1.
