MPCS 50103 — Problem Set 3

Instructions

This problem set is due on Wednesday January 29, 2020 at 17:00. Solutions to Problems should be submitted on Gradescope and will be graded. Solutions to Exercises will not be graded and you should not submit them, although we will be happy to discuss them with you.

Problems

  1. Solve the following system of equations: \begin{align*} 2x + 7y &= 12 &\pmod{13} \\ 3x + 11y &= 8 & \pmod{13} \end{align*}
  2. Solve the following system of equations: \begin{align*} x &= 2 &\pmod 5 \\ x &= 5 &\pmod 7 \\ x &= 7 &\pmod{11} \\ \end{align*}
  3. Find an expression for $\sum_{i=0}^n i \cdot i!$ and prove that it is correct.
  4. Let $f_n$ denote the $n$th Fibonacci number. Prove that for all $n \geq 1$, $\gcd(f_n, f_{n-1}) = 1$.

Exercises

Number theory

  1. Rosen 4.1, Exercises 15, 35, 37, 41
  2. Rosen 4.4, Exercises 9, 11, 13, 15, 17, 21
  3. Let $m \gt 0$ and consider $+$ on $\mathbb Z_m$. Prove the following:
    1. $+$ is commutative; $\forall a,b a+b = b+a$,
    2. $[0]_m$ is the additive identity; $\forall a, a+0 = a$,
    3. additive inverses exist; $\forall a \exists b, a+b = 0$.
  4. Let $m \gt 0$ and consider $\cdot$ on $\mathbb Z_m$. Prove the following:
    1. $\cdot $ is commutative; $\forall a,b, a \cdot b = b \cdot a$,
    2. $[1]_m$ is the multiplicative identity; $\forall a, a \cdot 0 = a$,
    3. $\cdot$ distributes over $+$; $\forall a,b,c, a \cdot (b+c) = a \cdot b + a \cdot c$.

Induction

  1. Rosen 5.1, Exercises 5, 7
  2. Rosen 5.1, Exercises 13, 15
  3. Rosen 5.1, Exercises 21
  4. Rosen 5.1, Exercises 35, 37
  5. Rosen 5.2, Exercises 7,9
  6. Rosen 5.2, Exercises 42
  7. Rosen 5.3, Exercises 13, 15
  8. Rosen 5.3, Exercises 35, 37, 39, 41

Reflection

Once in a while, there will be a reflection section attached to a problem set. These are meant to give you an opportunity to reflect on your relationship with the course and the things you're learning. I will be reading and responding to your submissions, so this will also allow us to establish a dialogue about your learning in this course.

Completion of this part is optional but is worth an extra 10 marks in total. These will be loosely graded on completion/thoughtfulness and not "correctness" (i.e. what you think I want you to say); you should aim for about a paragraph or two of "thoughtfulness".

  1. The midterm is coming up soon. What are some things that you would like to understand better as you prepare for it?
  2. What are some questions about number theory or mathematical logic that you have? This does not have to be anything that we covered or will cover in class.
  3. Think back to your goals that you set from the first reflection. How do you feel about your progress so far?
  4. Is there anything else you would like me to know at this point?