Homework Problems Mat 331

Set no. 3, November 26,2003

Due December 8, 2003

1. Find all common solutions ($\mod 12$) (or show that there are none) to
   $$4x+y \equiv 6(\mod 12), \,\,\,\,\,\, x+4y\equiv 9(\mod 12)$$

2. Find all positive integers less than $1000$ which leave the remainder $1$ when divided by $2$, $3$, $5$ and $7$.

3. Find a reduced system $(\mod 20)$ and give $\phi(20)$

4. Show that $3^3 \equiv -4(\mod 31)$ and use this to show that $3^{10} \equiv -6 (\mod 31)$. Use this result and Euler's theorem to show that
   $$3^{341} \not \equiv 3(\mod 31)$$
   and therefore
   $$3^{341} \not \equiv 3(\mod 341).$$

5. Show that if $p$ is a prime, and $a$ is an integer, and $k$ is a nonnegative integer, then
   $$a^{1+k(p-1)}\equiv a(\mod p).$$

6. Find $\phi(n)$ for $n=20, 60, 63, 341$ and $561$.

7. Let $x$ be the smallest positive integer such that $2^x \equiv 1(\mod 63)$. Find $x$ and verify that $x\vert\phi(63)$.