Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MAT 246
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 each page of the Crowdmark. Please note that any mismatch in uploading the pages of the solutions may cause in parts of the solutions not getting marked. 2. Please provide your final, polished solutions in the spaces provided. 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 they are all of equal weight, and 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. 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 Page 1 of 3 MAT 246, PS2 first draft Due: Fri. Mar. 3 Time 10:00 pm. EST - On PS1, unfortunately over %10 of the class did not properly acknowledged the statement below. As a result they lost their PS1 mark. Please note that an acknowledgement is when you sign your name at the bottom of a statement, as a sign of agreement with what the statement is suggesting. 00 If I sign my name on top of a page, what am I acknowledging? 0. Failure to answer this question may result in a mark of 0 on the entire PS2. 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.) Print Name (first, last) : , Signature: Date: 1. (a) We like to solve 51x ≡ 1 (mod 100). Note that 100 is not prime, so we cannot automatically apply cancellation law, as corollaries of chapter 4 guaranteed. Translate this equation to a Diophantine equation, apply Euclidean Algorithm to solve it and determine a solution to the original equation. (b) RSA: read the discussion of RSA on top of page 54, and consider N = 253 and the encrypter E = 9. With this protocol, a person wants to send the message of M = 13, what would they actually send us (R)? And in another occasion someone sends us the message 37. What was their intended message M? 2. a) Read Lemma 7.2.9 and its proof. This proof goes against our vision of transition between chapters because it is using a proof technique from chapter 4! Use Lemma 0 (from the lecture slides week 5 or 6) to give a different proof (a very short proof) of this lemma that uses gcd(s, u) = 1 (Hint: read lemma 7.2.2). (b) prove if a and b are integers and m > 1, and a ≡ b (mod m) and that gcd(a,m) = 1, then gcd(b,m) = 1 as well. (c) Prove that if a is multiplicative inverse of b in mod m then both a and b are relatively prime to m. 3. Consider two natural numbers a and b that are relatively prime. Define the sets Sa and Sb to be the set of all natural numbers (between 1 and a, including 1) that are relatively prime to a and b respectively. Similarly let Sab that is the set of all numbers less than ab which are relatively prime to ab. a) Prove that any number of the form ar + bs, where s ∈ Sa and r ∈ Sb must be relatively prime to ab. b) Conclude from part (a) that φ(a)φ(b) ≤ φ(ab). 4. (a) Prove the following statement in two ways, by applying PMI and by applying PCMI: : with the quantifiers over natural numbers, ∀n∃i∃j such that n = 2i−1(2j − 1), that is, any natural number can be written as the product of powers 2 and the left over, which is an odd number. (b) Prove for each n the choice of (i, j) must be unique. Page 2 of 3 MAT 246, PS2 first draft Due: Fri. Mar. 3 Time 10:00 pm. EST (c) How are the facts in (a) and (b) used to prove the function f : N×N −→ N defined by f(i, j) = 2i−1(2j − 2) is a bijection between N × N and N? What is the interpretation of this bijection in terms of the infinite hotel puzzle? 5. (a) Given that g : A×A −→ A is a bijection, show that the function G : A×A×A −→ A is also a bijection: G(m,n, k) = g(g(m,n), k) for all (m,n, k) ∈ A×A×A (b) Use the idea of part (a) and the previous question, and an argument using mathematical induction to prove for each n ∈ N there must exist a bijection Fn Fn : N× N× · · · × N −→ N between the Cartesian product of number of n copies of N and N. 6. Greek Constructions, Golden ratio, Golden rectangle, Golden Triangle, Construction of 36◦: This question involves reading ahead, some accessible material from chapter 12, and some Greek Constructions. (Please consult Tutorial Week 6 exercise on Greek Construction and read the slides on Greek Construction, posted on the LECTURES module.) (a) Read theorem 12.2.15 and its proof. Replace the proof with a proof using Pythagorean identity applied to triangle MDC. This proof is shorter and does not need theorems 11.3.9 and 11.3.11. (b) Golden Ratio: For positive real numbers a > b the ratio ab is said to be Golden ratio, if a b = a+b a . A rectangle with sides a and b is a golden rectangle. Denote the golden ratio ab by g, and prove that g must be a root of the polynomial x2 − x− 1. Determine the value of g. (c) Golden Rectangle: Start with a precisely drawn square ABEF (read the vertices counterclockwise with A being the lower left vertex) with each side of length 2. Let O be the mid-point of AB. Show that the line segment OE is √ 5, and use Greek Construction to extend the original square to a golden rectangle that you call it ACDF (counterclockwise). Make sure your Greek Construction steps are precisely drawn and documented. (d) Golden Triangle and Construction of 36◦: Consider the isosceles triangle with the angles 36◦ and 72◦ . Let the base be of size b, and let the sides be of size a each. Prove that the ratio ab is a golden ratio (as in part (b)). (Hint: see Theorem 12.4.10.) Use this information, and your Golden rectangle in part (c) to construct a angle of 36 at the vertex A. This consrtruction must be executed in three steps of Greek Construction. Demonstrate your construction, and indicate your steps and explain which rule was used in each step.