Homework 4

1. (Transitivity rule for modular arithmetic) Let $a$, $b$, $c$, and $n$ be integers, and suppose that $a\equiv b \pmod{n}$ and $b\equiv c \pmod{n}$. Show that $a\equiv c \pmod{n}$.

   Do this in the style of Example 3.3.3, Example 3.3.6, etc., that is, directly from the definitions.

   Note: the problem can also be solved in two lines as follows. The idea is not to do this.

   calc a ≡ b [ZMOD n] := h1
     _ ≡ c [ZMOD n] := h2

2. Let $t$ be an integer for which $t\equiv 2\pmod{4}$. Show that $3(t ^ 2 + t - 8) \equiv 3(2 ^ 2 + 2 - 8)\pmod{4}$.

   Do this in the style of Example 3.3.11, that is by applying the relevant lemmas from Section 3.3 one by one. Note: the problem can also be solved in one line as rel [h]. The idea is not to do this.

   Write this problem only in Lean, not on paper.

3. Let $a$ be an integer for which $a\equiv 3\pmod{5}$. Show that $a^3+4a^2+3\equiv 1\pmod{5}$.

4. Show that there exists an integer $k$, such that $k>50$ and $k\equiv 2\pmod{5}$ and $5k\equiv 6\pmod{8}$.

5. Let $x$ be an integer. Show that $x^5\equiv x\pmod{5}$.

6. Let $n$ be an integer which is divisible by 5 and by 12. Show that it is also divisible by 60.