2 Number Theory I 1.1 Facts about Divisibility The lemma below states some basic facts about divisibility that are not difficult to prove Lemma 1. The following statements about divisibility hold 1. If a b, then a bc for all c. 2. If a b and b c, then a c. 3. Ifa b and a c, then a sb tc for all s and t For all+0, a b if and only if ca cb Proof. Well only prove parts(2 )and(4); the other proofs are similar Proof of (2): Since a b, there exists an integer ki such that ak1= b. Since b c, there exists an integer k2 such that bk2=c. Substituting aki for b in the second equation gives ckik2=c, which implies that a c. Proof of (4): We must show that a b implies ca cb and vice-versa First, suppose a b. This means ak b for some k Multiplying both sides by c gives cak= cb for some k. This implies ca cb c is nonzero, so ak b for some k. This means a/a can divide both sides by c since Now, suppose ca cb. Then cak= cb for some k. We A number p> l with no positive divisors other than 1 and itself is called a prime Every other number greater than 1 is called composite. For example, 2, 3, 5, 7, 11, and 13 are all prime, but 4, 6,8, and 9 are composite. The number 1 is considered neither prime nor composite. This is just a matter of definition but reflects the fact that 1 does not behave like a prime in many contexts such as the Fundamental Theorem of Arithmetic which we ll come to shortly 1.2 When Divisibility Goes Bad As you learned in elementary school, if one number does not evenly divide another, then there is a"remainder" left over. More precisely, if you divide n by d, then you get quotient q and a remainder r. This basic fact is the subject of a useful theorem Theorem 2 (Division Theorem). Let n and d be integers such that d >0. Then there exists a unique pair of integers q and r such that n= gd +r<r<d� | 2 Number Theory I 1.1 Facts About Divisibility The lemma below states some basic facts about divisibility that are not difficult to prove: Lemma 1. The following statements about divisibility hold. 1. If a | b, then a bc | for all c. 2. If a | b and b c | | , then a c. 3. If a | b and a c | | , then a sb + tc for all s and t. 4. For all c = 0, a | b if and only if ca cb. Proof. We’ll only prove parts (2) and (4); the other proofs are similar. Proof of (2): Since a | b, there exists an integer k1 such that ak1 = b. Since b c | , there exists an integer k2 such that bk2 = c. Substituting ak1 for b in the second equation gives ak1k2 = c, which implies that a | c. Proof of (4): We must show that a | b implies ca cb | and vice­versa. • First, suppose a | b. This means ak = b for some k. Multiplying both sides by c gives cak = cb for some k. This implies ca | cb. • Now, suppose ca | cb. Then cak = cb for some k. We can divide both sides by c since c is nonzero, so ak = b for some k. This means a | b. A number p > 1 with no positive divisors other than 1 and itself is called a prime. Every other number greater than 1 is called composite. For example, 2, 3, 5, 7, 11, and 13 are all prime, but 4, 6, 8, and 9 are composite. The number 1 is considered neither prime nor composite. This is just a matter of definition, but reflects the fact that 1 does not behave like a prime in many contexts, such as the Fundamental Theorem of Arithmetic, which we’ll come to shortly. 1.2 When Divisibility Goes Bad As you learned in elementary school, if one number does not evenly divide another, then there is a “remainder” left over. More precisely, if you divide n by d, then you get a quotient q and a remainder r. This basic fact is the subject of a useful theorem: Theorem 2 (Division Theorem). Let n and d be integers such that d > 0. Then there exists a unique pair of integers q and r such that n = qd + r and 0 ≤ r < d