# Euler totient

(0.001 seconds)

## 1—10 of 13 matching pages

##### 1: 27.16 Cryptography
To do this, let $s$ denote the reciprocal of $r$ modulo $\phi\left(n\right)$, so that $rs=1+t\phi\left(n\right)$ for some integer $t$. (Here $\phi\left(n\right)$ is Euler’s totient27.2).) By the Euler–Fermat theorem (27.2.8), $x^{\phi\left(n\right)}\equiv 1\pmod{n}$; hence $x^{t\phi\left(n\right)}\equiv 1\pmod{n}$. But $y^{s}\equiv x^{rs}\equiv x^{1+t\phi\left(n\right)}\equiv x\pmod{n}$, so $y^{s}$ is the same as $x$ modulo $n$. …
##### 2: 27.2 Functions
27.2.7 $\phi\left(n\right)=\phi_{0}\left(n\right).$
The $\phi\left(n\right)$ numbers $a,a^{2},\dots,a^{\phi\left(n\right)}$ are relatively prime to $n$ and distinct (mod $n$). …Note that $J_{1}\left(n\right)=\phi\left(n\right)$. …
##### 3: 27.3 Multiplicative Properties
27.3.3 $\phi\left(n\right)=n\prod_{p\mathbin{|}n}(1-p^{-1}),$
##### 5: 27.21 Tables
Glaisher (1940) contains four tables: Table I tabulates, for all $n\leq 10^{4}$: (a) the canonical factorization of $n$ into powers of primes; (b) the Euler totient $\phi\left(n\right)$; (c) the divisor function $d\left(n\right)$; (d) the sum $\sigma(n)$ of these divisors. …6 lists $\phi\left(n\right),d\left(n\right)$, and $\sigma(n)$ for $n\leq 1000$; Table 24. …
##### 6: 27.8 Dirichlet Characters
For any character $\chi\pmod{k}$, $\chi\left(n\right)\neq 0$ if and only if $\left(n,k\right)=1$, in which case the Euler–Fermat theorem (27.2.8) implies $\left(\chi\left(n\right)\right)^{\phi\left(k\right)}=1$. There are exactly $\phi\left(k\right)$ different characters (mod $k$), which can be labeled as $\chi_{1},\dots,\chi_{\phi\left(k\right)}$. …
27.8.6 $\sum_{r=1}^{\phi\left(k\right)}\chi_{r}\left(m\right)\overline{\chi}_{r}(n)=% \begin{cases}\phi\left(k\right),&m\equiv n\pmod{k},\\ 0,&\mbox{otherwise}.\end{cases}$
##### 7: 27.11 Asymptotic Formulas: Partial Sums
27.11.6 $\sum_{n\leq x}\phi\left(n\right)=\frac{3}{{\pi}^{2}}x^{2}+O\left(x\ln x\right).$
27.11.7 $\sum_{n\leq x}\frac{\phi\left(n\right)}{n}=\frac{6}{{\pi}^{2}}x+O\left(\ln x% \right).$
27.11.9 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{1}{p}=\frac{1}{\phi\left(k% \right)}\ln\ln x+B+O\left(\frac{1}{\ln x}\right),$
27.11.11 $\sum_{\begin{subarray}{c}p\leq x\\ p\equiv h\!\!\!\!\!\pmod{k}\end{subarray}}\frac{\ln p}{p}=\frac{1}{\phi\left(k% \right)}\ln x+O\left(1\right),$
The prime number theorem for arithmetic progressions—an extension of (27.2.3) and first proved in de la Vallée Poussin (1896a, b)—states that if $\left(h,k\right)=1$, then the number of primes $p\leq x$ with $p\equiv h\pmod{k}$ is asymptotic to $x/(\phi\left(k\right)\ln x)$ as $x\to\infty$.
##### 8: 27.5 Inversion Formulas
27.5.4 $n=\sum_{d\mathbin{|}n}\phi\left(d\right)\Longleftrightarrow\phi\left(n\right)=% \sum_{d\mathbin{|}n}d\mu\left(\frac{n}{d}\right),$
##### 9: 27.7 Lambert Series as Generating Functions
27.7.4 $\sum_{n=1}^{\infty}\phi\left(n\right)\frac{x^{n}}{1-x^{n}}=\frac{x}{(1-x)^{2}},$
##### 10: 27.12 Asymptotic Formulas: Primes
27.12.8 $\frac{\operatorname{li}\left(x\right)}{\phi\left(m\right)}+O\left(x\exp\left(-% \lambda(\alpha)(\ln x)^{1/2}\right)\right),$ $m\leq(\ln x)^{\alpha}$, $\alpha>0$,
where $\lambda(\alpha)$ depends only on $\alpha$, and $\phi\left(m\right)$ is the Euler totient function (§27.2). …