MAT 321

Solution to Problem 7 of Homework Assignment #3

7. a) Find a complete system of residues modulo 9 consisting entirely of odd integers.

Solution. The standard complete system of residues, {0,1,2,3,4,5,6,7,8}, contains some even integers. They can each be replaced by adding 9 (or an odd multiple of 9), so one such complete system of residues is {9,1,11,3,13,5,15,7,17}.

b) Show why it is not possible to find a complete system of residues modulo 10 consisting entirely of odd integers.

Solution. The congruence class consisting of all integers congruent to 0 mod 10 (those of the form 10q) are all even, so we can’t select an odd integer from that set.

c) For which positive integers n is it possible to find a complete residue system consisting entirely of odd integers?

Solution. The odd integers. If n is odd, a complete residue system modulo n is {n, 1, n+2, ... , n-2, 2n-1}, and each of the integers in this set is odd. If n is even, this cannot be done, because the integers of the form nq are all even.

d) For which positive integers n is it possible to find a complete residue system consisting entirely of even integers?

Solution. The odd integers again! If n is odd, a complete system of residues modulo n is {0, n+1, 2, n+3, ... , 2n-2, n-1}, and each of the integers in this set is even. If n is even, this cannot be done, because the integers of the form nq+1 are all odd.