CS/Math 240: Supplemental Handout on Divisibility and PrimesDalibor Zelen´y2/19/20111 Division AlgorithmThink back to the time you were di v i di n g one numbe r by another at school. At some point, youlearned a procedure for dividing n by some number k. This method gave you a quotient q and aremainder r.Combining n, k, q and r into one eq uat i on gives usn = qk + r where 0 ≤ r < k. (1)For example, 70÷15 = 4 with remainder 10 (notice t hat the remainder is indeed between 0 inclusiveand 15 exclusive), and we can write 70 = 4 · 15 + 10.In fact, there is exactly one pair of q and r that satisfies (1) for any given n and k.Theorem 1. For any integers n and k, there exist unique integers q and r that satisfy (1).Proof. Let n and k be given. We first show that there exists a pair of integers q and r that satisfy(1). Afterwards, we show that if two such pairs exist, say q1and q2, and r1and r2, then q1= q2and r1= r2.Let’s start by sketching a proof that there are integers q and r that satisfy (1). We claim t hatthere is an integer l such that kl < n < k(l + 1). Indeed, take l = ⌊n/k⌋. Then pick q = l andr = n − kl as our integers that satisfy (1). One coul d use induction to prove this more formally.Now we show rigorously that if n = q1k + r1and n = q2k + r2with 0 ≤ r1< k and 0 ≤ r2< k,then q1= q2and r1= r2.Since n = q1k + r1and n = q2k + r2, we have q1k + r1= q2k + r2, which we rewrite as(q1− q2)k + r1= r2. (2)We know that 0 ≤ r2< k, so0 ≤ (q1− q2)k + r1< k (3)We argue by cases that (3) implies q1= q2.Case 1: q1< q2. Since q1and q2are integers, q1− q2≤ −1, so (q1− q2)k ≤ k. But then thefirst inequality in (3) impl i e s that 0 ≤ −k + r1, so k ≤ r1. This contradicts the fact that r1< k, sowe cannot have q1< q2.Case 2: q1> q2. Since q1and q2are integer s, q1− q2> 1, so (q1− q2)k ≥ k. Then the secondinequality in (3) implies that k + r1< k, so r1< 0. This contradicts t he fact that r1≥ 0, so wecannot have q1> q2.Case 3: Since Case 1 or Case 2 cannot happe n, it follows that q1= q2. Then (2) simplifies tor1= r2. This completes the proof b ec aus e we showed that both q1= q2and r1= r2.12 PrimesWe start our discussion of primes by introducing the notion of divisibility.Definition 1 (Divisibili ty). Let n = qk + r wi th 0 ≤ r < k. When r = 0, we say that k divides n,and write k | d to denote this fact. We also say that k is a divisor of n. If r 6= 0, we say that kdoes not divide n, and write k ∤ n.And now we can state what a prime number is.Definition 2. An integer n ≥ 2 is called prime if its only divisors are 1 and n itself. Otherwis e nis called composite, and it has a divisor that is strictly between 1 and n.Recall that every integer can be written as a product of primes. We write the prime factorizationof n as pe11pe22· · · perr, where p1, p2, . . . , prare distinct primes, and the exponents e1, e2, . . . , erarepositive integers.We proved in lecture that every integer has a prime factorization, but include the proof on thishandout for the sake of completeness. As we shall see l at er , the prime factorization is, in fact,unique.Theorem 2. Every integer n ≥ 2 can be written as a product of primes.Proof. We give a proof by strong induction on n.Consider the statement P (n): n can be written as a product of primes. We prove P (2) as thebase case, and show for all n ≥ 2 that P (n) implies P(n + 1).The base case is P(2), and we can indeed write 2 as a product of primes because 2 is a prime.Now we prove the induction step, i.e., (∀n ≥ 2)P (n) ⇒ P (n + 1).Assume that n can be written as a product of primes. We argue by cases.Case 1: n + 1 is prime. In t hi s case, there is nothing to prove.Case 2: n + 1 is not prime. This means that n + 1 has a divisor k such that 1 < k < n + 1.Hence, we can write n + 1 as n + 1 = k · l where k, l ∈ N and 1 < k < n + 1. (This is what it meansfor a numb er to have a divisor; also note that thi s means 1 < l < n + 1.) So now we have n + 1written as a product of two smaller numbers.Since k, l ≤ n, the induction hypothesis implies that b oth k and l have prime factorizations. Letp1, p2, . . . , pr, q1, q2, . . . , qsbe primes, and let e1, e2, . . . , erand f1, f2, . . . , fsbe positive integers.Then we can write the pri me factorizations of k and l ask = pe11pe22· · · perr(4)l = qf11qf22· · · qfrr(5)and combine them in a prim e factorization of n + 1 asn + 1 = kl = pe11pe22· · · perrqf11qf22· · · qfrr, (6)which completes the proof.We remark that in (6), it may happen that there are pairs i ∈ {1, . . . , r} and j ∈ {1, . . . , s}such that pi= qj. We could then combine the factors peiiand qfjjinto pei+fjiso as to get the primefactorization wr i t te n exactly in the format we describe d originally. But this is just a minor detail.2Note that every prime in the prime factorization of n divides n. To see this, suppose n =Qri=1peiiwhere all the piare primes and ei≥ 1 are integers. Then we can rewrite n = pipe11· · · pei−1i· · · perr.We can use this observation and prime factorizations to prove the following theorem.Theorem 3. There are infinitely many primesProof. We argue by contradiction.Suppose there are not infinite l y many primes. Then we can enumerate all the primes asp1, p2, . . . , prfor some integer r.Consider the integern =rYi=1pi+ 1. (7)By Theorem 2, n has a prime factorization pe11pe22· · · pesswhere piis prime and ei≥ 1 is an integer forall i ∈ {1, . . . , s}. Since every prime in n’s prime factorization divides n, and the prime fac tor i z ati onof n consists of at least one pri me (otherwise n would be 1), n has a prime divisor. But we seefrom (7) that no prime divides n because we can wr i t e n = (p1p2· · · pi−1pi+1· …