Euler Phi Function of Non-Square Semiprime/Proof 1
Jump to navigation
Jump to search
Theorem
Let $n \in \Z_{>0}$ be a semiprime with distinct prime factors $p$ and $q$.
Let $\map \phi n$ denote the Euler $\phi$ function.
Then:
- $\map \phi n = \paren {p - 1} \paren {q - 1}$
Proof
As $p$ and $q$ are distinct prime numbers, it follows that $p$ and $q$ are coprime.
Thus by Euler Phi Function is Multiplicative:
- $\map \phi n = \map \phi p \, \map \phi q$
From Euler Phi Function of Prime:
- $\map \phi p = p - 1$
- $\map \phi q = q - 1$
Hence the result.
$\blacksquare$
Examples
Euler Phi Function of $87$
- $\phi \left({87}\right) = 56$
Euler Phi Function of $91$
- $\map \phi {91} = 72$
Euler Phi Function of $95$
- $\phi \left({95}\right) = 72$
Euler Phi Function of $111$
- $\phi \left({111}\right) = 72$
Euler Phi Function of $1257$
- $\phi \left({1257}\right) = 836$