Math1061/7861 Integers Worksheet With Answers
ADVERTISEMENT
1
2MATH1061/7861
Semester 2, 2008
Assignment Four SOLUTIONS
This assignment is worth 2%. Marked out of 20; marks allocated as indicated.
1. (6 marks)
For all integers a and b, if a + b is even then a and b are either both even or both odd.
Prove this statement (i) directly; (ii) by contradiction.
:
: If integers a and b are both even or both odd, we say that a and b have the same parity.
(i) Direct proof:
Let a, b be any integers, and suppose their sum is even. So a + b = 2k, for some integer k.
Now a is either even or odd.
If a is even then a = 2A for some integer A, and then
b = 2k
a = 2k
2A
= 2(k
A)
= 2
integer,
so b is also even.
If on the other hand a is odd, then a = 2A + 1 for some integer A. In this case,
b = 2k
a = 2k
(2A + 1)
= 2(k
A) + 1
= (2
integer) + 1,
so b is also odd.
Hence if the sum of two integers is even, they are both even integers or else they are both odd
integers (that is, they have the same parity).
(ii) Proof by contradiction:
Assume that integers a and b satisfy a + b is even, but that one of a, b is even and the other
one is odd.
Since a + b = b + a, there’s no loss of generality in assuming that a is even and b is odd.
So say a = 2A and b = 2B + 1 for some integers A and B.
Then a + b = 2A + (2B + 1) = 2(A + B) + 1, which is odd. Contradiction!
Hence our assumption is false, so we can’t have one of a, b even and the other one odd; that
is, a and b must have the same parity (both even or both odd).
2. (4 marks)
For all integers c, d and e, if c d and c e, then c (d + e).
Use proof by contradiction to prove this statement.
:
Proof by contradiction: Note that the negation says
c, d, e
Z so that (c d and c e) and c (d + e).
Assume the negation holds.
Now c d means that d = cx for some integer x.
And c (d + e) means that d + e = cy, for some integer y.
Hence d + e = cx + e = cy, so e = cy
cx = c(y
x), and we have y
x
Z, because x
and y are both integers.
Thus c e, a contradiction.
Hence the negation isn’t true. So the original statement is true.
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education