MAT102 Lecture 14

• 2
  • $\varphi (6)$ How many numbers less than or 6 are coprime to 6
  • $\varphi (6)=|\{1,5\}|$
  • So $\varphi (6)=2$
  • a)
    • Compute $\varphi (i)$ for $i=1,\dots ,10$
    • $\varphi (1)=|\{1\}|=1$
    • $\varphi (2)=|\{1\}|=1$
    • $\varphi (3)=|\{1,2\}|=2$
    • $\varphi (4)=|\{1,3\}|=2$
    • $\varphi (5)=|\{1,2,3,4\}|=4$
    • $\varphi (6)=|\{1,5\}|=2$
    • $\varphi (7)=|\{1,2,3,4,5,6\}|=6$
    • $\varphi (8)=|\{1,5,7\}|=3$
    • $\varphi (9)=|\{1,2,4,5,7,8\}|=6$
    • $\varphi (10)=|\{\}|=4$
  • b)
    • If $p$ is prime, then $\varphi (p)=p-1$
    • $\varphi (m)=|\{x\in \mathbb{Z}:1\le x\le m,gcd(x,m)=1\}|$
    • So we know that if a number $p$ is prime, then that means that there aren't any elements less than $p$ are co-prime.
    • We can show the examples from above that are prime.
      • $\varphi (2)=|\{1\}|=1$
      • $\varphi (3)=|\{1,2\}|=2$
      • $\varphi (5)=|\{1,2,3,4\}|=4$
      • $\varphi (7)=|\{1,2,3,4,5,6\}|=6$
      • We can see that these are prime numbers and their result from $\varphi (p)$ is $p-1$.

    ---

    • Solution:
      • Clearly every number $x$ satifying $1\le x<p$ is coprime to $p$, so $\varphi (p)=p-1$
  • c)
    • If $p$ is prime and $r>0$, determine $\varphi (p^r)$.
    • If $\varphi (p)=p-1$:
      • Then we have $gcd(x,p)=1$
      • So we can have $\varphi (p^r)$
      • $gcd(x,p^r)=1=d$
      • This means:
        • $x=bd,p^r=ad$ for some $a,b\in \mathbb{Z}$.

    ---

    • If $p$ is prime, then $\varphi (p^r)$ has a factor which is $p$.
    • How many of these factors do we have? We have $p\cdot (r-1)$ co-prime factors.
    • So $\varphi (p^r)=p\cdot (r-1)-1$
    • Let's see if this works:
      • $\varphi (p^r)=p\cdot (r-1)-1$
      • $\{\begin{array}{l}p=7\\ r=2\end{array}$
      • $\varphi (7^2)=7\cdot (2-1)-1$

    ---

    • Solution:
      • $p$ and $p^r$ is not coprime.
      • All multiples of $p$ are not coprime with $p$.
      • Claim:
        • $x$ is not coprime to $p^r⟺x=pk$ for some $k\in \mathbb{Z}$.
      • $⟸$
        • Suppose $x=pk$ for some $k\in \mathbb{Z}$. Then $p\mid x$ and $p\mid p^r$ so $x$ and $p^r$ are not coprime.
      • $⟹$
        • Suppose that $x$ is not coprime to $p^r$. This means they share a prime factor.
        • Let $q$ be a prime factor of both $x$ and $p^r$.
        • Since $q\mid p^r$ then $q\mid p$.
          • $q\mid ab⟹q\mid a$ or $q\mid b$.
          • If two primes divide each other, they must be the same prime.
          • The only prime that divides $p^r$ is $p$.
        • Since $p,q$ are both prime, then $q=p$.
          • $q\mid x⟹\mathrm{\exists }k\in \mathbb{Z},x=qk⟹x=pk$.

      ---

      • So $\varphi (p^r)=p^r-|\{\text{multiples of p}\le p^r\}|$
      • So $\varphi (p^r)=p^r-p^{r-1}$
      • $\varphi (p^r)=p^r(1-\frac{1}{p})$