prime numbers

SearchAdvancedHelp

(0.003 seconds)

1—10 of 106 matching pages

1: 27.3 Multiplicative Properties

… ►Except for $\nu \left(n\right)$, $\mathrm{\Lambda }\left(n\right)$, $p_n$, and $\pi \left(x\right)$, the functions in §27.2 are multiplicative, which means $f(1)=1$ and … ►

27.3.2 $$f(n)=\prod _{r=1}^{\nu \left(n\right)}f(p_r^{a_r}).$$

ⓘ

Symbols:

$\nu \left(n\right)$: number of distinct primes dividing a number, $n$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers, $a_r$: positive exponent and $f(n)$: multiplicative function

Referenced by:

§27.20, §27.20, §27.3

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

… ►

27.3.5 $$d\left(n\right)=\prod _{r=1}^{\nu \left(n\right)}(1+a_r),$$

ⓘ

Symbols:

$d_k\left(n\right)$: divisor function, $\nu \left(n\right)$: number of distinct primes dividing a number, $n$: positive integer and $a_r$: positive exponent

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

►

27.3.6 $${\sigma }_{\alpha }\left(n\right)=\prod _{r=1}^{\nu \left(n\right)}\frac{p_r^{\alpha (1+a_r)}-1}{p_r^{\alpha }-1},$$ $\alpha \ne 0$.

ⓘ

Symbols:

${\sigma }_{\alpha }\left(n\right)$: sum of powers of divisors of a number, $\nu \left(n\right)$: number of distinct primes dividing a number, $n$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers and $a_r$: positive exponent

A&S Ref:

24.3.3 I.C

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

… ►

27.3.10 $$f(n)=\prod _{r=1}^{\nu \left(n\right)}{\left(f(p_r)\right)}^{a_r}.$$

ⓘ

Symbols:

$\nu \left(n\right)$: number of distinct primes dividing a number, $n$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers, $a_r$: positive exponent and $f(n)$: multiplicative function

Referenced by:

§27.20, §27.20

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.3 and Ch.27

2: 27.12 Asymptotic Formulas: Primes

§27.12 Asymptotic Formulas: Primes

… ► $\pi \left(x\right)$ is the number of primes less than or equal to $x$. … ►

Prime Number Theorem

… ► $\pi \left(x\right)-\mathrm{li}\left(x\right)$ changes sign infinitely often as $x\to \mathrm{\infty }$; see Littlewood (1914), Bays and Hudson (2000). … ►The largest known prime (2018) is the Mersenne prime $2^{82,589,933}-1$. …

3: 27.2 Functions

… ►where $p_1,p_2,\mathrm{\dots },p_{\nu \left(n\right)}$ are the distinct prime factors of $n$, each exponent $a_r$ is positive, and $\nu \left(n\right)$ is the number of distinct primes dividing $n$. ($\nu \left(1\right)$ is defined to be 0.) …There is great interest in the function $\pi \left(x\right)$ that counts the number of primes not exceeding $x$. … ►(See Gauss (1863, Band II, pp. 437–477) and Legendre (1808, p. 394).) … ►

§27.2(ii) Tables

…

4: 27.18 Methods of Computation: Primes

§27.18 Methods of Computation: Primes

►An overview of methods for precise counting of the number of primes not exceeding an arbitrary integer $x$ is given in Crandall and Pomerance (2005, §3.7). … Oliveira e Silva has calculated $\pi \left(x\right)$ for $x={10}^{23}$, using the combinatorial methods of Lagarias et al. (1985) and Deléglise and Rivat (1996); see Oliveira e Silva (2006). An analytic approach using a contour integral of the Riemann zeta function (§25.2(i)) is discussed in Borwein et al. (2000). … ►For small values of $n$, primality is proven by showing that $n$ is not divisible by any prime not exceeding $\sqrt{n}$. …

5: 27.9 Quadratic Characters

§27.9 Quadratic Characters

… ►

27.9.2 $$(2|p)={(-1)}^{(p^2-1)/8}.$$

ⓘ

Symbols:

$(n|p)$: Legendre symbol and $p$: odd prime

Referenced by:

§27.9

Permalink:

http://dlmf.nist.gov/27.9.E2

Encodings:

pMML, png, TeX

See also:

Annotations for §27.9 and Ch.27

►If $p,q$ are distinct odd primes, then the quadratic reciprocity law states that ►

27.9.3 $$(p|q)(q|p)={(-1)}^{(p-1)(q-1)/4}.$$

ⓘ

Symbols:

$(n|p)$: Legendre symbol, $p$: odd prime and $q$: odd prime

Referenced by:

§27.9

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.9 and Ch.27

►If an odd integer $P$ has prime factorization $P={\prod }_{r=1}^{\nu \left(n\right)}{p}_r^{a_r}$, then the Jacobi symbol $(n|P)$ is defined by $(n|P)={\prod }_{r=1}^{\nu \left(n\right)}{(n|p_r)}^{a_r}$, with $(n|1)=1$. …

6: 27.21 Tables

§27.21 Tables

… ►Bressoud and Wagon (2000, pp. 103–104) supplies tables and graphs that compare $\pi \left(x\right),x/\ln x$, and $\mathrm{li}\left(x\right)$. … ►

7: 27.6 Divisor Sums

… ►

27.6.2 $$\sum _{d|n}\mu \left(d\right)f(d)=\prod _{p|n}(1-f(p)),$$ $n>1$.

ⓘ

Symbols:

$\mu \left(n\right)$: Möbius function, $d$: positive integer, $n$: positive integer and $p,p_1,\mathrm{\dots }$: prime numbers

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.6 and Ch.27

… ►

27.6.3 $$\sum _{d|n}|\mu \left(d\right)|=2^{\nu \left(n\right)},$$

ⓘ

Symbols:

$\mu \left(n\right)$: Möbius function, $\nu \left(n\right)$: number of distinct primes dividing a number, $d$: positive integer and $n$: positive integer

Permalink:

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

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

…

8: 27.1 Special Notation

… ► ►►►

$d,k,m,n$	positive integers (unless otherwise indicated).
…
$p,p_1,p_2,\mathrm{\dots }$	prime numbers (or primes): integers ($>1$) with only two positive integer divisors, $1$ and the number itself.
…

9: 27.4 Euler Products and Dirichlet Series

… ►

27.4.1 $$\sum _{n=1}^{\mathrm{\infty }}f(n)=\prod _p\left(1+\sum _{r=1}^{\mathrm{\infty }}f(p^r)\right),$$

ⓘ

Symbols:

$n$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers and $f$: multiplicative function

Permalink:

http://dlmf.nist.gov/27.4.E1

Encodings:

pMML, png, TeX

See also:

Annotations for §27.4 and Ch.27

… ►

27.4.2 $$\sum _{n=1}^{\mathrm{\infty }}f(n)=\prod _p{(1-f(p))}^{-1}.$$

ⓘ

Symbols:

$n$: positive integer, $p,p_1,\mathrm{\dots }$: prime numbers and $f$: multiplicative function

Permalink:

http://dlmf.nist.gov/27.4.E2

Encodings:

pMML, png, TeX

See also:

Annotations for §27.4 and Ch.27

… ►

27.4.3 $$\zeta \left(s\right)=\sum _{n=1}^{\mathrm{\infty }}{n}^{-s}=\prod _p{(1-p^{-s})}^{-1},$$ $\mathrm{\Re }s>1$.

ⓘ

Symbols:

$\zeta \left(s\right)$: Riemann zeta function, $\mathrm{\Re }$: real part, $n$: positive integer and $p,p_1,\mathrm{\dots }$: prime numbers

A&S Ref:

23.2.1 and 23.2.2

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.4 and Ch.27

… ►

27.4.9 $$\sum _{n=1}^{\mathrm{\infty }}{2}^{\nu \left(n\right)}{n}^{-s}=\frac{{(\zeta \left(s\right))}^2}{\zeta \left(2s\right)},$$ $\mathrm{\Re }s>1$,

ⓘ

Symbols:

$\zeta \left(s\right)$: Riemann zeta function, $\nu \left(n\right)$: number of distinct primes dividing a number, $\mathrm{\Re }$: real part and $n$: positive integer

Permalink:

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

Encodings:

pMML, png, TeX

See also:

Annotations for §27.4 and Ch.27

…

10: 27.16 Cryptography

§27.16 Cryptography

… ►The primes are kept secret but their product $n=pq$, an 800-digit number, is made public. …