CMSC 27100 — Problem Set 3

Instructions

This problem set is due on Friday October 25, 2019 at 23:59. 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. Let $a$ be an integer and $m \gt 2$ be a positive integer. Show that if $a$ has a multiplicative inverse mod $m$, then $\gcd(a,m) = 1$.
  4. Using induction, prove that $3 \mid (n^3 + 2n)$ for every $n \in \mathbb N$.
  5. Show that if $p$ is a prime and $p \geq 5$, then $p = \pm 1 \pmod 6$.
  6. Prove that if $n$ is a positive integer of the form $3m+2$ for a non-negative integer $m$, then $n$ has a prime factor of the same form.

Exercises

  1. Rosen 4.4, Exercises 9-10
  2. Rosen 4.4, Exercises 13-14
  3. Rosen 4.4, Exercises 15
  4. Rosen 4.4, Exercises 17
  5. Rosen 4.4, Exercises 20-22
  6. 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$.
  7. 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$.
  8. Rosen 4.3, Exercises 52
  9. Rosen 4.3, Exercises 54-55
  10. Show that if $n$ is an integer, then $n^2 = 0$ or $1 \pmod 4$.
  11. The Euler Phi function is defined to be $$\varphi(n) = |\{k \leq n \mid \gcd(k,n) = 1\}|,$$ the number of positive integers less than or equal to $n$ which are relatively prime to $n$. Show that $n$ is prime if and only if $\varphi(n) = n-1$.
  12. Rosen 5.1, Exercises 5-7
  13. Rosen 5.1, Exercises 13-16