CMI2022-B: 3

Question

We say that an integer  $a$ is co-prime to another integer $b$ if $\gcd(a, b) = 1$. For any integer $n, \varphi (n)$ is the number of integers from $1$ up to $|n|$ that are co-prime to $n$.

1. Calculate $\varphi (5), \varphi (10)$ and $\varphi (20)$.
2. Show that $\varphi (p) = p – 1$ for any prime $p$.
3. Prove that if $a$ is co-prime to $b$ then the remainder of $a$ when divided by $b$ is also co-prime to $b$.