Euler totient

SearchAdvancedHelp

(0.001 seconds)

1—10 of 13 matching pages

1: 27.16 Cryptography

… ►To do this, let $s$ denote the reciprocal of $r$ modulo $\varphi \left(n\right)$, so that $rs=1+t\varphi \left(n\right)$ for some integer $t$. (Here $\varphi \left(n\right)$ is Euler’s totient (§27.2).) By the Euler–Fermat theorem (27.2.8), $x^{\varphi \left(n\right)}\equiv 1(modn)$; hence $x^{t\varphi \left(n\right)}\equiv 1(modn)$. But $y^s\equiv x^{rs}\equiv x^{1+t\varphi \left(n\right)}\equiv x(modn)$, so $y^s$ is the same as $x$ modulo $n$. …

2: 27.2 Functions

… ►

27.2.6 $${\varphi }_k\left(n\right)=\sum _{\left(m,n\right)=1}{m}^k,$$

ⓘ

Defines:

${\varphi }_k\left(n\right)$: sum of powers of integers relatively prime to a number

Symbols:

$\left(m,n\right)$: greatest common divisor (gcd), $k$: positive integer, $m$: positive integer and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.2.E6

Encodings:

pMML, png, TeX

See also:

Annotations for §27.2(i), §27.2 and Ch.27

… ►

27.2.7 $$\varphi \left(n\right)={\varphi }_0\left(n\right).$$

ⓘ

Defines:

$\varphi \left(n\right)$: Euler’s totient

Symbols:

${\varphi }_k\left(n\right)$: sum of powers of integers relatively prime to a number and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.2.E7

Encodings:

pMML, png, TeX

See also:

Annotations for §27.2(i), §27.2 and Ch.27

… ►The $\varphi \left(n\right)$ numbers $a,a^2,\mathrm{\dots },a^{\varphi \left(n\right)}$ are relatively prime to $n$ and distinct (mod $n$). …Note that $J_1\left(n\right)=\varphi \left(n\right)$. … ►

Table 27.2.2: Functions related to division.

► ►►

$n$	$\varphi \left(n\right)$	$d\left(n\right)$	$\sigma \left(n\right)$	$n$	$\varphi \left(n\right)$	$d\left(n\right)$	$\sigma \left(n\right)$	$n$	$\varphi \left(n\right)$	$d\left(n\right)$	$\sigma \left(n\right)$	$n$	$\varphi \left(n\right)$	$d\left(n\right)$	$\sigma \left(n\right)$
…

►

3: 27.3 Multiplicative Properties

… ►

27.3.3 $$\varphi \left(n\right)=n\prod _{p|n}(1-p^{-1}),$$

ⓘ

Symbols:

$\varphi \left(n\right)$: Euler’s totient, $n$: positive integer and $p,p_1,\mathrm{\dots }$: prime numbers

A&S Ref:

24.3.2 I.C

Permalink:

http://dlmf.nist.gov/27.3.E3

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

… ►

27.3.8 $$\varphi \left(m\right)\varphi \left(n\right)=\varphi \left(mn\right)\varphi \left(\left(m,n\right)\right)/\left(m,n\right).$$

ⓘ

Symbols:

$\varphi \left(n\right)$: Euler’s totient, $\left(m,n\right)$: greatest common divisor (gcd), $m$: positive integer and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.3.E8

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

…

4: 27.6 Divisor Sums

… ►

27.6.5 $$\sum _{d|n}\frac{|\mu \left(d\right)|}{\varphi \left(d\right)}=\frac{n}{\varphi \left(n\right)},$$

ⓘ

Symbols:

$\varphi \left(n\right)$: Euler’s totient, $\mu \left(n\right)$: Möbius function, $d$: positive integer and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.6.E5

Encodings:

pMML, png, TeX

See also:

Annotations for §27.6 and Ch.27

►

27.6.6 $$\sum _{d|n}{\varphi }_k\left(d\right){\left(\frac{n}{d}\right)}^k=1^k+2^k+\mathrm{\cdots }+n^k,$$

ⓘ

Symbols:

${\varphi }_k\left(n\right)$: sum of powers of integers relatively prime to a number, $d$: positive integer, $k$: positive integer and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.6.E6

Encodings:

pMML, png, TeX

See also:

Annotations for §27.6 and Ch.27

…

5: 27.21 Tables

… ►Glaisher (1940) contains four tables: Table I tabulates, for all $n\le {10}^4$: (a) the canonical factorization of $n$ into powers of primes; (b) the Euler totient $\varphi \left(n\right)$; (c) the divisor function $d\left(n\right)$; (d) the sum $\sigma (n)$ of these divisors. …6 lists $\varphi \left(n\right),d\left(n\right)$, and $\sigma (n)$ for $n\le 1000$; Table 24. …

6: 27.8 Dirichlet Characters

… ►For any character $\chi (modk)$, $\chi \left(n\right)\ne 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)}^{\varphi \left(k\right)}=1$. There are exactly $\varphi \left(k\right)$ different characters (mod $k$), which can be labeled as ${\chi }_1,\mathrm{\dots },{\chi }_{\varphi \left(k\right)}$. … ►

27.8.6

ⓘ

Symbols:

$\chi \left(n\right)$: Dirichlet character, $\varphi \left(n\right)$: Euler’s totient, $\overline{z}$: complex conjugate, $\equiv$: modular equivalence, $k$: positive integer, $m$: positive integer and $n$: positive integer

Permalink:

http://dlmf.nist.gov/27.8.E6

Encodings:

pMML, png, TeX

See also:

Annotations for §27.8 and Ch.27

…

7: 27.11 Asymptotic Formulas: Partial Sums

… ►

27.11.6 $$\sum _{n\le x}\varphi \left(n\right)=\frac{3}{{\pi }^2}{x}^2+O\left(x\ln x\right).$$

ⓘ

Symbols:

$O\left(x\right)$: order not exceeding, $\varphi \left(n\right)$: Euler’s totient, $\pi$: the ratio of the circumference of a circle to its diameter, $\ln z$: principal branch of logarithm function, $n$: positive integer and $x$: real number

A&S Ref:

24.3.2 III (in slightly different form)

Permalink:

http://dlmf.nist.gov/27.11.E6

Encodings:

pMML, png, TeX

Change of Notation (effective with 1.0.10):

The notation for logarithm has been changed to $\ln$ from $\log$.

See also:

Annotations for §27.11 and Ch.27

►

27.11.7 $$\sum _{n\le x}\frac{\varphi \left(n\right)}{n}=\frac{6}{{\pi }^2}x+O\left(\ln x\right).$$

ⓘ

Symbols:

$O\left(x\right)$: order not exceeding, $\varphi \left(n\right)$: Euler’s totient, $\pi$: the ratio of the circumference of a circle to its diameter, $\ln z$: principal branch of logarithm function, $n$: positive integer and $x$: real number

Permalink:

http://dlmf.nist.gov/27.11.E7

Encodings:

pMML, png, TeX

Change of Notation (effective with 1.0.10):

The notation for logarithm has been changed to $\ln$ from $\log$.

See also:

Annotations for §27.11 and Ch.27

… ►

27.11.9 $$\sum _{\begin{array}{c}p\le x\\ p\equiv h(modk)\end{array}}\frac{1}{p}=\frac{1}{\varphi \left(k\right)}\ln \ln x+B+O\left(\frac{1}{\ln x}\right),$$

ⓘ

Symbols:

$O\left(x\right)$: order not exceeding, $\varphi \left(n\right)$: Euler’s totient, $\equiv$: modular equivalence, $\ln z$: principal branch of logarithm function, $k$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers and $x$: real number

Referenced by:

§27.11

Permalink:

http://dlmf.nist.gov/27.11.E9

Encodings:

pMML, png, TeX

Change of Notation (effective with 1.0.10):

The notation for logarithm has been changed to $\ln$ from $\log$.

See also:

Annotations for §27.11 and Ch.27

… ►

27.11.11 $$\sum _{\begin{array}{c}p\le x\\ p\equiv h(modk)\end{array}}\frac{\ln p}{p}=\frac{1}{\varphi \left(k\right)}\ln x+O\left(1\right),$$

ⓘ

Symbols:

$O\left(x\right)$: order not exceeding, $\varphi \left(n\right)$: Euler’s totient, $\equiv$: modular equivalence, $\ln z$: principal branch of logarithm function, $k$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers and $x$: real number

Referenced by:

§27.11, §27.11

Permalink:

http://dlmf.nist.gov/27.11.E11

Encodings:

pMML, png, TeX

Change of Notation (effective with 1.0.10):

The notation for logarithm has been changed to $\ln$ from $\log$.

See also:

Annotations for §27.11 and Ch.27

… ►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\le x$ with $p\equiv h(modk)$ is asymptotic to $x/(\varphi \left(k\right)\ln x)$ as $x\to \mathrm{\infty }$.

8: 27.5 Inversion Formulas

… ►

27.5.4 $$n=\sum _{d|n}\varphi \left(d\right)⟺\varphi \left(n\right)=\sum _{d|n}d\mu \left(\frac{n}{d}\right),$$

ⓘ

Symbols:

$\varphi \left(n\right)$: Euler’s totient, $\mu \left(n\right)$: Möbius function, $d$: positive integer and $n$: positive integer

A&S Ref:

24.3.2 II.B

Permalink:

http://dlmf.nist.gov/27.5.E4

Encodings:

pMML, png, TeX

See also:

Annotations for §27.5 and Ch.27

…

9: 27.7 Lambert Series as Generating Functions

… ►

27.7.4 $$\sum _{n=1}^{\mathrm{\infty }}\varphi \left(n\right)\frac{x^n}{1-x^n}=\frac{x}{{(1-x)}^2},$$

ⓘ

Symbols:

$\varphi \left(n\right)$: Euler’s totient, $n$: positive integer and $x$: real number

A&S Ref:

24.3.2 I.B

Permalink:

http://dlmf.nist.gov/27.7.E4

Encodings:

pMML, png, TeX

See also:

Annotations for §27.7 and Ch.27

…

10: 27.12 Asymptotic Formulas: Primes

… ►

27.12.8 $$\frac{\mathrm{li}\left(x\right)}{\varphi \left(m\right)}+O\left(x\exp \left(-\lambda (\alpha ){(\ln x)}^{1/2}\right)\right),$$ $m\le {(\ln x)}^{\alpha }$, $\alpha >0$,

ⓘ

Symbols:

$O\left(x\right)$: order not exceeding, $\varphi \left(n\right)$: Euler’s totient, $\exp z$: exponential function, $\mathrm{li}\left(x\right)$: logarithmic integral, $\ln z$: principal branch of logarithm function, $m$: positive integer and $x$: real number

Referenced by:

Erratum (V1.0.17) for Equation (27.12.8)

Permalink:

http://dlmf.nist.gov/27.12.E8

Encodings:

pMML, png, TeX

Errata (effective with 1.0.17):

Originally the first term was given incorrectly by $\frac{x}{\varphi \left(m\right)}$.

Reported 2017-12-04 by Gergő Nemes

Change of Notation (effective with 1.0.10):

The notation for logarithm has been changed to $\ln$ from $\log$.

See also:

Annotations for §27.12, §27.12 and Ch.27

►where $\lambda (\alpha )$ depends only on $\alpha$, and $\varphi \left(m\right)$ is the Euler totient function (§27.2). …