CS212 Problem set 2 - Northwestern University EECS 212

Document Content and Description Below

For each numbered problem, write your solution on a separate page (or pages): you will upload them separately as PDFs. Do not write your name on the PDFs you submit. Read: LLM 2.1–2.3, 5.1–5.3 ... 0. (required to get any points for the problem set) Upload a page with your name and the names of all your collaborators on this problem set. If you did not collaborate at all, write that. 1. (20 points) We will denote the set of positive integers, also called natural numbers, by N. Let n be a composite (i.e., an integer greater than 1 which is not prime) number, and define the set D = {d ∈ N : 1 < d < n and d | n}. This is the set of all natural numbers strictly between 1 and n that also divide n. Let p be the smallest element of D. a. (3 points) Write out what D is for n = 12 and n = 245. b. (5 points) Explain why the “Let p be the smallest element of D” statement is legitimate (in general, not just in your examples). c. (7 points) Prove that p is prime. We suggest using a proof by contradiction, where the statement that you will contradict is that p is the smallest element of D. d. (5 points) Relying on the lemma you have established in (c), write out a complete proof (by descent) of the following proposition. (Feel free to use the proof in lecture, but write it nicely in your own words and complete anything that needs more detail.) Proposition. For all integers n > 1, the following are equivalent: (i) n is prime; (ii) there is no prime [Show More]

Last updated: 2 years ago

Preview 1 out of 3 pages