diff options
| author | Mattias Andrée <maandree@kth.se> | 2016-07-28 22:55:43 +0200 |
|---|---|---|
| committer | Mattias Andrée <maandree@kth.se> | 2016-07-28 22:55:43 +0200 |
| commit | 8092c767cb5f872b62a0cabbef793a08643497db (patch) | |
| tree | 73183a784d48a1b1551d4205f9dda425acee7c1f /doc | |
| parent | Fix small error in solution for [13] The totient (diff) | |
| download | libzahl-8092c767cb5f872b62a0cabbef793a08643497db.tar.gz libzahl-8092c767cb5f872b62a0cabbef793a08643497db.tar.bz2 libzahl-8092c767cb5f872b62a0cabbef793a08643497db.tar.xz | |
φ(−n) = φ(n), φ(1) = 1, φ(0) = 0
Signed-off-by: Mattias Andrée <maandree@kth.se>
Diffstat (limited to '')
| -rw-r--r-- | doc/exercises.tex | 8 |
1 files changed, 6 insertions, 2 deletions
diff --git a/doc/exercises.tex b/doc/exercises.tex index ebf8e91..14123d2 100644 --- a/doc/exercises.tex +++ b/doc/exercises.tex @@ -262,10 +262,13 @@ which calculates the totient of $n$. Its formula is \( \displaystyle{ - \varphi(n) = n \prod_{p \in \textbf{P} : p | n} + \varphi(n) = |n| \prod_{p \in \textbf{P} : p | n} \left ( 1 - \frac{1}{p} \right ). }\) +Note that, $\varphi(-n) = \varphi(n)$, $\varphi(0) = 0$, +and $\varphi(1) = 1$. + \end{enumerate} @@ -671,7 +674,8 @@ So, if we set $a = n$ and $b = 1$, then we iterate of all integers $p$, $2 \le p \le n$. For which $p$ that is prime, we set $a \gets a \cdot (p - 1)$ and $b \gets b \cdot p$. After the iteration, $b | a$, -and $\varphi(n) = \frac{a}{b}$. +and $\varphi(n) = \frac{a}{b}$. However, if $n < 0$, +then, $\varphi(n) = \varphi|n|$. |