Homework 1 Post-Write
1. Pythagorean Theorem
Proposition: The square of the hypotenuse of a right triangle is equal to the sum of the squares of the other two sides.
a2 + b2 = c2
Proof: Suppose you have a square with sides (a + b) that has been cut into five pieces: a smaller inscribed square with sides c and four right triangles with sides a, b, and c. The area of the larger square is given by (a + b)2 = a2 + 2ab + b2. The area of the larger square can also be given by the sum of the interior square and the four right triangles: c2 + 4(ab/2) = c2 + 2ab. Since the two areas are equal, we can set them equal to each other and subtract what they have in common.
a2 + 2ab + b2 = c2 + 2ab Subtract 2ab from both sides
a2 + b2 = c2 Pythagorean Theorem

2. Prime Numbers
(a) Proposition: There are infinitely many prime numbers.
Proof: Suppose not. Then, there exists only finitely many prime numbers. We can label these finitely many primes p1, p2, …, pn. Call the product of all these primes plus 1 N.
N = p1* p2* …* pn + 1
N is thus larger than any number in the set p1, p2, …, pn. Since N > pn, and pn is the largest prime number, N is not prime. Therefore, N must be divisible by a positive integer other than itself and 1. Based on the fundamental theorem of arithmetic, it follows that N has some prime factorization. This means one of the numbers in the above list of primes must divide N. Thus, there exists an integer, i with 1 ≤ in so that pi divides N. As pi divides N, and thus the product of all primes, it must also divide N – (p1 * p2* …* pn) = 1. Since pi > 2, it is impossible for pi to divide one. This contradicts the idea that N is not prime so there cannot be only finitely many primes.

(b) Algorithm: First try n + 1, if the returned number is prime, stop there.
If returned number is not prime, plug into the following formula: (2n + 1)
If the returned number is still not prime, add 2 until you reach a prime number
Any number returned by the algorithm satisfies the condition 0 < n < A. As we previously proved there is an infinite number of primes, there will always be an output that is larger than n. A problem with this formula is that it as you begin to input larger numbers, the possibility of encountering a prime number gets larger and larger so you will have to add 2 at an increaisng rate.

n n + 1 prime? 2n + 1 prime? ~ + 2 prime?
0 1 No 1 No 3 Yes
1 2 Yes N/A N/A N/A N/A
2 3 Yes N/A N/A N/A N/A
6 7 Yes N/A N/A N/A N/A
10 11 Yes N/A N/A N/A N/A
17 18 No 35 No 37 Yes
21 22 No 43 Yes N/A N/A
26 27 No 53 Yes N/A N/A
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License