Basic Number Theory

This article gives a brief introduction to the beginning of number theory.

Divisibility

Definition

Let $a,b\in\mathbf{Z}$ and $a\ne 0$. If $\exists q\in\mathbf{Z}$ such that $b=aq$, then $b$ is said to be divisible by $a$, written $a\mid b$; the statement that $b$ is not divisible by $a$ is written $a\nmid b$.

Properties of divisibility:

• $a\mid b\iff-a\mid b\iff a\mid-b\iff|a|\mid|b|$
• $a\mid b\land b\mid c\implies a\mid c$
• $a\mid b\land a\mid c\iff\forall x,y\in\mathbf{Z}, a\mid(xb+yc)$
• $a\mid b\land b\mid a\implies b=\pm a$
• Let $m\ne0$. Then $a\mid b\iff ma\mid mb$.
• Let $b\ne0$. Then $a\mid b\implies|a|\le|b|$.
• Let $a\ne0,b=qa+c$. Then $a\mid b\iff a\mid c$.

Divisors

Definition

If $a\mid b$, then $b$ is called a multiple of $a$, and $a$ is called a divisor of $b$.

The number $0$ is a multiple of every non-$0$ integer. For an integer $b\ne0$, $b$ has only finitely many divisors.

Trivial divisors (trivial factors): for an integer $b\ne0$, $\pm1$ and $\pm b$ are the trivial divisors of $b$. When $b=\pm1$, $b$ has only two trivial divisors.

For an integer $b\ne 0$, the other divisors of $b$ are called proper divisors (proper factors, nontrivial divisors, or nontrivial factors).

Properties of divisors:

• Let $b\ne0$ be an integer. As $d$ ranges over all divisors of $b$, $\dfrac{b}{d}$ also ranges over all divisors of $b$.
• Let $b\gt 0$ be an integer. As $d$ ranges over all positive divisors of $b$, $\dfrac{b}{d}$ also ranges over all positive divisors of $b$.

In concrete problems, unless stated otherwise, “divisor” always means “positive divisor.”

Division with Remainder

Remainder

Let $a,b$ be two given integers with $a\ne0$, and let $d$ be a given integer. Then there is a unique pair of integers $q$ and $r$ satisfying $b=qa+r,d\le r<|a|+d$.

For any choice of the integer $d$, $r$ is called a remainder. The statement $a\mid b$ is equivalent to $a\mid r$.

In general, take $d$ to be $0$. Then the equation $b=qa+r,0\le r<|a|$ is called division with remainder. Here $r$ is called the least nonnegative remainder.

There are two other common choices of remainder:

• Absolute least remainder: take $d$ to be the negative of half the absolute value of $a$. That is, $b=qa+r,-\dfrac{|a|}{2}\le r<|a|-\dfrac{|a|}{2}$.
• Least positive remainder: take $d$ to be $1$. That is, $b=qa+r,1\le r<|a|+1$.

Division with remainder has only one least nonnegative remainder. Unless stated otherwise, “remainder” always means the least nonnegative remainder.

Properties of remainders:

• After any integer is divided by a positive integer $a$, its remainder is exactly one of the numbers from $0$ to $(a-1)$; there are $a$ such numbers.
• When any $a$ consecutive integers are divided by the positive integer $a$, they produce exactly the $a$ remainders above. In particular, exactly one of them is divisible by $a$.

Greatest Common Divisor and Least Common Multiple

For the definitions of the four terms common divisor, common multiple, greatest common divisor, and least common multiple, see greatest common divisor.

Warning

Some authors consider the greatest common divisor of $0$ and $0$ undefined, while others generally regard it as $0$. The latter convention is used in the C++ STL implementation, which treats the greatest common divisor of $0$ and $0$ as $0$¹.

The greatest common divisor has the following properties:

• $(a_1,\dots,a_n)=(|a_1|,\dots,|a_n|)$;
• $(a,b)=(b,a)$;
• If $a\ne 0$, then $(a,0)=(a,a)=|a|$;
• $(bq+r,b)=(r,b)$;
• $(a_1,\dots,a_n)=((a_1,a_2),a_3,\dots,a_n)$. Consequently, $\forall 1<k<n-1,~(a_1,\dots,a_n)=((a_1,\dots,a_k),(a_{k+1},\dots,a_n))$;
• For integers not all equal to $0$, $a_1,\dots,a_n$, and a nonzero integer $m$, $(ma_1,\dots,ma_n)=|m|(a_1,\dots,a_n)$;
• For integers not all equal to $0$, $a_1,\dots,a_n$, if $(a_1,\dots,a_n)=d$, then $(a_1/d,\dots,a_n/d)=1$;
• $(a^n,b^n)=(a,b)^n$.

The greatest common divisor also has the following properties related to coprimality:

• If $b|ac$ and $(a,b)=1$, then $b\mid c$;
• If $b|c$, $a|c$, and $(a,b)=1$, then $ab\mid c$;
• If $(a,b)=1$, then $(a,bc)=(a,c)$;
• If $(a_i,b_j)=1,~\forall 1\leq i\leq n,1\leq j\leq m$, then $\left(\prod_i a_i,\prod_j b_j\right)=1$. In particular, if $(a,b)=1$, then $(a^n,b^m)=1$;
• For integers $a_1,\dots,a_n$, if $\exists v\in \mathbf{Z},~\prod_i a_i=v^m$, and $(a_i,a_j)=1,~\forall i\ne j$, then $\forall 1\leq i\leq n,~\sqrt[m]{a_i}\in\mathbf{Z}$.

The least common multiple has the following properties:

• $[a_1,\dots,a_n]=[|a_1|,\dots,|a_n|]$;
• $[a,b]=[b,a]$;
• If $a\ne 0$, then $[a,1]=[a,a]=|a|$;
• If $a\mid b$, then $[a,b]=|b|$;
• $[a_1,\dots,a_n]=[[a_1,a_2],a_3,\dots,a_n]$. Consequently, $\forall 1<k<n-1,~[a_1,\dots,a_n]=[[a_1,\dots,a_k],[a_{k+1},\dots,a_n]]$;
• If $a_i\mid m,~\forall 1\leq i\leq n$, then $[a_1,\dots,a_n]\mid m$;
• $[ma_1,\dots,ma_n]=|m|[a_1,\dots,a_n]$;
• $[a,b,c][ab,bc,ca]=[a,b][b,c][c,a]$;
• $[a^n,b^n]=[a,b]^n$.

The greatest common divisor and least common multiple can be combined to produce many remarkable identities, such as:

• $(a,b)[a,b]=|ab|$;
• $(ab,bc,ca)[a,b,c]=|abc|$;
• $\dfrac{(a,b,c)^2}{(a,b)(b,c)(a,c)}=\dfrac{[a,b,c]^2}{[a,b][b,c][a,c]}$.

All these properties can be proved from the definitions or the fundamental theorem of arithmetic. Proofs using the fundamental theorem of arithmetic are easier to understand.

Coprime

Definition

If $(a_1,a_2)=1$, then $a_1$ and $a_2$ are called coprime (relatively prime).

If $(a_1,\ldots,a_k)=1$, then $a_1,\ldots,a_k$ are called coprime (relatively prime).

Several integers being coprime does not necessarily mean that they are pairwise coprime. For example, $6$, $10$, and $15$ are coprime, but no two of them are coprime.

The properties of coprimality and the theory of greatest common divisors lead to Bézout's identity. See Bézout's identity.

Euclidean Algorithm

The Euclidean algorithm, also called Euclid's algorithm, is an algorithm. See greatest common divisor.

Prime and Composite Numbers

Algorithms for primes can be found at primes.

Definition

Let $p\ne0,\pm1$ be an integer. If $p$ has no divisors other than its trivial divisors, then $p$ is called a prime (irreducible number).

If an integer $a\ne0,\pm 1$ and $a$ is not prime, then $a$ is called composite.

$p$ and $-p$ are always either both prime or both composite. Unless stated otherwise, “prime” always means a positive prime.

If a factor of an integer is prime, that prime is called a prime factor (prime divisor) of the integer.

Simple properties of primes and composite numbers:

• An integer greater than $1$, denoted $a$, is composite if and only if $a$ can be represented as the product of integers $d$ and $e$ ($1<d,e [!note]+ Arithmetic Fundamental Lemma

Let $p$ be prime. If $p\mid a_1a_2$, then at least one of $p\mid a_1$ and $p\mid a_2$ holds.

With a slight modification of the converse of the fundamental arithmetic lemma, we obtain another definition of a prime.

Another Definition of a Prime

For an integer $p\ne 0,\pm 1$, if for any integers satisfying $p\mid a_1a_2$, namely $a_1,a_2$, either $p\mid a_1$ or $p\mid a_2$ holds, then $p$ is called prime.

Tip

The motivation for this definition can be found in prime ideals.

Fundamental Theorem of Arithmetic (Unique Factorization Theorem)

Let $a$ be a positive integer. Then it has a representation:

$$a=p_1p_2\cdots p_s$$

where $p_j(1\le j\le s)$ are primes. Moreover, this representation is unique up to order.

Standard Prime Factorization

Combining equal primes in the representation above gives:

$$a={p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots{p_s}^{\alpha_s},p_1<p_2<\cdots<p_s$$

This is called the standard prime factorization of the positive integer $a$.

The fundamental theorem of arithmetic and the fundamental arithmetic lemma are equivalent theorems.

Congruence

Definition

Let $m\ne0$ be an integer. If $m\mid(a-b)$, then $m$ is called the modulus (mod), $a$ is congruent to $b$ modulo $m$, and $b$ is a residue of $a$ modulo $m$. This is written $a\equiv b\pmod m$.

Otherwise, $a$ is not congruent to $b$ modulo $m$, and $b$ is not a residue of $a$ modulo $m$. This is written $a\not\equiv b\pmod m$.

An equality of this kind is called a congruence modulo $m$, or simply a congruence.

By the properties of divisibility, the congruence above is also equivalent to $a\equiv b\pmod{(-m)}$.

In what follows, unless stated otherwise, the modulus is always a positive integer.

The $b$ in the expression is a residue of $a$ modulo $m$, and this concept is exactly the same as a remainder. By restricting the range of $b$, we correspondingly obtain the least nonnegative residue, absolute least residue, and least positive residue of $a$ modulo $m$.

Properties of congruences:

• Congruence is an equivalence relation, that is, it has
  • Reflexivity: $a\equiv a\pmod m$.
  • Symmetry: if $a\equiv b\pmod m$, then $b\equiv a\pmod m$.
  • Transitivity: if $a\equiv b\pmod m,b\equiv c\pmod m$, then $a\equiv c\pmod m$.
• Linear operations: if $a,b,c,d\in\mathbf{Z},m\in\mathbf{N}^*,a\equiv b\pmod m,c\equiv d\pmod m$, then:
  • $a\pm c\equiv b\pm d\pmod m$.
  • $a\times c\equiv b\times d\pmod m$.
• Let $f(x)=\sum_{i=0}^n a_ix^i$ and $g(x)=\sum_{i=0}^n b_ix^i$ be two polynomials with integer coefficients, let $m\in\mathbf{N}^*$, and suppose $a_i\equiv b_i\pmod m,~0\leq i\leq n$. Then for every integer $x$, $f(x)\equiv g(x)\pmod m$. Consequently, if $s\equiv t\pmod m$, then $f(s)\equiv g(t)\pmod m$.
• If $a,b\in\mathbf{Z},k,m\in\mathbf{N}^*,a\equiv b\pmod m$, then $ak\equiv bk\pmod{mk}$.
• If $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid a,d\mid b,d\mid m$, then if $a\equiv b\pmod m$, $\dfrac{a}{d}\equiv\dfrac{b}{d}\left(\bmod\;{\dfrac{m}{d}}\right)$.
• If $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*,d\mid m$, then if $a\equiv b\pmod m$, $a\equiv b\pmod d$.
• If $a,b\in\mathbf{Z},d,m\in\mathbf{N}^*$ and $a\equiv b\pmod m$, then $(a,m)=(b,m)$. If $d$ divides $m$ and one of $a,b$, then $d$ must divide the other of $a,b$ as well.

Another property is the multiplicative inverse. See multiplicative inverse.

Congruence Classes and Residue Systems

For convenience, for sets $A,B$ and an element $r$, introduce the following notation:

• $r+A:=\{r+a:a\in A\}$;
• $rA:=\{ra:a\in A\}$;
• $A+B:=\{a+b:a\in A,b\in B\}$;
• $AB:=\{ab:a\in A,b\in B\}$.

Congruence Class

For a nonzero integer $m$, partition all integers into $|m|$ pairwise disjoint sets such that any two numbers in the same set are congruent modulo $m$. We call each of these $|m|$ sets a congruence class or residue class modulo $m$. Write $r\bmod m$ for the congruence class containing the integer $r$ modulo $m$.

It is not difficult to prove that for every nonzero integer $m$, the partition above exists and is unique.

It follows from the definition of congruence classes that:

• $r\bmod m=\{r+km:k\in\mathbf{Z}\}$;
• $r\bmod m=s\bmod m\iff r\equiv s\pmod m$;
• For any $r,s\in\mathbf{Z}$, either $r\bmod m=s\bmod m$ or $(r\bmod m)\cap (s\bmod m)=\varnothing$;
• If $m_1\mid m$, then for every integer $r$, $r+m\mathbf{Z}\subseteq r+m_1\mathbf{Z}$.

Since congruence is an equivalence relation, a congruence class is an equivalence class of the congruence relation.

Let the set of all congruence classes modulo $m$ be denoted by $\mathbf{Z}_m$, that is,

$$\mathbf{Z}_m:=\{r\bmod m:0\leq r<m\}$$

It is easy to see that:

• For every integer $a$, $a+\mathbf{Z}_m=\mathbf{Z}_m$;
• For every integer coprime to $m$, denoted $b$, $b\mathbf{Z}_m=\mathbf{Z}_m$.

By the definition of a quotient group, $\mathbf{Z}_m=\mathbf{Z}/m\mathbf{Z}$, so we sometimes also write $\mathbf{Z}/m\mathbf{Z}$ for $\mathbf{Z}_m$.

The pigeonhole principle gives:

• Among any $m+1$ integers, two are congruent modulo $m$.
• There exist $m$ integers that are pairwise incongruent modulo $m$.

This gives the definition of a complete residue system:

(Complete) Residue System

For $m$ integers $a_1,a_2,\dots,a_m$, if for every number $x$ there is exactly one $a_i$ such that $x$ is congruent to $a_i$ modulo $m$, then these $m$ integers $a_1,a_2,\dots,a_m$ are called a complete residue system, or simply a residue system, modulo $m$.

We can also define the following systems modulo $m$:

• Least nonnegative (complete) residue system: $0,\dots,m-1$;
• Least positive (complete) residue system: $1,\dots,m$;
• Absolute least (complete) residue system: $-\lfloor m/2\rfloor,\dots,-\lfloor -m/2\rfloor-1$;
• Greatest nonpositive (complete) residue system: $-m+1,\dots,0$;
• Greatest negative (complete) residue system: $-m,\dots,-1$.

Unless stated otherwise, we generally use the least nonnegative residue system.

We note that the following proposition holds:

• In any congruence class modulo $m$, any two integers $a_1,a_2$ satisfy $(a_1,m)=(a_2,m)$.

Consider the congruence class $r\bmod m$. If $(r,m)=1$, then every element of this congruence class is coprime to $m$. This suggests that we may be able to determine the structure of the set of all integers coprime to $m$ in a similar way.

Reduced Congruence Class

For a congruence class $r\bmod m$, if $(r,m)=1$, then the class is called a reduced congruence class or reduced residue class.

Denote the number of reduced residue classes modulo $m$ by $\varphi(m)$; this is called the Euler totient function.

Let the set of all reduced congruence classes modulo $m$ be denoted by $\mathbf{Z}_m^*$, that is,

$$\mathbf{Z}_m^*:=\{r\bmod m:0\leq r<m,(r,m)=1\}$$

Warning

For every integer $a$ and every integer coprime to $m$, denoted $b$, $b\mathbf{Z}_m^*=\mathbf{Z}_m^*$, but $a+\mathbf{Z}_m^*$ is not necessarily $\mathbf{Z}_m^*$. This differs from $\mathbf{Z}_m$.

The pigeonhole principle gives:

• Among any $\varphi(m)+1$ integers coprime to $m$, two are congruent modulo $m$.
• There exist $\varphi(m)$ integers coprime to $m$ that are pairwise incongruent modulo $m$.

This gives the definition of a reduced residue system:

Reduced Residue System

For $t=\varphi(m)$ integers $a_1,a_2,\dots,a_t$, if $(a_i,m)=1,~\forall 1\leq i\leq t$, and for every number satisfying $(x,m)=1$, namely $x$, there is exactly one $a_i$ such that $x$ is congruent to $a_i$ modulo $m$, then these $t$ integers $a_1,a_2,\dots,a_t$ are called a reduced residue system, reduced system of residues, or simplified residue system modulo $m$.

Similarly, we can define the least nonnegative reduced residue system and related concepts.

Unless stated otherwise, we generally use the least nonnegative reduced residue system.

Composition of Residue Systems

For a positive integer $m$, we have the following theorem:

• If $m=m_1m_2,~1\leq m_1,m_2$, and $Z_{m_1},Z_{m_2}$ are complete residue systems modulo $m_1,m_2$ respectively, then for any integer coprime to $m_1$, denoted $a$,

  $$Z_m=aZ_{m_1}+m_1Z_{m_2}.$$

  This is a complete residue system modulo $m$. Furthermore, if $m=\prod_{i=1}^k m_i,~1\leq m_1,m_2,\dots,m_k$, and $Z_{m_1},\dots,Z_{m_k}$ are complete residue systems modulo $m_1,\dots,m_k$ respectively, then:

  $$Z_m=\sum_{i=1}^k\left(\prod_{j=1}^{i-1}m_j\right)Z_{m_i}.$$

  This is a complete residue system modulo $m$.

Proof

It is enough to prove that for $ax+m_1y\equiv ax'+m_1y'\pmod{m_1m_2}$, where $x,x'\in Z_{m_1}$ and $y,y'\in Z_{m_2}$, we have:

$$ax+m_1y=ax'+m_1y'.$$

In fact, since $m_1\mid m_1m_2$, we have $ax+m_1y\equiv ax'+m_1y'\pmod{m_1}$, and hence $ax\equiv ax'\pmod{m_1}$. Since $(a,m_1)=1$, we obtain $x\equiv x'\pmod{m_1}$, and therefore $x=x'$.

Furthermore, $m_1y\equiv m_1y'\pmod{m_1m_2}$, so $y\equiv y'\pmod{m_2}$, that is, $y=y'$.

Therefore,

$$ax+m_1y=ax'+m_1y'.$$

• If $m=m_1m_2,~1\leq m_1,m_2,(m_1,m_2)=1$, and $Z_{m_1}^*,Z_{m_2}^*$ are reduced residue systems modulo $m_1,m_2$ respectively, then:

  $$Z_m^*=m_2Z_{m_1}^*+m_1Z_{m_2}^*.$$

  This is a reduced residue system modulo $m$.

Tip

This theorem is equivalent to proving that the Euler totient function is a multiplicative function.

Proof

Let $Z_{m_1},Z_{m_2}$ be complete residue systems modulo $m_1,m_2$, respectively. We have already proved that

$$Z_m=m_2Z_{m_1}+m_1Z_{m_2}$$

is a complete residue system modulo $m$. Let $M=\{a\in Z_m:(a,m)=1\}\subseteq Z_m$. Clearly, $M$ is a reduced residue system modulo $m$, so it is enough to prove $M=Z_m^*$.

Clearly, $Z_m^*\subseteq Z_m$.

Take any $m_2x+m_1y\in M$, where $x\in Z_{m_1}$ and $y\in Z_{m_2}$. We have $(m_2x+m_1y,m_1m_2)=1$, and since $(m_1,m_2)=1$,

$$1=(m_2x+m_1y,m_1)=(m_2x,m_1)=(x,m_1),$$ $$1=(m_2x+m_1y,m_2)=(m_1y,m_2)=(y,m_2).$$

Therefore, $x\in Z_{m_1}^*$ and $y\in Z_{m_2}^*$, so $M\subseteq Z_m^*$.

Take any $m_2x+m_1y\in Z_m^*$, where $x\in Z_{m_1}^*$ and $y\in Z_{m_2}^*$. We have $(x,m_1)=1$ and $(y,m_2)=1$, and since $(m_1,m_2)=1$,

$$(m_2x+m_1y,m_1)=(m_2x,m_1)=(x,m_1)=1,$$ $$(m_2x+m_1y,m_2)=(m_1y,m_2)=(x,m_2)=1,$$

Therefore $(m_2x+m_1y,m_1m_2)=1$, so $Z_m^*\subseteq M$.

In conclusion,

$$Z_m^*=m_2Z_{m_1}^*+m_1Z_{m_2}^*.$$

This is a reduced residue system modulo $m$.

Number-Theoretic Functions

A number-theoretic function (also called an arithmetic function) is a function whose domain is the positive integers. A number-theoretic function can also be viewed as a sequence.

Multiplicative Functions

Definition

In number theory, if a function $f(n)$ satisfies $f(1)=1$ and $f(xy)=f(x)f(y)$ for any coprime $x, y \in\mathbf{N}^*$, then $f(n)$ is a multiplicative function.

In number theory, if a function $f(n)$ satisfies $f(1)=1$ and $f(xy)=f(x)f(y)$ for all $x, y \in\mathbf{N}^*$, then $f(n)$ is a completely multiplicative function.

Properties

If $f(x)$ and $g(x)$ are both multiplicative functions, then the following functions are also multiplicative:

$$\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=\sum_{d\mid x}f(d)g\left(\dfrac{x}{d}\right) \end{aligned}$$

For a positive integer $x$, let its unique prime factorization be $x=\prod p_i^{k_i}$, where $p_i$ are primes.

If $F(x)$ is multiplicative, then $F(x)=\prod F(p_i^{k_i})$.

If $F(x)$ is completely multiplicative, then $F(x)=\prod F(p_i^{k_i})=\prod F(p_i)^{k_i}$.

Examples

• Unit function: $\varepsilon(n)=[n=1]$. (Completely multiplicative)
• Identity function: $\operatorname{id}_k(n)=n^k$; $\operatorname{id}_{1}(n)$ is usually abbreviated as $\operatorname{id}(n)$. (Completely multiplicative)
• Constant function: $1(n)=1$. (Completely multiplicative)
• Divisor function: $\sigma_{k}(n)=\sum_{d\mid n}d^{k}$. $\sigma_{0}(n)$ is usually abbreviated as $d(n)$ or $\tau(n)$, and $\sigma_{1}(n)$ is usually abbreviated as $\sigma(n)$.
• Euler totient function: $\varphi(n)=\sum_{i=1}^n[(i,n)=1]$.
• Möbius function: $\mu(n)=\begin{cases}1&n=1\\0&\exists d>1,d^{2}\mid n\\(-1)^{\omega(n)}&\text{otherwise}\end{cases}$, where $\omega(n)$ denotes the number of distinct prime factors of $n$.

Additive Functions

Definition

In number theory, if a function $f(n)$ satisfies $f(1)=0$ and $f(xy)=f(x)+f(y)$ for any coprime $x, y \in\mathbf{N}^*$, then $f(n)$ is an additive function.

In number theory, if a function $f(n)$ satisfies $f(1)=0$ and $f(xy)=f(x)+f(y)$ for all $x, y \in\mathbf{N}^*$, then $f(n)$ is a completely additive function.

Additive Function

The additive function in this section is the number-theoretic Additive function; it should be distinguished from the Additive map in algebra.

Properties

For a positive integer $x$, let its unique prime factorization be $x=\prod p_i^{k_i}$, where $p_i$ are primes.

If $F(x)$ is additive, then $F(x)=\sum F(p_i^{k_i})$.

If $F(x)$ is completely additive, then $F(x)=\sum F(p_i^{k_i})=\sum F(p_i)\cdot k_i$.

Examples

For convenience, let the set of all primes be $\mathbf P$.

• The multiplicity of $p$ in the prime factorization: $\nu_p(n) = \max\{k\in\mathbf N: p^k\mid n\}$, where $p\in\mathbf P$. (Completely additive)
• The total number of prime factors: $\Omega(n)=\sum_{p \in\mathbf P} \nu_p(n)$. (Completely additive)
• The number of distinct prime factors: $\omega(n)=\sum_{p \in\mathbf P} [p \mid n]$.
• The sum of all prime factors: $a_0(n)=\sum_{p \in\mathbf P} \nu_p(n)\cdot p$. (Completely additive)
• The sum of distinct prime factors: $a_1(n)=\sum_{p \in\mathbf P} [p \mid n] \cdot p$.

Floor and Ceiling Functions

For a real number $x$, define the floor function and ceiling function, respectively, by

$$\lfloor x\rfloor = \max\{k\in\mathbf Z:k\le x\},~\lceil x\rceil = \min\{k\in\mathbf Z:k\ge x\}.$$

Using the floor function, a real number can be decomposed into its integer part and fractional part: $x = \lfloor x\rfloor + \{x\}$. Here, $\{x\}$ denotes the fractional part of $x$.

The floor and ceiling functions have the following basic properties: ($x\in\mathbf R,~n\in\mathbf Z$)

• $x\in\mathbf Z \iff x = \lfloor x\rfloor = \lceil x\rceil$.
• $\lceil x\rceil - \lfloor x\rfloor = [x\notin\mathbf Z]$.
• $x - 1 < \lfloor x\rfloor \le x \le \lceil x\rceil < x + 1$.
• $\lfloor -x\rfloor = -\lceil x\rceil,~\lceil -x\rceil = -\lfloor x\rfloor$.
• $\lfloor x + n\rfloor = \lfloor x\rfloor + n,~\lceil x + n\rceil = \lceil x \rceil + n$.
• Both $\lfloor x\rfloor$ and $\lceil x\rceil$ are monotonically nondecreasing functions of $x$.

When proving equalities involving floor or ceiling functions, the following equivalent forms are often useful: ($x\in\mathbf R,~n\in\mathbf Z$)

• $\lfloor x\rfloor = n \iff n \le x < n + 1 \iff x - 1 < n \le x$.
• $\lceil x\rceil = n \iff n - 1 < x \le n \iff x \le n < x + 1$.

When proving inequalities involving floor or ceiling functions, the following equivalent forms are often useful: ($x\in\mathbf R,~n\in\mathbf Z$)

• $x < n \iff \lfloor x\rfloor < n$.
• $n < x \iff n < \lceil x\rceil$.
• $x \le n \iff \lceil x\rceil \le n$.
• $n \le x \iff n \le \lfloor x\rfloor$.

The properties involving sums and differences are as follows: ($x,y\in\mathbf R$)

• $\lfloor x\rfloor + \lfloor y\rfloor \le \lfloor x + y\rfloor \le \lfloor x\rfloor + \lfloor y\rfloor + 1$, with exactly one equality holding.
• $\lceil x\rceil +\lceil y\rceil -1\leq \lceil x+y\rceil \leq \lceil x\rceil +\lceil y\rceil$, with exactly one equality holding.
• $\lfloor|x - y|\rfloor \le |\lfloor x\rfloor - \lfloor y\rfloor| \le \lceil|x - y|\rceil$.
• $\lfloor|x - y|\rfloor \le |\lceil x\rceil - \lceil y\rceil| \le \lceil|x-y|\rceil$.

The properties involving quotients are as follows: ($x\in\mathbf R,~n\in\mathbf Z,~m\in\mathbf Z_+$)

• $\left\lceil\dfrac{n}{m}\right\rceil = \left\lfloor\dfrac{n+m-1}{m}\right\rfloor,~\left\lfloor\dfrac{n}{m}\right\rfloor = \left\lceil\dfrac{n-m+1}{m}\right\rceil$.
• $\left\lfloor\dfrac{x + n}{m} \right\rfloor = \left\lfloor\dfrac{\lfloor x\rfloor + n}{m} \right\rfloor,~\left\lceil\dfrac{x + n}{m} \right\rceil = \left\lceil\dfrac{\lceil x\rceil + n}{m} \right\rceil$.
• $\left\lfloor\dfrac{\lfloor x/n\rfloor}{m}\right\rfloor = \left\lfloor\dfrac{x}{nm}\right\rfloor,~\left\lceil\dfrac{\lceil x/n\rceil}{m}\right\rceil = \left\lceil\dfrac{x}{nm}\right\rceil$.
• For $x > 0$, $\displaystyle\left\lfloor\dfrac{x}{m}\right\rfloor = \sum_{k=1}^{\lfloor x\rfloor}[m\mid k]$.

The second and third properties can both be viewed as direct consequences of the following result:

• Let $f$ be a continuous, strictly increasing function, and suppose that whenever $f(x)\in\mathbf Z$, we have $x\in\mathbf Z$. Then

  $$\lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor,~ \lceil f(x)\rceil = \lceil f(\lceil x\rceil)\rceil.$$

  ??? note "Proof" By symmetry, it is enough to prove the first equality. If $x$ is an integer, the claim is obvious. Otherwise, $\lfloor x\rfloor < x$. By the monotonicity of $f$ and the floor function, $\lfloor f(x)\rfloor \ge \lfloor f(\lfloor x\rfloor)\rfloor$. If equality does not hold, let $y = \lfloor f(x)\rfloor$. It satisfies $\lfloor f(\lfloor x\rfloor)\rfloor < y \le \lfloor f(x)\rfloor$, which is equivalent to $f(\lfloor x\rfloor) < y \le f(x)$. By the continuity of $f$, there exists $\lfloor x\rfloor < x_0 \le x$ such that $f(x_0)=y$. Since $y\in\mathbf Z$, we have $x_0\in\mathbf Z$, contradicting the definition of $\lfloor x\rfloor$. Therefore equality holds, namely $\lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor$.

Finally, here are some results about sums involving floor and ceiling functions: ($x\in\mathbf R,~n\in\mathbf Z,~m\in\mathbf Z_+$)

• $n = \left\lfloor\dfrac{n}{2}\right\rfloor + \left\lceil\dfrac{n}{2}\right\rceil$.
• $n = \left\lfloor\dfrac{n}{m} \right\rfloor + \left\lfloor\dfrac{n+1}{m} \right\rfloor + \cdots + \left\lfloor\dfrac{n+m-1}{m} \right\rfloor$.
• $n = \left\lceil\dfrac{n}{m} \right\rceil + \left\lceil\dfrac{n-1}{m} \right\rceil + \cdots + \left\lceil\dfrac{n-m+1}{m} \right\rceil$.
• $\lfloor mx\rfloor = \lfloor x\rfloor + \left\lfloor x+\dfrac{1}{m}\right\rfloor + \cdots + \left\lfloor x+\dfrac{m-1}{m}\right\rfloor$.
• $\lceil mx\rceil = \lceil x\rceil + \left\lceil x - \dfrac{1}{m}\right\rceil + \cdots + \left\lceil x - \dfrac{m-1}{m}\right\rceil$.
• If $m\perp n$, then $\displaystyle\sum_{k=1}^{m-1}\left\lfloor\dfrac{kn}{m}\right\rfloor=\dfrac{1}{2}(n-1)(m-1)$.
• If $m\perp n$, then $\displaystyle\sum_{k=1}^{m-1}\left\lceil\dfrac{kn}{m}\right\rceil=\dfrac{1}{2}(n+1)(m-1)$.

Derivations of these and more general sums of similar forms can be found on the Euclidean algorithm page.

More properties and applications of floor and ceiling functions can be found on the following pages:

• Modular arithmetic: $n\bmod m = n - \left\lfloor\dfrac{n}{m}\right\rfloor m$. It can be used for optimizing integer modulo operations.
• Use Gauss's lemma to prove the quadratic reciprocity law.
• Number-theoretic block decomposition, especially the proof of its properties.
• Legendre's formula for calculating the exponent of a prime factor in a factorial.
• Beatty sequences, Rayleigh's theorem, and the Wythoff game.

References and Notes

• Pan Chengdong, Pan Chengbiao. Elementary Number Theory. Peking University Press.
• Floor and ceiling functions - Wikipedia
• Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. "Concrete mathematics: a foundation for computer science." (1989).

Footnotes

1. std::gcd - cppreference.com ↩