Math Proofs

Math 135, Fall 2019, Sample Answers to Homeworks 5 and 6
Homework 5:
Theorem 1. Let a, b, and c be integers, where a and b are not both zero, and c is not zero. Then
gcd(ac, bc) = c · gcd(a, b).
Proof: [Note: As stated, this theorem is not true! If c < 0 it is not possible for gcd(ac, bc) = c · gcd(a, b)
because a greatest common divisor is always positive. I will give a proof that assumes that c > 0.]
Let d = gcd(a, b) and e = gcd(ac, bc). Since d | a and d | b, it follows easily that dc | ac and dc | bc. So,
dc is a common divisor of ac and bc. Since e is the greatest common divisor, we must have dc ≤ e.
We know d can be written as d = ak + b` for some integers k and `, and multiplying both sided by c
gives dc = ack + bc`. We also know that e is the smallest positive integer that can be written in the form
aci + bcj for integers i and j. Since dc can be written in that form, we must have dc ≥ e.
Since dc ≤ e and dc ≥ e, it follows that e = dc, as we wanted to show.
Theorem 2. Let a, b, c ∈ N, If a does not divide bc, then a does not divide b.
Proof: We prove the contrapositive: If a | b then a | bc. This is a theorem that we have previously
proved. [In fact, a | b means b = ka for some integer k. Then bc = bka = a(bk), which means that a | bc.]
Theorem 3. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n).

Proof: Suppose a ≡ b (mod n) and c ≡ d (mod n). Since a ≡ b (mod n), n | (a − b), and (a − b) = kn
for some integer k. Since c ≡ d (mod n), n | (c − d), and (c − d) = `n for some integer `. So, ac − bd =
ac − ad + ad − bd = a(c − d) + d(a − b) = a`n + dkn = n(a` + dk). We see that n | (ac − bd), and therefore
ac ≡ bd (mod n).
Theorem 4. Let r and s be rational numbers. The r + s is rational.

Proof: Suppose that r and s are rational. Since r is rational, we can write r = ab , where a, b ∈ Z and
b 6= 0. Since s is rational, we can write s = dc , where c, d ∈ Z and d 6= 0. Then, r+s = ab + dc = ad cb
bd + bd =
ad+cb
bd .
Since ad + cb and bd are integers and bd 6= 0, we see that r + s is rational.
Theorem 5. For any real number x, one of the numbers x and x − π is irrational.
Proof: Suppose, for the sake of contradiction, that both x and x − π are rational. Since the negative
of a rational number is rational, π − x is also rational. By the previous theorem, x + (π − x) is rational,
because it is the sum of two rational numbers. But x + (π − x) is π, which we know to be irrational. This
contradiction proves that at least one of x and π − x must be irrational.
Homework 6:
1. Prove: If a and b are integers, then (a + b)3 ≡ a3 + b3 (mod 3).

3 3 3 3 2 2
(a + b) − (a + b ) = a + 3a b + 3ab
Proof: Note that + b3 − a3 − b3 = 3(a2 b + ab2 ). So 3 |
(a + b) − (a + b ) , which means by definition that (a + b) ≡ a3 + b3 (mod 3).
3 3 3 3
2. Prove using the contrapositive method: If the product of two integers is odd, then both of the numbers
are odd.
Proof: We prove the contrapositive: If it is not the case that both integers are odd, then the product of
the two numbers is not odd.
Let a and b be two integers that are not both odd. Then at least one of the integers is even. Say, without
loss of generality, that a is even. Then a = 2k for some integer k, and ab = 2kb. This shows that ab is even.
That is, ab is not odd.
3. Prove using proof by contradiction: If a is a rational number and b is an irrational number, then a + b is
an irrational number.
Proof: Assume, for the sake of contradiction, that a + b is rational. Since a is rational, −a is also
rational [since − pq = −p
q ]. We have previously proved that the sum of two rational numbers is rational. So
(a + b) + (−a) is rational. But (a + b) + (−a) = b, and b is irrational, not rational. This contradiction shows
that a + b cannot be rational.
4. Prove using the contrapositive method: If n is an integer and n ≡ 2 (mod 3), then n is not a square.
(Saying that n is not a square means that there is no integer a such that n = a2 .)
Proof: We prove the contrapositive: If n is a square, then n 6≡ 2 (mod 3). Let n be an integer that is
a square, and let a ∈ Z such that n = a2 . We need to show that a2 6≡ 2 (mod 3). Since every integer is
congruent to exactly one of 0, 1, or 2 (mod 3), we can show that for any integer a, either a2 ≡ 0 (mod 3) or
a2 ≡ 1 (mod 3). We use a proof by cases. Using the Division Algorithm, we can write a = 3q + r where q
and r are integers and r is 0, 1, or 2.
In the case a = 3q + 0, we have that a2 = (3q)2 = 3 · 3q 2 . This means 3 | a2 , and a2 ≡ 0 (mod 3).
In the case a = 3q + 1, we have that a2 = (3q + 1)2 = 9q 2 + 6q + 1 = 3 · (3q 2 + 2q) + 1. This means
3 | (a2 − 1), and a2 ≡ 1 (mod 3).
In the case a = 3q + 2, we have that a2 = (3q + 2)2 = 9q 2 + 12q + 4 = 3 · (3q 2 + 4q + 1) + 1. This means
3 | (a2 − 1), and a2 ≡ 1 (mod 3).
So, in any case, one of a2 ≡ 0 (mod 3) or a2 ≡ 1 (mod 3) is true, as we wanted to show.
5. Prove using proof by contradiction: No rational number is a solution of the equation x3 + x + 1 = 0.

(Outline of proof: Suppose x = pq is a solution, where p and q are not both even. Substitute pq into the
equation, and multiply by q 3 to clear the denominator. Now show that the left side of the equation is
odd, which means that it cannot be zero. To show the left side is odd, use a proof by cases.)
Proof: Suppose, for the sake of contradiction, that there is a rational number x = pq such that x3 +x+1 =
0. We can assume that the fraction is in lowest terms so that, in particular, p and q are not both even. We
3
have pq + ( pq + 1 = 0. Multiplying this equation by q 3 to clear the denominators gives us p3 + pq 2 + q 3 = 0.

We show that the left-hand side of this equation is an odd number, and so cannot be equal to zero. This
contradiction will complete the proof.
To show p3 + pq 2 + q 3 is odd, we use a proof by cases. Since we know that p and q are not both even,
the cases are: both p and q are odd, p is odd and q is even, or p is even and q is odd.
In the case where p and q are both odd, then, because the product of odd numbers is odd, we know that
p3 , pq 2 , and q 3 are all odd. Since the sum of odd numbers is odd, it follows that p3 + pq 2 + q 3 is odd.
In the case where p is odd and q is even, we have that p3 is odd and pq 2 + q 3 = q(pq + q 2 ) is even. Since
the sum of an odd number and an even number is odd, p3 + pq 2 + q 3 is odd.
Finally, in the case where p is even and q is odd, we have that q 3 is odd and p3 + pq 2 = p(p2 + q 2 ) is
even. Since the sum of an odd number and an even number is odd, p3 + pq 2 + q 3 is odd.

Math Proofs

Uploaded by

Copyright:

Available Formats

Math Proofs

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Math Proofs

Uploaded by

Copyright:

Available Formats

Math 135, Fall 2019, Sample Answers to Homeworks 5 and 6

Theorem 3. If a ≡ b (mod n) and c ≡ d (mod n), then ac ≡ bd (mod n).

Theorem 4. Let r and s be rational numbers. The r + s is rational.

1. Prove: If a and b are integers, then (a + b)3 ≡ a3 + b3 (mod 3).

5. Prove using proof by contradiction: No rational number is a solution of the equation x3 + x + 1 = 0.

You might also like