These solutions use information found in the Reading Section.
1. Beside each step of the following proof, state which definitions and properties of the integers have been used.
Prove that for all integers m, n, p and r, if m < n and p < r, then m + p < n + r.
Proof Suppose that m, n, p and r are integers and m < n and p < r.
| Since | m < n and p < r, | |
| n + (-m) is positive and r + (-p) is positive | by definition of < | |
| (n + (-m)) + (r + (-p)) is positive | by closure of Z+ (observation 1) | |
| [(n + (-m)) + r] + (-p) is positive | by associativity | |
| [n + ((-m) + r)] + (-p) is positive | by associativity | |
| [n + (r + (-m))] + (-p) is positive | by commutativity | |
| [(n + r) + (-m)] + (-p) is positive | by associativity | |
| (n + r) + ((-m) + (-p)) is positive | by associativity | |
| (n + r) + (-(m + p)) is positive | by distributivity (by -1) | |
| Hence | m + p < n + r | by definition of < |
These solutions use information found in pages 112 - 124 of the textbook.
Fill in the blanks to complete the following sentences.
1 and s
1.
D, if P(x) then Q(x)'' is true: Suppose
that for a particular but arbitrarily chosen element of D, P(x) is true.
Show that Q(x) is also true. D, if P(x) then Q(x)'' is false, find a value
of x D for which P(x) is
true and Q(x) is false. You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Prove that there exists an integer which can be written as a product of primes.
2. Prove that for all x{0,1,2,3,4,5},
x2 + x + 41 is a prime number.
3. Prove that for all integers a, b, c and m, if a - b = rm and b - c = sm, then a - c = tm for some integers r, s and t.
4. Prove that for all integers a, b, c and m, if a = d + rm and b = d
+ sm, then a + c = b + c + tm where d, r, s, t Z.
5. On page 121 of your textbook, in the section on Begging the question, an incorrect proof is given of the fact that the product of any two odd integers is odd. Fill in the steps to correctly prove that the product of any two odd integers is odd.
6. Disprove the following statement. If n is an even integer then 1 + 2 + 3 + ... + (n - 1) = kn for some integer k. (Note that this statement is true for odd integers).
To disprove this statement, we need only find ONE value of n (an even integer) for which the statement does not hold.
These solutions use information found in pages 125 - 130 of the textbook.
Fill in the blanks to complete the following sentences.
0.You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Determine the truth values of the following statements (remember your logical connectives from Chapter 1).
a) (0 is rational) L (0.377777... is rational).
b) (
is rational) V (
is rational).
c) " x R, if 3 
x 4
then x is rational.
In Section 3.0 we discussed the properties of the integers. You may wish to refer back to that section and use the properties of the integers to prove the following properties of the rationals.
2. Prove that the product of two rational numbers is a rational number.
3. Prove that every rational number r has an additive inverse.
Not all integers have a multiplicative inverse; in other words if a is an integer, we may not be able to find another integer a' such that a · a' = 1. However, the non-zero rational numbers do have multiplicative inverses.
4. Prove that every non-zero rational number has a multiplicative inverse.
These solutions use information found in pages 131 - 138 of the textbook.
Fill in the blanks to complete the following sentences.
0, then n is divisible by d if, and only if,
n = d·k for some integer k.
) if, and only if, n/d is not an integer.You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. a) Does 4 | 72? Explain.
b) Is 24 a multiple of 48? Explain.
c) Does 0 | 5? Explain.
d) Is -3 a factor of 9? Explain.
2. Suppose a and b are negative integers and a | b. Prove that b a.
3. a) Does 6 | 2a(3b + 3), " a,bZ? Explain.
b) Is 2a(4b + 1) a multiple of 4, "
a,bZ? Explain.
4. Find the unique factorization of the following integers.
a) 5440
b) 43560
5. Suppose that k, a and b are integers. If k | a and k | b , prove that k | (a+b).
These solutions use information found in pages 140 - 146 of the textbook.
Fill in the blanks to complete the following sentences.
r < d. r
< d, n div d = q and n
mod d = r.
b (mod d). Note that this is the
same as saying a - b = kd for some integer k or equivalently d | (a -
b). You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Given the following values for n and d, find integers q and r such that n = d · q +
r and 0 r < d.
a) n = 102 and d = 11.
b) n = -4 and d = 5.
2. Given an amount of money A between 5 cents and 95 cents, the following steps can be used to determine one possible combination of 50 cent (f), 20 cent (t), 10 cent (n) and 5 cent (v) pieces which equal A.
Round the given amount of money to the nearest multiple of five (since we do not have one cent coins). Then evaluate the steps in the order listed.
| f | = | A div 50 |
| B | = | A mod 50 |
| t | = | B div 20 |
| C | = | B mod 20 |
| n | = | C div 10 |
| D | = | C mod 10 |
| v | = | D div 5 |
Use the steps above to find a set of coins which will be equivalent to 95 cents.
3. If a and b are integers such that a = 4x + 1 and b = 4y + 1 for some x,y Z, then prove that the
product a·b is of the the form 4m + 1, for some integer m.
4. Determine whether each of the following statements is true or false.
i) 2 7 (mod
5) ii) 112 12 (mod 9)
iii) 112 7 (mod 3)
5. For positive integers u, v, w, x and d, if u v (mod d)
and w x (mod
d), prove the following two statements.
a) u + w v + x (mod d)
b) u·w v·x (mod d)
These solutions use information found in pages 148 - 153 of the textbook.
Fill in the blanks to complete the following sentences.
R,
the floor of x, denoted 
x
, is defined to be that integer n such
that n x < n + 1.R,
the ceiling of x, denoted 
x
,
is defined to be that integer n such that n - 1 < x n.You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Compute the values of -3.5, 4
and 26/5.
2. Suppose you were working in a job where you were only paid for full hours of work. If you worked for 441 minutes, how many hours of work would you be paid for?
3. Is the following statement true or false? Support your answer by either proving the
statement or giving a counterexample.
x · y = x· y
4. Suppose that n is an even integer. Prove that n / 2 = n / 2.
5. Suppose that n is an odd integer. Prove that n / 2 = n / 2+ 1.
These solutions use information found in pages 154 - 160 of the textbook.
Fill in the blanks to complete the following sentences.
D, if P(x) then Q(x) is $ x 
D such that
P(x) and ~Q(x). D, if P(x) then Q(x). D, if ~Q(x) then ~P(x).You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Prove the following statement by contradiction. For all integers n and all prime numbers p, if n2 is divisible by p, then n is divisible by p.
2. Prove the following statement by contraposition. For all integers n, if n2 is odd, then n is odd.
3. Prove the following statement using your favourite proof technique. The product of any non-zero rational number and any irrational number is irrational.
Proof by contradiction
Proof by contraposition
Why a direct proof doesn't work
These solutions use information found in pages 161 - 165 of the textbook.
You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Prove or disprove the following statements.
a) is irrational.
b) 1 +
is irrational.
2. Theorem 3.7.4 states that the set of prime numbers is infinite but the actual process of determining whether or not a large number is a prime number is very time-consuming. Use the Web to find the largest known prime number. You might like to investigate other facts about prime numbers at http://www.utm.edu/research/primes.
What is the largest known prime number???
These solutions use information found in the Reading Section and on pages 173 - 175 of the textbook.
Fill in the blanks to complete the following sentences.
d.You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
1. Use the Euclidean Algorithm to calculate the gcd of the following pairs of integers.
a) 186, 403
b) 90, 37
c) 36, 102
d) 114, 19
These solutions use information found in the Reading Section.
Fill in the blanks to complete the following sentences.
Z, has a solution if, and only if, gcd(a, b) | c.You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
For each of the following Linear Diophantine equations, determine whether or not a solution exists. If a solution does exist, find one such solution.
1. Find, if they exist, integers x and y which satisfy 91x + 221y = 676.
2. Find, if they exist, integers m and n which satisfy 105m + 56n = -14.
3. Find, if they exist, integers x and y which satisfy 115x + 35y = 11.
Extra Practice Problems
For each of the following Linear Diophantine equations, determine whether or not a
solution exists. If a solution does exist, find one such solution. Once you have finished
all three of these problems, click here to check your
answers.
1. 21x + 15y = 9
2. 158m + 57n = 20000
3. 354a + 258b = 45
The following solutions use information found in the Reading Section.
Fill in the blanks to complete the following sentences.
State Theorem 3.10.1 from the Reading Section.
If x0 and y0 are one solution to the linear
Diophantine equation ax + by = c, where a, b, c Z,
and d = gcd(a, b), then the general solution to the
linear Diophantine equation ax + by = c is given by
x = x0 + (b / d) · t |
and |
y = y0 - (a / d) · t |
where t
Z.
You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.
In the previous section you found one solution to each of the following linear Diophantine equations. For each equation, use the solution you found in the previous section to find the general solution. Then list all solutions which involve only positive integers.
1. Find a formula for all integers x and y, given that x and y satisfy the linear
Diophantine equation 91x + 221y = 676.
List all the solutions which involve positive values for x and y.
2. Find a formula for all integers m and n, given that m and n satisfy the linear
Diophantine equation 105m + 56n = - 14.
List all the solutions which involve positive values for m and n.
Extra Practice Problems
In the previous section you found one solution to each of the following linear Diophantine
equations. For each equation, use the solution you found in the previous section to find
the general solution. Then list all solutions which involve only positive integers. Once
you have finished both of these problems, click here to
check your answers.
1. 21x + 15y = 9
2. 158m + 57n = 20000