Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
1MAT 246
1. a) Given natural numbers m and n, prove that for all natural numbers k, if m < n, then m+ k < n+ k.
(Note that this is Rule 2 stated in the basics, which you are proving here. You may use Trichotomy
and PMI in your proof.)
b) Prove the converse of part (a). (Note: this is known as Cancellation Law for addition, (so you cannot
use cancellation because you are proving this. Furthermore, this leads to subtraction, so you are not allowed
subtraction in this process either.)
c) For n > 1 the predecessor of n is denoted by n − 1, and satisfies S(n − 1) = n, which, of course,
means (n− 1) + 1 = n. In this question we extend this notion further: for natural numbers n > m we
define n−m to be the natural number solution to the equation x+m = n. Using this definition (and
Trichotomy and transitivity) and given natural numbers k < m < n, prove that n−m < n− k.
d) In part (c) the way we define subtraction was by appealing to existence of a solution to a linear equation.
Prove, by applying WOP that such a solution must exist.
e) Assume distributivity of multiplication over addition for natural numbers, that is a(b+ c) = ab+ ac.
Prove distributivity for subtraction: for natural numbers m < n and k, prove that k(n−m) satisfies
the equation y + km = kn, and hence conclude that k(n−m) = kn− km.
2. We saw (Online Quiz 2) that for natural numbers r < n, and k, and a = nk + r, n ∤ a. We want to prove
a converse to this fact: that is, for any natural numbers n < a such that n ∤ a there is a unique natural
number r < n and a unique natural number k such that a = nk + r. (Hint: your argument must be formal
and using WOP. And here is a set of numbers that can be helpful: S = {a− nq : q ∈ N, and nq < a}.
3. A restricted version of division: recall definition of m|n is that there exists a natural number q such that
n = mq. (Informally, the choice of letter q refers to the word “quotient" is a restricted sense. So, carefully,
in this case this number q can be denoted by nm . Now we use the language of polynomials to express this
idea of “quotient" of two natural numbers: the “quotient" q is the unique solution to mx = n.
a) Prove this solution (whose existence is guaranteed by the assumption m|n) must be unique. That is, if
two numbers q1 and q2 both claim to satisfy this equation, they must be equal.
b) Prove that k nm =
kn
m and
n1
m +
n2
m =
n1+n2
m .
4. Bijections between sets
a) Given natural numbers m < n, give a very short and complete argument that there cannot be a 1-1
function f : {1, 2, . . . , n} −→ {1, 2, . . . ,m}.
b) Given a set of objects A, we say A is finite and of size n if there is a natural number n and a bijection
f : {1, 2, . . . , n} −→ A.
Assume A is a set of size greater than 2, choose u, v ∈ A, and define B = A \ {u, v}. That is, we take
away two elements of A to arrive at the new set B (which is a proper subset of A). Prove that B is
now of size n− 2 (that is, prove there is a bijection g : {1, 2, . . . , n− 2} −→ B. (Note: this g must be
defined based on the given bijection f which witnesses the assumption that |A| = n).
3c) Conclude that the there can be no bijection between the two sets A and B.
5. Mathematical Induction
a) This is a variation of Pythagorean identity: prove using mathematical induction that for any natural
number n, there are natural numbers a, b such that 5n = a2 + b2. (Note: case of n = 2 is the famous
instance of Pythagorean identity).
b) This question is not about induction, but it is relevant to techniques of chapter 2 and it is relevant to chapter
7. Given two natural numbers a and b, we define the set S = {an+ bm : n,m ∈ Z, an+ bm > 0}.
Show that S ̸= ∅ and applying the WOP to S we let d be the least elements of S. Prove that d|a (and
of course similar argument can show d|b as well). (So d would be a common divisor of a and b,) continue
to show that if c is any common divisor of a and b then c|d, and therefore c ≤ d. This makes d the
greatest common divisor of a and b.)
6. Modular Arithmetic
a) Apply modular arithmetic (not induction) to prove 7 divides 3n+1− 22n+52n+1 if and only if n is even.
b) Find the remainder when 37 · 16!− 175399 is divided by 17. (Note: it is expected that this question is
done using methods of chapter 3 only).
c) What is the remainder of the following number when divided by 13? (Note: the letters x, y, z are
unknown digits (ranging from 0 to 9), and you must show all the details of your calculations).