(I make no guarantees that this list is complete, but to the best of my knowledge it is. Also, please keep in mind that my statements of the theorems may be slightly different from the text's, since I'm doing this from memory. - CLP)
3.8 - Let m and n be positive integers. A positive integer d is the GCD of m and n if and only if there exist integers x and y such that mx + ny = d.
This is probably the most crucial of the incorrect statements, since we need the salvaged version of this statement for several problems in chapter 4. The "only if" clause of this statement is correct, but the "if" clause is (blatantly) incorrect. By now you should be able to construct a counterexample for the "if" clause. If you can't do this immediately, get out a sheet of paper and think on it for a few minutes. If you work on it for a few minutes and still can't come up with a counterexample, please talk to me immediately.
There are a couple of ways to salvage this statement. One possible salvage was offered by Malcolm:
3.8* (Malcolm) - Let m and n be positive integers, and let d be the GCD of m and n. Then d is the least positive integer that can be written in the form d = mx + ny for some integers x and y.
This statement is correct, and captures the essential information that we need from this theorem (without capturing the parts that made it incorrect). For some of the theorems in chapter 4, you may find the following salvage particularly useful. (I am not sure whether somebody offered this salvage; if you did, I apologize for forgetting about this.)
3.8+ - Let m and n be positive integers, and let d be the GCD of m and n. Let k be an integer. Then there exist integers x and y such that mx + ny = k if and only if d divides k.
In particular, make sure you understand how to apply this modified theorem to solve problem 4.6.
3.10(a) - Let m, n, and d be integers. If d divides mn, then d divides m or d divides n.
This statement is false. Make sure that you are aware of this and can easily construct a counterexample - I have caught several people trying to use this "theorem" on homework problems. The following theorem is the salvage hinted at by the text:
3.10(a)* - Let m, n, and d be integers. If d divides mn and (d, m) = 1, then d divides n.
Make sure you can prove this theorem. You may find 3.9 useful for this.
4.5 - Let a, b, and c be integers, and let m > 1. Then a is congruent to b (mod m) if and only if ac is congruent to bc (mod m).
False. Again, make sure you can construct a counterexample. Several students tried to prove this statement, so I'm not yet convinced that everybody can do this. (The "only if" clause is correct; you need to find a counterexample for the "if" clause.) Recall that in class, we came up with the following salvage:
4.5* - Let a, b, and c be integers, and let m > 1. Assume that (c, m) = 1. Then a is congruent to b (mod m) if and only if ac is congruent to bc (mod m).
Now you should be able to prove the "if" part without much trouble. Try translating the theorem into a statement that doesn't use the language of mods, then see if you can apply a previous theorem.
4.11 - Let a and m be integers. Then a^m is congruent to a (mod m).
False (make sure you can give a counterexample). Most people used Fermat's little theorem to prove this, but forgot that Fermat's little theorem only applies if m is prime, and (a, m) = 1. (However, the current statement holds as long as m is prime, whether a is relatively prime to m or not. You'll need to do a little extra work to show this.)
If you have any questions or comments on this, please feel free to e-mail me. Best of luck studying for this week's exam.