1MAT 246, PS1 Due: Fri. Feb2 Time 10:00 pm. Crowdmark
.
Please note:
1. Ideally the PS must be written in the spaces provided, and page by page, (a picture or scan of individual pages) to be
uploaded to the appropriate pages of a Crowdmark file (link to be posted.) If you wish, you can write your answers
on separate pieces of paper and upload them properly at the allocated page of Crowdmark. Please note that any
mismatch in uploading the pages of the solutions may result in parts of the solutions not getting marked.
2. Please provide your final, polished solutions in the spaces provided. Sometimes the spaces are very small, which
indicates a short solution is possible or expected. Sometimes the break point of a question forces us to leave a large
space, which doesn’t necessarily mean a long solutions is expected. If you have no access to a printer you can write
your solutions on a blank sheet of paper and upload a picture of scan. Remember, it is an art to write a short yet
complete solution; one learns a lot from practicing this art. Please write a complete, even though long solutions.
Then inspect and edit; while editing, ask yourselves:
- am I proving common believes and facts accepted in the literature? If yes, know which facts are common belief
and which ones need an argument.
- can I just quote some of the facts that I tried to prove? This requires a good familiarity with the literature of
the subject (in our case, the textbook and the slides, and earlier questions in the same PS).
- am I introducing too many cases in my proof, and presenting parallel arguments? Change your type of argument
if possible (direct proof versus proof by cases, or proof by contradiction.)
Editing your first complete solution is a very good way of learning. Make sure you have a good solution, then return
to it and reflect on the above questions.
3. Problem set questions contain ideas complementary to the textbook and lecture materials, opportunity for reflection
and deepening on the subject. The level of difficulty of the questions is elementary so that each student has chance
to individually think about the problems. So, please don’t let your “kind" friends take this opportunity away from you!
4. Not all questions will be marked, nor are they all of equal weight. It is not known in advance which questions will
be marked, and how heavy they will be weighed. Therefore if a question is skipped one may lose a larger portion of
the PS mark than one would expect.
5. To receive full mark on the computational questions all the computation details must be provided. For questions
involving proofs there is no need to prove textbook or “slides" proofs but one can simply quote them. When a
theorem is applied the relevance of it to the proof must be made clear.
6. Collaboration in this work is not allowed. You may discuss the idea of a the solutions only, but each person must
write their own solutions completely independently, without knowing or consulting the structure and details of the
argument of another person.
So please be careful not to share any written hint with your friends, because some people have photographic memory,
and then your solutions may become subject to plagiarism. You can give them your general ideas if you wish, but
absolutely no details and format of writing.
7. By participating in this problem set you agree that you are aware of the university regulations regarding plagiarism.
Individual students are expected to organize and write their own solutions independently. During the online teaching,
and while students are connected through email, any assistance to your fellow classmate in the form of a written note
might be directly copied and it may count as a form of plagiarism. Markers are carefully monitoring the solutions,
and any incidence of plagiarism, and all the parties involved will be dealt with according to university regulations.
Please carefully read the item regarding plagiarism in our course outline, and consult the university policies regarding
plagiarism (not knowing the rules is not a good excuse for not obeying them):
http://www.artsci.utoronto.ca/newstudents/transition/academic/plagiarism
2-
0. Failure to answer this question may result in a mark of 0 on the entire PS1. And it is not the name, signature
and date, but it is the acknowledgement .. signing some statement that is intended in this part:
Please sign below as an acknowledgment that you have read the cover page ; (unsigned papers shall not be marked.)
If you don’t have access to a printer, please produce the same acknowledgement by hand on a piece of paper. Your name
alone is not an acknowledgement that you are aware of the policies discussed in the cover page.
Print Name (first, last) : , Signature: Date:
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).
A = 5x2yx5y371z2z3z+1