Answers to Quiz 4

Theorem: For any integers a,b and c, if a2+b2=c2, then at least one of a and b must be even.
Proof: By contradiction. Suppose a,b, and c are integers such that a2+b2=c2 and a and b are both odd. Then there exist integers, k and l,
such that a=2k+1 and b=2l+1. Then a2+b2=4(k2+k+l2+l)+2. On the other hand, consider c. By the QRT with d=2, there exits some integer m such that c=2m or c=2m+1. Then consider c2=4m2 or c2=4(m2+m)+1. In neither case could a2+b2=c2 since the two sides have different remainders after dividing by 4. A contradiction. QED
 

Theorem: If r is a irrational number, then sqrt(r) is also irrational.
Proof by contradiction. Suppose r is an irrational number and sqrt(r) is rational. Then, there exist integers a and b, with b not equal to 0, such that
sqrt(r) = a/b. Then r= a2/b2.  However, since a2  and b2 are integers and b2 is not equal to 0, r is a rational number. This contradicts the assumption that r was irrational. Hence sqrt(r) must be irrational. QED.
 


 

Theorem: Suppose p is an integer at least 2. If 2p-1 is prime then p must be prime.
Proof by contradiction. Suppose p is an integer such that 2p-1 is prime and p is composite. Then there exist integers r and s such that p=rs and 1<r<p and 1<s<p.
Then 2p-1=2rs-1=(2r-1)(2r(s-1) + 2r(s-2)+ 2r(s-3) + ... + 2r(2) + 2r + 1).  Since r and s are both at least 2, each of the factors of 2p-1 are at least 2. Hence 2p-1 is composite. This contradicts the assumption that 2p-1 was prime. Hence p must be prime. QED

You can see thisway to factor by long division. Here is an example. Suppose p=15=3x5.

215-1=23x5-1=(23-1)(2(3x4) + 2(3x3)+ 2(3x2) +  23 + 1)
32768 -1 = 7 x (4098 + 512 + 64 + 8 + 1) = 7 x 4681