Problem 0: Complete the Canvas quiz "PSet 4 - Canvas".

Problem (6 points): Prove that for any three digit positive integer, if the sum of the digits is a multiple of 3, then the number is a multiple of 3. (Hint: if the hundreds digit of $n$ is $a$ and the tens digit is $b$ and the ones digit is $c$, what is $n$ equal to in terms of $a$, $b$, and $c$?)

Problem (18 points): Use the modular arithmetic corollary of the Quotient/Remainder Theorem to prove each of the following:

• For all integers $n$, $n^8 \equiv 0 \pmod{5}$ or $n^8 \equiv 1 \pmod{5}$.
• For all integers $n$, if $6 \mid n^2$, then $6 \mid n$.
  • Is the above statement true if we replace both 6's with 5's? With 7's? With 8's? (You need not prove that your responses are correct.)
  • Find an integer $a$ greater than or equal to 10 so that the statement "for all integers $n$, if $a \mid n^2$ then $a \mid n$" is false. (No proof required.)
  • Make a conjecture about exactly which integers $a \ge 2$ make the statement "for all integers $n$, if $a \mid n^2$ then $a \mid n$" true. (Again, no proof required. Hint: compare the lists of divisors of the $a$ that make the statement true to the lists of divisors of the $a$ that make the statement false.)

Problem (8 points): Prove that, for any integers $n, a, b, c, d$ with $n \ge 2$ and $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, $ac \equiv bd \pmod{n}$.

Problem (8 points): Complete the proof that the Euclidean algorithm is correct by showing that for all integers $a, b$ and $r$, if $b \ne 0$ and $a = b\cdot q + r$ for some integer $q$, then $gcd(b, r) \le gcd(a, b)$.