Number theory

If $\gcd (a,m)=1$, infinitely many primes satisfy

An arithmetic function $f$ is multiplicative when $f(mn)=f(m)f(n)$ whenever $m$ and $n$ are coprime.

The divisor sum of an arithmetic function $f$ isIf $f$ is multiplicative, then $F$ is multiplicative as well.

Repeated squaring computes $a^n$ using $O(\log n)$ multiplications by reading the binary expansion of $n$. Performing every multiplication modulo $m$ computes $a^n\mathrm{mod}m$ with the same number of modular multiplications.

An integer is a whole number, positive, negative, or zero.

A positive integer is an integer greater than zero.

An odd integer is not divisible by two; equivalently, it has the form $2k+1$.

An integer is even when it is divisible by two.

An integer is odd when it is not divisible by two.

A square-free integer is divisible by no square greater than one.

An integer $d$ divides an integer $n$, written $d\mid n$, when $n=dk$ for some integer $k$.

An integer divisor of $n$ is an integer that divides $n$.

The greatest common divisor of integers $a$ and $b$ is the largest positive integer dividing both.

Two integers $a$ and $b$ are coprime when $\gcd (a,b)=1$.

The least common multiple of positive integers is the smallest positive integer divisible by all of them.

The congruence $a\equiv b(\mathrm{mod}n)$ means that $n$ divides $a-b$.

A prime number is an integer $p>1$ whose only positive divisors are $1$ and $p$.

A Fermat prime is a prime number of the formFor $k\ge 1$, it is congruent to $1$ modulo $4$ and to $2$ modulo $3$.

For a Fermat prime $p=2^{2^k}+1$, the multiplicative group modulo $p$ has order $2^{2^k}$. Its $\phi (p-1)=(p-1)/2$ primitive roots are all quadratic nonresidues; since there are also $(p-1)/2$ nonresidues, the two sets coincide.

Every integer greater than one is a product of prime numbers, uniquely up to reordering the factors.

A prime power is a positive integer of the form $p^d$, where $p$ is a prime number and $d$ is a nonnegative integer.

A composite number is an integer greater than one that is not a prime number.

If $\gcd (a,n)=1$, then $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$. For prime $n=p$, this yields Fermat's little theorem.

For fixed $a>1$ and suitable odd primes $p$, the composite generalized repunitis congruent to one modulo $2p$ and is a pseudoprime to base $a$.

An odd composite number $N$ is a Fermat pseudoprime to a coprime base $b$ when

Write the even number $N-1$ as $2^{s}m$ with $m$ odd. An odd composite number $N$ is a strong pseudoprime to a coprime base $b$ whenor $b^{2^{j}m}\equiv -1(\mathrm{mod}N)$ for some $0\le j<s$.

Let $N=pq$ for distinct odd prime numbers $p,q$ with $\gcd (p-1,q-1)=10$. Exactly $100$ unit bases make $N$ a Fermat pseudoprime, and exactly $50$ of these make it a strong pseudoprime. The Fermat bases form $C_{10}\times C_{10}$ under the Chinese remainder theorem for unit groups. If $N-1=2^{s}m$, then $5\mid m$ and $m$ is odd, so the $m$th-power map sends five elements of each $C_{10}$ to $1$ and five to $-1$. The strong condition requires equal signs in both components, giving $5^2+5^2=50$.

An odd composite number $N$ is an Euler pseudoprime to a coprime base $b$ whenwhere the right side is the Jacobi symbol.

For a prime $p$ and a nonzero integer $N$, the $p$-adic valuation isIt extends to nonzero rational numbers by $v_p(a/b)=v_p(a)-v_p(b)$.

For a prime number $p$ and a positive integer $n$, the P-adic valuation of a factorial is

If $k\ge 1$ and $k+2\le p\le 2k+1$ is prime, thenIndeed, neither $(k+1)!$ nor $k!$ contains a factor $p$, while $(2k+1)!$ contains $p$ exactly once because $2p>2k+1$.

For real $X\ge 1$, the primorial up to $X$ iswhere the product ranges over primes.

The Chebyshev theta function is the natural logarithm of the primorial:where both the sum and the product range over prime numbers.

The central binomial coefficient and Legendre formula implyfor every sufficiently large real number $x$.

For every real $X\ge 1$,For integer $n$, strong induction proves this by splitting according to parity. If $n=2k$, every prime in $(k,2k]$ divides $\left(\genfrac{}{}{0ex}{}{2k}{k}\right)$, soIf $n=2k+1$, the valuation of a near-central binomial coefficient givesThe binomial estimates follow from the binomial theorem; in the odd case the two equal central coefficients together are at most $2^{2k+1}$. The result for real $X$ follows by replacing $X$ with $\lfloor X\rfloor$.

A positive integer $n$ is decisive when every integer $a$ satisfying $1<a<n$ and $\gcd (a,n)=1$ is a prime number. There are only finitely many decisive numbers: every prime $p<\sqrt{n}$ must divide a decisive $n$, so the Chebyshev theta function gives $\log n\ge \vartheta (\sqrt{n})$, which eventually contradicts the linear lower bound for $\vartheta (\sqrt{n})$.

The prime-counting function $\pi (X)$ is the number of primes at most $X$.

If $P(X)\le A^X$ for every $X\ge 1$, where $A>1$, thenfor $X\ge 2$. Every prime in $(\sqrt{X},X]$ contributes at least $\sqrt{X}$ to the primorial, soTaking logarithms, using $\pi (\sqrt{X})\le \sqrt{X}$, and observing that $\log X\le \sqrt{X}$ for $X\ge 2$ proves the claim.

A unit $g$ modulo $N$ is a primitive root when its multiplicative order is $\phi (N)$.

Let $p$ be an odd prime and let $b$ be primitive modulo $p$. Then $b$ is primitive modulo every $p^m$ if and only if it is primitive modulo $p^2$. In that case

An integer $n$ has a primitive root exactly whenwhere $p$ is an odd prime and $a\ge 1$. When primitive roots exist, their number is $\phi (\phi (n))$.

For an odd prime $p$, a nonzero class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$. These residues form an index-two subgroup of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$.

A nonzero class modulo an odd prime is a quadratic nonresidue when it is not a square.

For $\omega =e^{2\pi i/p}$ and the Legendre symbol $\chi$, the quadratic Gauss sum isIt equals $\sqrt{p}$ for $p\equiv 1(\mathrm{mod}4)$ and $i\sqrt{p}$ for $p\equiv 3(\mathrm{mod}4)$ with the standard choice of square root.

If $Q$ and $N$ are the nonzero square and nonsquare classes modulo eleven and $\omega =e^{2\pi i/11}$, thenTheir sum is $-1$, and their difference is the Quadratic Gauss sum $i\sqrt{11}$.

For an odd prime $p$,

For an odd prime $p$ and $p\nmid a$,

For an odd prime $p$ and $p\nmid a$, let $m$ be the number of least positive residues amongthat exceed $p/2$. Then

For an odd prime $p$,For $p\nmid a$, write $a=g^m$ using a primitive root $g$; then the left side is $(-1{)}^m$, which is one exactly when $m$ is even and $a$ is a square.

Euler's criterion at $a=-1$ gives

For every odd prime,

If $q_1,\dots ,q_r$ listed all primes congruent to seven modulo eight, then for $n=8q_1\cdots q_r$ the odd number $(n^2-2)/2$ is seven modulo eight. Every prime factor is one or seven modulo eight, at least one is seven, and none is among the $q_i$, a contradiction.

Let ${\pi }_k(x)$ count primes at most $x$ congruent to $k$ modulo eight. Bounding the prime-power divisibility ofabove and its size below gives, for all sufficiently large $x$,

For an integer matrix $A$ and prime $p$, the commuting-matrix binomial theorem and divisibility of $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ for $0<j<p$ give

For $T={\sum }_{a=1}^{p-1}a(\frac{a}{p})$, one has $T=0$ when $p\equiv 1(\mathrm{mod}4)$, and $T\equiv 0(\mathrm{mod}p)$ for every $p>3$.

If $p\equiv 7(\mathrm{mod}8)$, the sum of the least positive quadratic residues below $p/2$ isThe proof uses $(\frac{2}{p})=1$ to compare the sum of all residues with its image under doubling.

For $p\nmid a$, the congruence $a{X}^2+bX+c=0(\mathrm{mod}p)$ has a solution exactly when its discriminant $b^2-4ac$ is zero or a quadratic residue modulo $p$.

If $g$ is primitive modulo an odd prime $p$ and $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$, then $g$ is primitive modulo every $p^k$.

The Möbius function is $\mu (1)=1$, is zero on integers divisible by a prime square, and is $(-1{)}^r$ on products of $r$ distinct primes.

$\zeta (s)={\sum }_{n\ge 1}{n}^{-s}$ for $\Re s>1$; its Euler product is ${\prod }_p(1-p^{-s}{)}^{-1}$.

For $\Re s>0$, the alternating Dirichlet seriesconverges locally uniformly and defines a holomorphic function. For $\Re s>1$,

The identity $\zeta (s)=\eta (s)/(1-2^{1-s})$ continues the Riemann zeta function meromorphically to $\Re s>0$. Apparent singularities at nonreal zeros of $1-2^{1-s}$ are removable, as one sees by replacing $2$ with an integer $k$ for which $1-k^{1-s}\ne 0$. At $s=1$, $\eta (1)=\log 2$ and $1-2^{1-s}\sim (s-1)\log 2$, so $\zeta$ has a simple pole of residue one.

For odd $n=\prod p_i^{e_i}$, $(a/n)=\prod (a/p_i{)}^{e_i}$. A value $1$ need not mean that $a$ is a square modulo composite $n$.

For distinct odd primes, $(p/q)(q/p)=(-1{)}^{(p-1)(q-1)/4}$.

For an odd prime $p\ne 3$, quadratic reciprocity givesThus $-3$ is a square modulo $p$ exactly when $p\equiv 1(\mathrm{mod}3)$.

The factorizationshows that $X^3=-1$ always has $X=-1$ as a solution. For $p\ne 3$, it has two further solutions exactly when $-3$ is a quadratic residue; for $p=3$, all three factors coalesce at the unique root $-1$.

A composite $N$ is Carmichael when $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$.

A composite integer $N$ is Carmichael exactly when it is square-free and $p-1$ divides $N-1$ for every prime $p$ dividing $N$.

A simple continued fraction recursively expands a real number by taking integer parts and reciprocals. Its convergents are exceptionally good rational approximations.

Starting from $x_0=x>0$, definewhenever $x_n$ is not an integer. This produces $x=[a_0;a_1,a_2,\dots ]$.

A simple continued fraction terminates exactly when its value is rational. For a reduced rational $p/q$, each reciprocal step is one step of the Euclidean algorithm and replaces the denominator by a strictly smaller nonnegative remainder.

Truncating a simple continued fraction gives a convergent; sufficiently accurate rational approximations with bounded denominator occur among these convergents.

With $M(a)=\left(\begin{array}{cc}a& 1\\ 1& 0\end{array}\right)$,

If $p_n/q_n=[a_0,\dots ,a_n]$, then appending a positive tail $x$ gives

For positive $a_j,b_j$, define $p_0=a_0$, $p_{-1}=1$, $q_0=1$, $q_{-1}=0$ andThenand $p_n/q_n$ is the corresponding finite generalized continued fraction.

When $b_j=1$ and $a_j$ are positive integers, adjacent convergents satisfyEven and odd convergents are monotone from opposite sides, their separation is $1/(q_n{q}_{n+1})$, and $q_n\to \infty$. They therefore have a common limit $x$, with

If every $a_j=b_j=1$, then $p_n=F_{n+2}$ and $q_n=F_{n+1}$. Binet's formulashows that the convergents tend to $\varphi$ and gives sharp scaled errors through $F_{n+1}-\varphi F_n={\psi }^n$.

The simple continued fraction of a quadratic irrational is eventually periodic. For a nonsquare positive integer $D$, the continued fraction of $\sqrt{D}$ is periodic after its integer part.

Successive complete quotients repeat after two steps:

Rationalizing successive complete quotients gives

If $p_n/q_n$ are the convergents of $\sqrt{11}$, then

For the even convergents of $\sqrt{11}$,Since the second factor has norm one, every such convergent satisfies $p_{2m}^2-11q_{2m}^2=-2$.

If an irrational algebraic number has degree $d$, then $|\alpha -p/q|>C(\alpha )q^{-d}$. Approximations of arbitrarily larger polynomial order therefore prove transcendence.

For the degree-$d$ minimal polynomial $P\in \mathbb{Z}[X]$ of $\alpha$, the nonzero integer $q^{d}P(p/q)$ gives $|P(p/q)|\ge q^{-d}$. On a fixed neighbourhood of $\alpha$, the mean value theorem boundsOutside that neighbourhood the desired lower bound is immediate, giving $|\alpha -p/q|>c(\alpha )q^{-d}$ after decreasing the constant.

For distinct reduced fractions $p/q$ and $u/v$,If $q>v$, this is strictly greater than $q^{-2}$.

Every convergent series of positive rational terms has a subseries whose rational partial sums $p_j/q_j$ satisfyChoose each new term small enough to enforce all previous tail bounds. Separation of reduced fractions first makes $\alpha$ irrational, and the Liouville approximation theorem then rules out every finite algebraic degree.

A binary quadratic form is $a{x}^2+bxy+c{y}^2$; integral changes of variables organize forms into equivalence classes.

Integral forms $f$ and $g$ are properly equivalent whenfor some $\left(\begin{array}{cc}\alpha & \beta \\ \gamma & \delta \end{array}\right)\in {\mathrm{SL}}_2(\mathbb{Z})$. Proper equivalence preserves both represented integers and orientation.

An integral binary quadratic form $[a,b,c]$ is primitive when $\gcd (a,b,c)=1$. This property is invariant under proper equivalence because a unimodular change and its integral inverse express either coefficient triple as integer combinations of the other.

The discriminant of $[a,b,c]$ is $D=b^2-4ac$. It is invariant under proper equivalence, and a real form with $a>0$ is positive definite exactly when $D<0$.

A positive definite integral form $[a,b,c]$ is reduced when $|b|\le a\le c$, with $b\ge 0$ if $|b|=a$ or $a=c$. Every proper equivalence class has a unique reduced representative under this boundary convention.

For a reduced form of negative discriminant $D$, the inequalities imply $3a^2\le |D|$. One can therefore enumerate all classes by checking the finite setand retaining integral $c=(b^2-D)/(4a)$ with $a\le c$ and the boundary sign convention.

For a negative discriminant $D\equiv 0$ or $1(\mathrm{mod}4)$, the class number $h(D)$ is the number of proper equivalence classes of primitive positive definite integral binary quadratic forms of discriminant $D$. Equivalently, it is the number of reduced primitive forms of discriminant $D$.

For an odd prime number $q$, the primitive positive definite formshave discriminant $-8q$ and lie in distinct proper equivalence classes. The first represents one, whereas the second has minimum positive value two.

If $q\equiv 3(\mathrm{mod}8)$ is prime and $h(-8q)=2$, then for every prime $p>q$,for some integers $x,y$ exactly when $p\equiv \pm 1(\mathrm{mod}8)$ and $p$ is a quadratic residue modulo $q$.

Let $d$ be odd and have $k$ distinct prime divisors. Assigning each complete prime-power factor of $d$ to one of two factors gives $2^k$ ordered coprime factorizations $d=ac$. Interchanging $a$ and $c$ identifies pairs, and each unordered factorization gives a different reduced primitive form $[\min (a,c),0,\max (a,c)]$ of discriminant $-4d$. Hence

The identitycomes from an integer change-of-variable matrix of determinant $-1$. It therefore preserves the set of integers represented and reduces the form to $u^2+v^2$.

If a prime divides a product of integers, it divides at least one factor.

The prime valuation v_p(n) is the exponent of p in the prime factorization of n.

Euler’s totient function counts residue classes modulo n that are coprime to n.

If a is coprime to n, then a raised to the power phi(n) is congruent to one modulo n.

Multiplication by a unit $a$ permutes the reduced residue classes modulo $n$. Multiplying all classes before and after this permutation and cancelling their unit product proves $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.

For coprime positive integers m and n, the Chinese remainder theorem gives phi(mn)=phi(m)phi(n).

For each positive integer $k$, only finitely many $n$ satisfy $\phi (n)=k$. Indeed, every prime $p\mid n$ has $p-1\mid k$, and the exponent of $p$ in $n$ is bounded because $p^{a-1}\mid k$.

The Jordan totient function counts ordered $k$-tuples modulo $n$ that together with $n$ have greatest common divisor one. The inclusion-exclusion principle gives

For a prime p, every integer a satisfies a^p congruent to a modulo p.

A squarefree integer is not divisible by the square of any prime.

An integer has a square factor when some prime square divides it.

The identity $r^2-s^2=(r-s)(r+s)$ converts a square difference into a factorization.

Fermat factorization tests successive $r\ge \lceil \sqrt{N}\rceil$ until $r^2-N=s^2$, then returns $N=(r-s)(r+s)$.

A rational number is a quotient of two integers with nonzero denominator.

Between any two distinct real numbers lies a rational number.

A real number is rational exactly when its expansion in any integer base is eventually periodic.

A positional expansion in an integer base represents a rational number exactly when its digit sequence is eventually periodic. Long division proves the forward implication because only finitely many remainders occur; summing a periodic tail as a geometric series proves the converse.

The Carmichael function $\lambda (n)$ is the exponent of $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$, equivalently the least positive $m$ such that every unit $a$ satisfies $a^m\equiv 1(\mathrm{mod}n)$.

The multiplicative order of a unit $a$ modulo $N$ is the least positive $r$ for which $a^r\equiv 1(\mathrm{mod}N)$.

For an $L$-digit decimal integer $n$, moving its leading digit to the end gives a cyclic rotation $c_1(n)$ satisfyingThus, when a modulus $d$ divides $10^L-1$, every rotation has the same divisibility by $d$ as $n$, up to multiplication by a power of ten.

For a unit $a$ modulo $N$, the function $x\mapsto a^x\mathrm{mod}N$ is periodic on the integers.

Equality $a^x\equiv a^y(\mathrm{mod}N)$ holds exactly when the multiplicative order divides $x-y$, so one period contains no repeated values.

To verify a candidate order $r$, check $a^r\equiv 1$ and rule out $a^{r/q}\equiv 1$ for every prime divisor $q$ of $r$.

The Euclidean algorithm repeatedly replaces $(a,b)$ by $(b,a\mathrm{mod}b)$ and terminates at $\gcd (a,b)$.

A linear Diophantine equation in two variables has the form $ax+by=c$ with integer coefficients and seeks integer solutions.

The equation $ax+by=c$ has an integer solution exactly when $\gcd (a,b)$ divides $c$. Bézout's identity proves sufficiency, while every integer linear combination of $a,b$ is divisible by their greatest common divisor.

A positive integer is a sum of two integer squares exactly when every prime factor congruent to $3$ modulo $4$ has even exponent in its prime factorization.