# Homework

When doing your homework, I encourage you to use the Elements of Style of Proofs as a reference.

## Daily Homework

The following assignments are to be turned in at the end of the indicated class period. I reserve the right to modify the assignment if the need arises. These exercises will form the basis of the student-led presentations each day. Daily assignments will be graded on a $\checkmark$-system.

*Note:* On each Daily Homework, please write (i) your name, (ii) name of course, and (iii) Daily Homework number.

**Daily Homework 1:**Read the syllabus, Chapter 0 (you can safely skip the Acknowledgements), and Chapter 1 up to page 10 (don't worry too much about the definition of conguent modulo $n$) of the textbook. In addition, complete 1.1, 1.2, 1.3, 1.4, 1.6 (Due Thursday, February, 3).**Daily Homework 2:**Read definition of conguent modulo $n$ and pages 11-12. In addition, complete 1.7, 1.8, 1.11, 1.12, 1.14, 1.15 (Due Tuesday, February 8).**Daily Homework 3:**Read pages 12-16 (up to and including 1.27) and complete 1.17, 1.18, 1.25, 1.26, 1.27 (Due Thursday, February 10).**Daily Homework 4:**Read pages 16-18 (up to and including 1.35) and complete 1.28, 1.29, 1.30, 1.31, 1.32, 1.33, 1.35 (for this last one, think about it and jot down some ideas) (Due Tuesday, Feburary 15).**Daily Homework 5:**Read pages 18-19 (up to and including 1.40) and complete 1.34, 1.36, 1.37, 1.38, 1.39. 1.40 (Due Thursday, February 17).**Daily Homework 6:**Read pages 19-20 (up to and including 1.45) and complete 1.41, 1.42, 1.43, 1.45 (Due Tuesday, February 22).**Daily Homework 7:**Spend some time reviewing what we've done so far, read pages 20-25, and complete 1.48, 1.51 (Due Thursday, February 24).**Daily Homework 8:**Read pages 27-32 and complete 2.1, 2.7, 2.8, 2.9 (Due Tuesday, March 1).**Daily Homework 9:**Read the section on "Applications of the Fundamental Theorem of Arithmetic" on pages 32-35 and complete 2.12, 2.13, 2.14, 2.19, 2.21 (Due Thursday, March 3).**Daily Homework 10:**Read the section on "The infinitude of primes" and complete 2.26, 2.27, 2.32, 2.33 (Due Tuesday, March 8).**Daily Homework 11:**Read the rest of Chapter 2 and complete 2.34, 2.38, 2.46 (Due Tuesday, March 15).**Daily Homework 12:**Read pages 47-48 (from 3.14 through 3.17) and complete 3.14, 3.15, 3.16, 3.17 (Due Tuesday, March 29).**Daily Homework 13:**Read the section on Linear congruences on pages 48-49 and complete 3.18 (any two), 3.19, 3.20, 3.24 (Due Thursday, March 31).**Daily Homework 14:**Read the section on Systems of linear congruences on pages 50-52. In particular, contemplate 3.25 and 3.26. Complete 3.28 and 3.29 (Due Tuesday, April 5).**Daily Homework 15:**Read pages 53-54 and complete 4.2, 4.3, 4.4, 4.6 (Due Thursday, April 7).**Daily Homework 16:**Read page 55 and complete 4.7, 4.8, 4.9, 4.10 (Due Tuesday, April 12).**Daily Homework 17:**Read pages 56-58 and complete 4.13, 4.14, 4.15, 4.18, 4.22 (Due Thursday, April 14).**Daily Homework 18:**Read pages 59-60 and complete 4.27, 4.31, 4.32, 4.33, 4.34. Note that we already know that 4.33 (Fermat's Little Theorem) is true, but the intention of this problem is for you to use 4.32 (Euler's Theorem) to prove it (Due Tuesday, April 19).**Daily Homework 19:**Read Chapter 5 and complete 5.2, 5.3, 5.4 (Due Thursday, May 5).**Daily Homework 20:**Complete the following: Using $p=11$, $q=17$, $E=7$, and $D=23$, decrypt the following message that I have already encrypted:130, 134, 146, 133, 128, 1, 130, 130, 1, 124, 70, 145, 124, 1, 124, 133, 93, 93, 88, 70, 146 You should use the dictionary that is on the RSA handout that I distributed in class.*Note:*I'm using a block length of 2 to keep things simple. In addition, complete 5.7 and 5.8. (Due Tuesday, May 10).

## Weekly Write-ups

In addition to the Daily Homework, you will also be required to submit two formally written proofs each week. You may choose any two *theorems* that were *turned in* during a given week to submit the following Wednesday by 5PM. For example, you may choose any two theorems that were turned in during week 2. These problems are due by 5PM on Wednesday in week 3. Beginning with the second Weekly Write-up, you will be required to type your submission.

*Note:* On each Weekly Write-up, please write (i) your name, (ii) name of course, and (iii) Weekly Write-up number. You should type your Weekly Write-ups using $\LaTeX$, MS Word, OpenOffice/LibreOffice, or Google Docs. If you plan to email me your file, then you should send me a PDF (if you need help with this, please let me know). Furthermore, you should name your file using the following convention:

`WeeklyXLast-Name.pdf`

where you replace "X" with the assignment number and replace "Last-Name" with your actual last name. Please don't put any spaces in your file name.

**Weekly Write-up 1:**Choose any two theorems (anything requiring a proof) from Daily Homework 1 (Due Wednesday, February 9).*Note:*This assignment does not need to be typed.**Weekly Write-up 2:**Choose any two theorems (anything requiring a proof) from Daily Homework 2 and 3 (Due~~Wednesday, February 16~~Friday, February 18).**Weekly Write-up 3:**Choose any two theorems (anything requiring a proof) from Daily Homework 4 and 5 (Due Wednesday, February 23).**Weekly Write-up 4:**Choose any two theorems (anything requiring a proof) from Daily Homework 6 and 7 (Due Wednesday, March 2).- There is no Weekly Write-up due the week of March 7 due to Exam 1.
**Weekly Write-up 5:**In class on Thursday, March 10, I distributed two proofs written by students at Wellesley College to each student. Each proof has a number on top that will be used to identify the author and reviewer. Your task is to peer review both of the proofs that you were given and provide a formal critique. The purpose of this exercise is twofold: (i) experience a formal referee process, and (ii) provide feedback to the author that will improve the quality of their proof writing. Your review should neither be a scathing critique nor filled with false praise. Furthermore, you should point out trends in the work which the author could address to improve their work in the future. You should back up each stated trend with a specific example of that trend from the work. Your comments also shouldn't be entirely negative; you should also address the successes that the author had in constructing and delivering the proof. Again, specific examples which illustrate the successes you list are desirable. Your feedback should include a grade for both mathematical correctness and "style", each graded on a scale of 1-4 whereGrade Criteria 4 the work is perfect 3 the work is nearly perfect, but there are some minor errors 2 the work has at least one significant problem 1 the work doesn't seem to address the question `Review1Last-NameProof-Number.pdf`

`Last-Name`

" with your last name and "`Proof-Number`

" with the appropriate number. You will be graded on the accuracy and thoroughness of your reports. (Due Thursday, March 17 by 5PM)- There is no Weekly Write-up due the week of March 28.
**Weekly Write-up 6:**Choose any two theorems (anything requiring a proof) from Daily Homework 12 and 13 (Due Wednesday, April 6).**Weekly Write-up 7:**Choose any two theorems (anything requiring a proof) from Daily Homework 14 and 15 (Due Friday, April 15).- There is no Weekly Write-up due the weeks of April 18 and April 25 due to Exam 2.
**Weekly Write-up 8:**In class on Thursday, April 28, I distributed two proofs written by students at Wellesley College to each student. Each proof has a number on top that will be used to identify the author and reviewer. Your task is to peer review both of the proofs that you were given and provide a formal critique. The purpose of this exercise is twofold: (i) experience a formal referee process, and (ii) provide feedback to the author that will improve the quality of their proof writing. Your review should neither be a scathing critique nor filled with false praise. Furthermore, you should point out trends in the work which the author could address to improve their work in the future. You should back up each stated trend with a specific example of that trend from the work. Your comments also shouldn't be entirely negative; you should also address the successes that the author had in constructing and delivering the proof. Again, specific examples which illustrate the successes you list are desirable. Your feedback should include a grade for both mathematical correctness and "style", each graded on a scale of 1-4 whereGrade Criteria 4 the work is perfect 3 the work is nearly perfect, but there are some minor errors 2 the work has at least one significant problem 1 the work contains many significant errors and/or doesn't seem to address the question `Review2Last-NameProof-Number.pdf`

`Last-Name`

" with your last name and "`Proof-Number`

" with the appropriate number (without PSUWCNT). For example, if I reviewed #2.10, I would name my file`Review2Ernst2.20.pdf`

. You will be graded on the accuracy and thoroughness of your reports. (Due Tuesday, May 3 by 5PM)**Weekly Write-up 9:**This assignment has three parts. For all three parts, you'll need a partner. If you don't have a partner or don't know who your partner is, let me know as soon as possible (in class, most people selected a partner).**Part 1:**For the first part, I want you to select two distinct primes $p$ and $q$ that are both between 3 to 7 digits in length. You can find a list of the first 10,000 primes here. Using your primes, determine a suitable pair $E$ and $D$ for encrypting and decrypting, respectively. Next, I want you to send your partner (via email) the following information: the product $pq$ and $E$. Do*not*send your partner your primes $p$ and $q$. Please include me on the email that you send to your partner. (Due Tuesday, 5.10.11)**Part 2:**After you receive the product $pq$ and $E$ from your partner, you should pick a phrase that is between 20-40 characters long. Then convert your phrase to blocks of length 2 using the dictionary that is on the RSA handout that I distributed in class. Next, encrypt your phrase using your partner's $pq$ and $E$. Send your partner (via email) your encrypted phrase by sending them a list of your encrypted blocks so that the encrypted blocks are listed in order and separated by commas. Like in Part 1, please include me on the email that you send to your partner. (Due Wednesday, 5.11.11)**Part 3:**For the last part of the assignment, first decrypt the message that your partner sent you using the $D$ that you determined in Part 1. Next, I want you to write up a summary of what happened in each part. In particular, describe how you went about decoding the message that your partner sent you; you can assume that your reader has a passing understanding of how RSA encryption works, but you should also assume that the reader will be interested to see how you went about decoding the message in a "step by step" fashion. The more detail you can provide into the process, the better. (Due Thursday, 5.12.11)

`Weekly9Last-Name.pdf`

`Last-Name`

" with your last name.

## LaTeX Template for Homework

You can find a $\LaTeX$ template for typing up your homework and for typing up peer reviews in my public ScribTeX folder. In this directory you will also find a help file for using $\LaTeX$ with ScribTeX. You can download the entire directory and then if you are using ScribTeX, you can upload the files you are interested in using. Alternatively, you can copy the content of the file and paste it into a new tex file.

For a rough overview of some of the basics of $\LaTeX$, you might find the Quick LaTeX Guide useful.