Exercises

1. Prove that if two positive integers divide each other, then they must be equal; i.e., if $a,b \in\mathbb{N}$, $a\vert b$, and $b\vert a$, then $a = b$.

2. Extend the definition of g.c.d. to three elements $a,b,c \in\mathbb{Z}$ and denote it by $gcd (a,b,c)$. Prove that $gcd (a,b,c) = gcd (gcd (a,b),c) = gcd (a,gcd(b,c))$. (Note that $gcd (a,b,c) = 1$ does not imply that $a,b,c$ are pairwise relatively prime.)

3. Show that for $a,b,c \in\mathbb{Z}$ if $a\vert c$ and $b\vert c$, and $gcd (a,b) = 1$, then $ab\vert c$.

4. Suppose $gcd (a,b) = 1$. Show that $gcd (a + b, a - b) = 1$ or $=2$.

5. Prove that the product of any three consecutive integers is divisible by $6 ( =3!)$. Try to generalize this.

6. Show that the set of integers $1^2, 2^2, ..., m^2$ is not a complete residue system modulo $m$ if $m > 2$.

7. Let $a_1, a_2, ..., a_m$ be a complete residue system modulo $m$. Show that, if $gcd (a,m) = 1$, then $aa_1, aa_2, ...aa_m$ is also a complete residue system modulo $m$.

8. Let $a_1, a_2, ..., a_{\phi(m)}$ be a reduced residue system modulo $m$ and let $gcd (a,m) = 1$. Show that $aa_1, aa_2, ..., aa_{\phi(m)}$ is also a reduced residue system modulo $m$.

9. If $gcd (a,m) = 1$ show that there is an integer $b$ such that $ab \equiv 1$ (mod $m$). Also show that $gcd(b,m)= 1$.