Perimeters of Primitive Pythagorean Triangles - Report

PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES Abstract. This paper examines two methods of determining whether a positive integer can correspond to the semiperimeter of a number of Pythagorean triangles. For all positive integers k, using Bertrand’s Postulate, we can find semiperimeters corresponding to k or more isoperimetrical triangles, and using the Prime Number Theorem, we can find exactly k generator pairs which correspond to a semiperimeter. 1. Introduction Pythagorean triangles are familiar to any high school geometry student. Many could come up with the classic example, a triangle with sides of length 3, 4 and 5. They have likely also come into contact with triangles which have the same perimeter, but different length sides. Less well known are distinct Pythagorean triangles with equal perimeters - and rightly so, since the smallest example of two such Pythagorean triangles share a perimeter of 1716. In this paper, we find methods of determining whether or not a given perimeter can correspond to any Pythagorean triangles, and a way of creating triangles which share their perimeter with an exact number of distinct triangles. The methods are based largely upon the work of A. A. Krishnaswami and Leon Bernstein, from their articles ”On Isoperimetrical Pythagorean Triangles”[6] and ”On Primitive Pythagorean Triangles With Equal Perimeters,”[2] respectively. 2. Generators for a PPT A Pythagorean triple consists of three positive integers, (a, b, c) where c is the largest, such that they can represent the sides of a Pythagorean (or right) triangle. The well-known Pythagorean theorem states that for such triples, a2 + b2 = c2 , where c is the hypotenuse. We call a Pythagorean triple primitive if the three numbers are pairwise relatively prime, that is, no two share a common factor greater than 1. To indicate that two integers a and b are relatively prime, we will use the notation gcd(a, b) = 1. Theorem 1. If (a, b, c) is a primitive Pythagorean triple then one of a or b is even. Proof. It is obvious that a and b cannot both be even for the triple to remain primitive. Assume that both a and b are odd. This means that for some positive 1 2 integers k and j, a = 2k − 1 and b = 2j − 1, and therefore a2 + b2 = c2 (2k − 1)2 + (2j − 1)2 = c2 4k 2 − 4k + 4j 2 − 4j − 2 = c2 Because both a and b are odd, c must be even. Let c = 2i. This gives us: 4k 2 − 4k + 4j 2 − 4j − 2 4k 2 − 4k + 4j 2 − 4j − 4i2 = 4i2 = 2 Now we can factor 4 out of the left side of this equation, but this means that 4 divides 2, which is a contradiction. Therefore a and b cannot both be odd. Thus exactly one must be even, and c must be odd.  A natural place to begin a discussion of Pythagorean triangles is a method of generating these triples. In Euclid’s Elements Book X, Proposition 29, he provides a generator formula for Pythagorean triples. The following formula is a different wording of the same result, and my proof follows the style of Keith Conrad’s expository paper, ”Pythagorean Triples.”[4] Theorem 2. The positive integers a, b, and c (where a is even) form a primitive Pythagorean triple if and only if there exist relatively prime positive integers s and t such that t > s > 0, exactly one is even, gcd(s, t) = 1, and a = 2st, b = t2 − s2 , c = t2 + s2 . Proof. Let (a, b, c) where a is even be a primitive Pythagorean triple. We find that a2 = c2 − b2 = (c + b)(c − b). Because both c and b are odd, c + b and c − b must be even. Using simple algebra,  a 2 c+b c−b = · 2 2 2 Let us prove that (c+b)/2 and (c−b)/2 are relatively prime. It is a common result in number theory that if an integer divides two numbers, it must also divide their sum and difference. Thus if d is a prime divisor of both of these fractions, then it must divide c and b. By assumption, (a, b, c) is primitive, and so c and b are relatively prime. Thus d = 1, and so the fractions (c + b)/2 and (c − b)/2 are relatively prime. Because by definition c is the hypotenuse, and thus c > b > 0, we can see that both (c + b)/2 and (c − b)/2 are positive. Because they are relatively prime and their product is a square, the Fundamental Theorem of Arithmetic indicates that there exist relatively prime positive integers s and t such that c+b = t2 , 2 c−b = s2 . 2 PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES 3 Because we have proved that the fractions equivalent to s2 and t2 are relatively prime, it is clear that gcd(s, t) = 1. Algebraically, it follows that b = t2 − s2 , c = t2 + s2 , and thus a = 2st. It still remains to prove that s and t are not of the same parity. If they were of the same parity, then b and c would both be even, which would contradict the fact that (a, b, c) is primitive. Finally, since b = t2 − s2 > 0, we can conclude that t > s > 0. A proof of the converse is simple. Suppose s and t are positive integers that satisfy t > s > 0, gcd(s, t) = 1, and exactly one is even. We can see then that the given formula generates a primitive Pythagorean triple. a2 + b2 = (2st)2 + (t2 − s2 )2 = t4 + 2s2 t2 + s4 = t2 + s2 = c2 Thus we have a2 + b2 = c2 , but it remains to prove that the triple (a, b, c) is primitive. Assume that it is not primitive, and thus the elements are not relatively prime. Then gcd(b, c) = d 6= 1. Any divisor of b and c must also divide their sum and difference, 2t2 and 2s2 . However, because c is odd, d 6= 2. Because s and t are relatively prime, d must equal 1. This is a contradiction. Therefore, the formulas in Theorem 2 generate a primitive Pythagorean triple.  The next theorem provides a second generating formula which will prove more useful for the purposes of this paper. Theorem 3. The positive integers a, b, and c (where a is even) form a primitive Pythagorean triple, taking c to be the hypotenuse, if and only if there exist relatively prime positive integers u and v such that u < v < 2u, v is odd, and a = 2uv − 2u2 , b = 2uv − v 2 , c = 2u2 − 2uv + v 2 . Proof. Let (a, b, c) be a primitive Pythagorean triple. From Theorem 2, there exist relatively prime integers s and t such that t > s > 0 and exactly one is even, such that the formulas in Theorem 2 hold. Let u = t and v = s + t. Therefore, we have s = v − u, so that a = 2u(v − u) = 2uv − 2u2 b = u2 − (v − u)2 = u2 − v 2 + 2uv − u2 = 2uv − v 2 c = u2 + (v − u)2 = 2u2 − 2uv + v 2 Since s < t, it is clear that t < s + t < 2t, so u < v < 2u, and because t and s are of opposite parity, v must be odd. Because gcd(s, t) = 1, from the way we chose u 4 and v it is clear that gcd(u, v) = 1 as well. Thus we have proven that (u, v) is a generator pair for (a, b, c) with the specified qualities. Next, beginning with relatively prime positive integers u and v such that u < v < 2u and v is odd, we will prove that the formula in Theorem 3 generates a primitive Pythagorean triple. With some algebraic manipulation, we can see that these values satisfy the Pythagorean Theorem: (2uv − 2u2 )2 + (2uv − v 2 )2 (2u2 − 2uv + v 2 )2 = 4u2 v 2 − 8u3 v + 4u4 + 4u2 v 2 − 4uv 3 + v 4 = 4u4 − 8u3 v + 8u2 v 2 − 4uv 3 + v 4 = 4u4 − 8u3 v + 8u2 v 2 − 4uv 3 + v 4 Similarly to the proof of Theorem 2, assume that the triple (a, b, c) is not primitive. Then there exists some positive integer d 6= 1 which divides all three values a, b and c. Thus d must also divide a + c = v 2 and b + c = 2u2 . However, because u and v are relatively prime, d must equal 1. This is a contradiction, and so the triple (a, b, c) must be primitive. This completes the proof.  We will call such a u and v a generator pair. Each primitive Pythagorean triangle corresponds to a distinct generator pair. This is because the matrix   −2 2 0   2 −1 0 2 −2 1 is invertible, and so    a −2    = b  0 c 2 2 2 −2   0 u2   −1 uv  1 v2 gives us a one-to-one mapping to (a, b, c). If there were another generator pair (u0 , v 0 ) which satisfied the above equation, so that      a −2 2 0 u02      2 −1 u0 v 0  b =  0 c 2 −2 1 v 02 then we will have u = u0 and v = v 0 . Thus this generator pair (u, v) is unique, and each primitive Pythagorean triangle is generated by precisely one generator pair. 3. A Discussion of Perimeters We are interested in the perimeters of right triangles which correspond to primitive Pythagorean triples. Using Theorem 3, the perimeter of such a triangle is equal to a + b + c = 2uv where u and v are positive, relatively prime integers that satisfy u < v < 2u and v is odd. Thus an integer must be even for it to possibly be the perimeter of a PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES 5 primitive right triangle. We will deal primarily with the semiperimeter, denoted s, which is defined as half of the perimeter, so s = uv. A positive integer s can be the semiperimeter of a primitive right triangle if and only if it can be factored as s = uv, where (u, v) = 1, u < v < 2u and v is odd. We will be interested in distinct triangles which share a perimeter - such triangles are called isoperimetrical. Because each generator pair corresponds to a distinct primitive right triangle, if we have k generator pairs which correspond to a particular s, then we have k distinct isoperimetrical right triangles with semiperimeter s. It is clear that the conditions √ √ s = uv and u < v < 2u are equivalent to s < v < 2s, hence the number of primitive right triangles with semiperimeter s depends on the number of odd √ √ divisors v of s which are in the interval ( s, 2s). Thus the following definition will be important. Definition 1. Let z be a positive integer. A positive integer n is a unitary divisor of z if n divides z and the integers n and z/n are relatively prime. If z = xy and y √ √ is an odd unitary divisor of z that satisfies z < y < 2z, then we call this product a P -factorization of z and write z = x × y. Note that the order in which the factors x and y are written is important. Counting the number of distinct P -factorizations of s gives the number of primitive right triangles to which s corresponds. The following theorem provides a simple way to check for P -factorizations. Theorem 4. Suppose that z > 1 is a positive integer and that z = xy, where x and y are positive integers. Then z = min{x, y} × max{x, y} is a P -factorization of z if and only if gcd(x, y) = 1, max{x, y} is odd, and the ratio x/y is between 1/2 and 2. Proof. Assume that z = min{x, y} × max{x, y} is a P -factorization of z. Thus max{x, y} is an odd unitary divisor of z, and gcd(x, y) = 1 from the definition of a unitary divisor. Because max{x, y} is a unitary divisor of z, the conditions of Theorem 3 apply, and the ratio x/y comes from the stipulation that u < v < 2u. When x is the larger of the two, we have 1 < x/y < 2, and when x is the smaller, we have 1/2 < x/y < 1. Therefore x/y is between 1/2 and 2. Assume that (x, y) = 1, max(x, y) is odd, and the ratio x/y is between 1/2 and 2, and let z = min{x, y} × max{x, y}. Because max{x, y} divides z and gcd(x, y) = 1, max{x, y} is a unitary divisor of z. It is clear that 1/2 < x/y < 2 gives us √ min{x, y} < max{x, y} < 2 min{x, y}, which is equivalent to z < max{x, y} < √ 2z. Therefore, z = min{x, y}×max{x, y} is a P -factorization of z. This completes the proof.  The following theorem will make use of the greatest integer function, also known as the floor function. Let us define it here. 6 Definition 2. For all x ∈ R, bxc is equal to the largest integer less than or equal to x. The next theorem concerns integers which can and cannot be semiperimeters of primitive right triangles. Theorem 5. The following hold: a. If p is a prime and r is a positive integer, then s = pr is not the semiperimeter of any primitive right triangle. b. If p is an odd prime, then s = p(p + 2) is the semiperimeter of exactly one primitive right triangle. c. If p > 5 is an odd prime of the form 3k + 2, then s = 6p(p + 2) is the semiperimeter of exactly two primitive right triangles. d. Suppose that p is an odd prime and that f is a positive integer. Then s = 2r pf is the semiperimeter of exactly one primitive right triangle if and only if r = blog2 pf c. Proof. The result in part (a) follows from Theorem 3. Because s must be factorizable into the product of two relatively prime integers, it cannot be the power of a single prime. If we factor s = uv as u = 1 and v = pr , it is clear that 1 < pr < 2 does not hold for any prime p. Therefore, s = pr does not have any P -factorizations and cannot correspond to the semiperimeter of any primitive right triangles. For part (b), note that because p is an odd prime, p > 2, and 1 < (p + 2)/p < 2. It is clear that gcd(p, p + 2) = 1 and p + 2 is odd. Because p > 2, 2p < 4p + 4 < p2 + 4p p2 + 2p 2, we know that 2b < p + 2 and p + 2 < pa. This contradicts b < pa < 2b, and so we can rule out s = b × pa. Next, choose u = a and v = pb, and thus a < bp < 2a. However, because a < b, this gives us bp < 2a < 2b, and therefore p < 2. This is a contradiction. Therefore the only P -factorization of s that works is s = p × (p + 2), and so any number of the form p(p + 2) can correspond to only one primitive right triangle. PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES 7 For part (c), we will prove that the only P -factorizations of s are s = 2p×3(p+2) and s = 2(p + 2) × 3p. Note that these are unitary divisors because p is an odd prime of the form 3k + 2, and so p + 2 cannot be divisible by 2 or 3. It is also clear that 2p < 3p + 6 ≤ 4p and 2p + 4 < 3p < 4p + 8, and so by Theorem 4, both are P -factorizations. If p + 2 is prime, these are the only factorizations of s. Suppose p+2 is composite and p+2 = xy, where 5 ≤ x < y < p and gcd(x, y) = 1. Since s = 2 · 3 · x · y · p, there are 25 = 32 unitary divisors of s corresponding to this factorization of p + 2. Half of these divisors involve two or fewer terms: 1, 2, 3, x, y, p, 6, 2x, 2y, 3x, 3y, xy, 2p, 3p, xp, yp By Theorem 4, the ratio of factors in a P -factorization must be between 1/2 and 2. It is clear that p/(p + 2) > 1/2. First note that xy 1p+2 1 1 = < < 6p 6 p 3 2 and therefore by Theorem 4, xy cannot be a factor in a P -factorization of s, because it violates the restrictions on the ratio of factors. All of the terms preceding xy in the list are clearly smaller, and so the ratio of each with its complement in s is smaller than xy/6p. Thus none of the terms preceding xy can be factors in a P -factorization of s either. Since yp xp x2 p x2 p x2 25 > = = > ≥ >2 6x 6y 6xy 6 p+2 12 12 neither xp nor yp can be terms in a P -factorization of s. Therefore the only remaining options are s = 2p × 3(p + 2) and s = 2(p + 2) × 3p, and so there are exactly two P -factorizations of s. Thus for each prime p = 3j + 2, there are two generator pairs which correspond to the semiperimeter s = 6p(p + 2). For part (d), suppose that s = 2r pf is the semiperimeter of a primitive right triangle. Because v must be odd, the only possible P -factorization of s is u = 2r and v = pf . This means that 2r < pf < 2r+1 r b Listing the primes in increasing order, let the nth odd prime be denoted pn . Because Bertrand’s Postulate guarantees the existence of a prime in the interval (n, 2n), we can see that 3 · 5 · 7 · · · pn < 3 · (3 · 2) · (3 · 22 ) · · · (3 · 2n−1 ) = 3n · 2 n(n−1) 2 < (22 )n · 2 = 2 n(n−1) 2 n(n+3) 2 n(n+3) Suppose that s = 3 · 5 · 7 · · · pn . Then, using b as defined above, 2b < s < 2 2 , n(n + 3) and therefore b < . Then, taking rt as defined earlier as the greatest ri , 2 rt > 2(2n−1 − 1) 2n−1 2n−1 − 1 > > 2 . b n(n + 3) n + 3n By choosing a sufficiently large value for n, we can make this larger than any positive integer. Therefore, we can guarantee that there are at least k odd divisors √ √ of s in one of the intervals ( 2i s, 2i+1 s) for 1 ≤ i ≤ b. Thus there exists some i within these parameters such that either s or 2i s is a positive integer which corresponds to at least k isoperimetrical right triangles.  This shows us that for any k ∈ Z+ , we can choose a large enough integer s - that is, an s comprised of sufficiently many primes - that we can guarantee it corresponds to the semiperimeter of at least k isoperimetrical right triangles. By virtue of this ”large enough” s, there must also be infinitely many larger integers 10 s which also correspond to the semiperimeter of at least k distinct primitive right triangles. 5. Semiperimeters Which Correspond to Exactly k Triangles Now that we can guarantee that for all k ∈ Z+ , there exist infinitely many positive integers which correspond to the semiperimeter of at least k distinct right triangles, a natural question is whether it is possible to find integers corresponding to exactly k right triangles. Leon Bernstein’s article [2] describes a way of generating such numbers. The following proof is based on the method he lays out, but expands upon the details. We define the prime counting function π(x), as equal to the number of primes less than or equal to x for any real number x. For example, π(14) = 6 and π(14.17) = 6. By invoking the much stronger Prime Number Theorem, a generalization of Bertrand’s Postulate, we can strengthen our results. The Prime Number Theorem states that π(x) lim x = 1. x→∞ ln x It was proved in 1896 by J. Hadamard [5] and C. de la Vallée Poussin [7] (independently), but the proofs are quite beyond the scope of this paper. As it is quite often used, we will define the function in the denominator as `(x) = x/ ln x. Theorem 7. For each r > 1, lim (`(rx) − `(x)) = ∞ x→∞ Proof. Given an r > 1 and a number x, the Mean Value Theorem guarantees the existence of a point c ∈ (x, rx) such that `0 (c) = `(rx) − `(x) rx − x Note `0 (x) = (ln(x)−1)/(ln x)2 . This function’s derivative is `00 (x) = (2−ln x)/(x ln3 x), which has a critical point at x = e2 . On the interval [e2 , ∞), `0 (x) is decreasing, and so we can say that `0 (c) > `0 (rx), assuming x > e2 . Note that `0 (x) = ln x − 12 ln x ln(x) − 1 1 > = . (ln x)2 (ln x)2 2 ln x Therefore, we can see that `(rx) − `(x) = `0 (c)(rx − x) > `0 (rx)(r − 1)x (r − 1)x > 2 ln(rx) PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES 11 Let us take the limit of this final inequality. lim (r − 1) x→∞ x 2 ln(rx) = = r−1 x lim x→∞ 2 ln rx r−1 1 lim =∞ 2 x→∞ x1 Note that we have used L’Hôpital’s Rule here, because the limit was an indeterminate form. Because `(rx) − `(x) > ((r − 1)x)/(2 ln(rx)), if the limit as x approaches infinity of the right side of the inequality is ∞, the limit of the left must also be ∞.  Theorem 8. For all k ∈ Z+ and for each r > 1, there exists a positive integer N (r, k) such that for each x ≥ N (r, k) there exist k prime numbers between x and rx. Proof. To prove this theorem, we examine lim x→∞ π(rx) − π(x) . First, note the fol`(rx) − `(x) lowing: `(rx) lim x→∞ `(x) rx = lim lnxrx x→∞ ln x ln x = r lim x→∞ ln r + ln x = r π(rx) − π(x) is equal to 1, we will be able to approximate π(rx) − π(x) `(rx) − `(x) by the function `(rx) − `(x). If lim x→∞ π(rx) − π(x) lim x→∞ `(rx) − `(x) π(rx) `(rx) π(x) · − `(rx) `(x) `(x) = lim x→∞ `(rx) −1 `(x) By the Prime Number Theorem, we know that lim π(x)/`(x) = 1. Thus using x→∞ this result and our previous limit, we can see that lim x→∞ π(rx) − π(x) r−1 = = 1. `(rx) − `(x) r−1 Now it is clear that Theorem 8 follows from Theorem 7. Because lim (`(rx) − `(x)) = ∞, it follows that lim π(rx) − π(x) = ∞ as well. Thus x→∞ x→∞ by the definition of the limit, for any k ∈ Z+ and for each r > 1, there exists N (r, k) > 0 such that π(rx) − π(x) > k for all x ≥ N (r, k). Equivalently, there exist k primes in the interval (x, rx).  This is a generalization of Bertrand’s Postulate, which states that N (2, 1) = 2 that is, there is one prime in the interval (x, 2x) for all x ≥ 2. 12 The following method for choosing an s which corresponds to exactly k primes comes from Bernstein’s article. He provides a way to build s such that there are exactly k possible generator pairs, which he explicitly describes. Theorem 9. For each positive integer k ≥ 3, there exists a positive integer Mk with the following property: for each n ≥ Mk there exist primes p1 , p2 , . . . , pk and q such that n < p1 < p2 < · · · < pk < 4 n, 3 k k 1 Y 2 Y p < q < pi . i p21 i=1 p2k i=1 Proof. From Theorem 8, if we choose r = 43 and x = n, then we are ensured that for some N (4/3, k), there exist k primes in the interval (n, 43 n) for all n ≥ N (4/3, k). Similarly, to guarantee the existence of q, we can newly apply Theorem 8 for new p2 p3 · · · pk n and r values. Because we have already chosen our k primes, we let x = . p1 By Theorem 8, for every real number r > 1, there is a corresponding integer N (r, k) such that for every x ≥ N (r, k), there exists a prime in the interval (x, rx), or in our case,   p2 p3 · · · pk p2 p3 · · · pk ,r . p1 p1 If we can show that r(p2 p3 · · · pk )/p  1 < 2(p1 p2 · · · pk−1 )/pk , then we see that our p2 p3 · · · pk p2 p3 · · · pk interval ,r is a subinterval of the desired interval, and so p1 p1 there exists a prime q such that p2 p3 · · · pk p1 p2 · · · pk−1 p1 p2 · · · pk q (p1 p2 · · · pk )2 = p22 p23 · · · p2k p21 ≥ v2 u > v which is a contradiction, and so q cannot divide u. Therefore it must divide v. We can see that if u contains none of the primes pi , v will be much too large to satisfy u < v < 2u. If u contains all of the primes, then v=q<2 p1 p2 · · · pk−1 < p1 p2 · · · pk = u, pk which cannot be true. So u can neither contain all nor none of the primes. The question is, how many of the pi divide u? Assume that u contains m > 1 such primes, where m is a positive integer such that 1 < m < k. Let xi denote some pi , 14 not necessarily in order. Then u = x1 x2 · · · xm and v = (xm+1 xm+2 · · · xk )q. (xm+1 xm+2 · · · xk )q = v p1 p2 · · · pk (xm+1 xm+2 · · · xk ) p21 < 2u = 2(x1 x2 · · · xm ) (x1 x2 · · · xm )(xm+1 xm+2 · · · xk )2 p21 < 2(x1 x2 · · · xm ) (x1 x2 · · · xm )2 p1 2 < 2 < 2u This cannot be true, because even if (x1 x2 · · · xm ) was as small as it could possibly be, that is, the first m primes, then (x1 x2 · · · xm )2 = (p2 p3 · · · pm )2 . p1 2 For m > 1, this is always an integer greater than 2, because each pi is an odd prime. Thus u must contain exactly one prime pi , since it neither contain more than 1 nor 0, and so all generator pairs corresponding to a triangle of semiperimeter s = p1 p2 · · · pk q must be of the form (ut , vt ) as described in Theorem 10 Because all generators are of the form (ut , vt ) and there are k primitive Pythagorean triangles of semiperimeter s which are generated by these pairs, there are infinitely many perimeters which correspond to exactly k primitive Pythagorean triangles.  Theorem 11. Any (u, v) which generates a primitive right triangle with semiperimeter s = qA is of the form (ut , vt ). Proof.  6. Appendix 1: A Proof of Bertrand’s Postulate Bertrand’s Postulate states that if n ≥ 2 is an integer, there is always at least one prime in the interval (n, 2n). The following proof is similar to that of Paul Erdős.[1] In order to prove this statement, several lemmas will be necessary. Lemma 1. For each x ≥ 1, x ∈ R+ , π(x) ≤ 12 (x + 1). Proof. We will prove this result for x ∈ Z+ . The result easily generalizes to all positive real numbers, because for any x which is not an integer, π(x) = π(bxc). Take x to be even. Every alternate integer in the interval [1, x] is even, and there are x integers in the interval. Because 2 is the only even prime and 1 is not prime, we can swap the two, and include 1 in our count of “even” - that is, composite integers in the interval, and count 2 as a possible prime. Thus there are 12 x integers which, by virtue of being even or 1, cannot be prime. On the other hand, if x is odd, π(x) ≤ π(x − 1) + 1, where x − 1 is even. Thus π(x) ≤ 12 (x − 1) + 1 = 12 (x + 1).  PERIMETERS OF PRIMITIVE PYTHAGOREAN TRIANGLES 15 Lemma 2. For any real number x ≥ 1, we have  0, if 0 ≤ x − bxc < 1 ; 2 b2xc − 2bxc = 1, if 1 ≤ x − bxc < 1. 2 Proof. Let us first consider the case when 0 ≤ x − bxc < 21 . 1 2 2bxc ≤2x< 2bxc + 1 bxc ≤ x < bxc + Therefore 2bxc = b2xc, and so b2xc − 2bxc = 0. Similarly, 1 ≤ x − bxc < 1 2 2bxc + 1 ≤ 2x < 2bxc + 2 Therefore b2xc − 2bxc = 1, and thus we have proven the lemma.  1 Lemma 3. The function g defined by g(x) = x− 2 ln(x) is decreasing on the interval [e2 , ∞).   ln(x) 3 Proof. Note that g 0 (x) = x− 2 1 − . The function g has a critical point at 2 x = e2 , and on the interval (e2 , ∞), g 0 is negative. Thus, g is decreasing on the interval [e2 , ∞).    4n 2n Lemma 4. For any integer n > 1, we have < . 2n n Proof. Using the Binomial Theorem, 4n = (1 + 1)2n =  2n  X 2n k=0 k . The first and last terms of this sum are the smallest, with each equal to 1. We can
sum these and, the resulting term will still be the smallest, because 2 < 2n all 1 for
n > 1. Thus we now have a sum of 2n terms, in which the largest term is 2n , so n replacing every term with the largest gives:   2n 4n < (2n) . n   4n 2n Therefore < , as desired.  2n n Q Lemma 5. For each real number x ≥ 2, the inequality p < 4x holds. 1 + 2 m m+1   2m + 1 = m Because 2m + 1 is odd, the mth and the (m + 1)th terms are the same, by the symmetric nature of Pascal’s Triangle. Because every prime in the interval (m + 1, 2m + 1] appears in the numerator

and not the denominator of 2m+1 , each one divides 2m+1 , so we have m m   Y 2m + 1 p≤ . m m+1 logp (2n) are 0, so we are left with µp ≤ logp (2n), and therefore pµp ≤ plogp (2n) = 2n.  Lemma 7. For p > √ 2n,  µp =    2n n −2 . p p 2 Proof. Using the sum from the proof of Lemma  6, because  p > 2n, the first term 2n n is the only nonzero term. For i = 1, we have −2 .  p p Theorem 12. Bertrand’s Postulate: For n ∈ Z+ , n > 1, there exists at least one prime in the interval (n, 2n). Proof. This will be a proof by contradiction. For 2 ≤ n ≤ 127, see Table 1 in the appendix to observe that for each, there is a prime in (n, 2n). Assume that n ≥ 128 is a positive integer for which there are no primes in the interval (n, 2n). Before we begin, note the following important calculations: √ 2n We can use simple algebra to show that 2n < for n > 5. 3 √ Q µp For p , we have p > 2n, so Lemma 7 applies. Therefore 2n/3 √ pµp = 1. Q 2n, from Lemma 7, Y √ 2n