Divisibility theory

In mathematics, divisibility theory is a branch of abstract algebra concerned with the study of divisibility relations in rings and algebraic structures arising from these relations.

The main object of study is a ring $A$, in which for elements:

$a,b\in A$

the relation is defined:

$a\mid b$

meaning that:

$\mathrm{\exists }c\in A:b=ac$.

Elements of divisibility

Divisor

Main article: Divisor

Let $a,b\in A$.

An element $a$ is called a divisor of an element $b$ if:

$a\mid b$.

Equivalently, there exists an element:

$r\in A$

such that:

$b=ar$.

The set of all divisors of an element $b$ is sometimes denoted by:

$\mathrm{Div}(b)$.

In the ring of integers, for example:

$1,2,3,6$

are the positive divisors of:

$6$.

Multiple

Main article: Multiple

Let $a,b\in A$.

An element $b$ is called a multiple of an element $a$ if:

$a\mid b$.

This means that there exists an element:

$r\in A$

such that:

$b=ar$.

Every multiple of an element $a$ is obtained by multiplying it by some element of the ring.

In the set of natural numbers, multiples of:

$4$

include:

$4,8,12,16,20,\dots$.

If:

$a\mid b$,

then $a$ is a divisor of $b$, and $b$ is a multiple of $a$.

Associated elements

Main article: Unit (ring theory)

Elements:

$a,b\in A$

are called associated if there exists a unit:

$u\in A^{\times }$

such that:

$a=ub$.

This is denoted by:

$a\sim b$.

After identifying associated elements, the divisibility relation becomes a partial order.

Operations on divisibility

Divisibility relation

Main article: Divisibility (ring theory)

The divisibility relation is a binary relation defined on elements of a ring.

For elements $a,b,c\in A$, we say that $a$ divides $b$ (denoted $a\mid b$) if there exists an element $r\in A$ such that:

$b=a\cdot r$.

The divisibility relation has the following properties:

Reflexivity

The relation is reflexive because every element divides itself:

$a\mid a$.

Indeed:

$a=a\cdot 1$,

so there exists the element $1$ in the ring such that multiplying by it yields $a$ again.

Transitivity

If:

$a\mid b$ and $b\mid c$,

then:

$a\mid c$.

From the first condition, there exists $r\in A$ such that:

$b=a\cdot r$.

From the second condition, there exists $s\in A$ such that:

$c=b\cdot s$.

Substituting:

$c=(a\cdot r)\cdot s=a\cdot (r\cdot s)$.

Since $r\cdot s\in A$, it follows that:

$a\mid c$.

Association relation

Because antisymmetry does not hold in general, the association relation is introduced.

We say that elements $a,b\in A$ are associated if there exists a unit element $u\in A$ such that:

$a=b\cdot u$.

This means that two elements are associated if they differ only by multiplication by an invertible element of the ring.

In particular:

$a\sim b$

is equivalent to:

$a\mid b$ and $b\mid a$.

Greatest common divisor

Main article: Greatest common divisor

Let $a,b\in A$. An element $d\in A$ is called the greatest common divisor of $a$ and $b$ if:

$d\mid a$

and:

$d\mid b$

and for every element $c\in A$ satisfying:

$c\mid a$ and $c\mid b$

we have:

$c\mid d$.

It is denoted by:

$\gcd (a,b)$.

For any finite sequence $a_1,a_2,\dots ,a_n\in A$, the iterated gcd is defined:

$\underset{k=1}{\stackrel{n}{\gcd }}(a_k)=\gcd (a_1,a_2,\dots ,a_n)$.

The gcd operation selects the greatest element dividing all arguments and combines them into a single element representing their common part:

$\gcd (a,b)\leftrightarrow a\cdot b$.

Least common multiple

Main article: Least common multiple

An element $m\in A$ is called the least common multiple of $a,b\in A$ if:

$a\mid m$

and:

$b\mid m$

and for every:

$x\in A$

such that:

$a\mid x$ and $b\mid x$

we have:

$m\mid x$.

It is denoted by:

$\mathrm{lcm}(a,b)$.

For any finite sequence $a_1,a_2,\dots ,a_n\in A$:

$\underset{k=1}{\stackrel{n}{\mathrm{lcm}}}(a_k)=\mathrm{lcm}(a_1,a_2,\dots ,a_n)$.

The lcm operation selects the smallest element that is a common multiple of all arguments:

$\mathrm{lcm}(a,b)\leftrightarrow a+b$.

Divisibility lattice

In many rings, the set of association classes under divisibility forms a lattice structure.

For elements:

$a,b\in A$

we distinguish:

• greatest common divisor,
• least common multiple.

Connection with ideals

Divisibility is closely related to principal ideals.

For:

$a,b\in A$

we have:

$a\mid b$

if and only if:

$b\in (a)$.

Divisibility of polynomials

Main article: Polynomial

The theory of divisibility can also be developed in polynomial rings.

For polynomials:

$f(x),g(x)\in K[x]$

we say that:

$f(x)\mid g(x)$

if there exists a polynomial:

$q(x)\in K[x]$

such that:

$g(x)=f(x)q(x)$.

For example:

$x+1\mid x^2-1$

since:

$x^2-1=(x+1)(x-1)$.

In polynomial rings over a field there exist analogues of:

• the greatest common divisor,
• the least common multiple,
• the Euclidean algorithm.

Polynomial divisibility plays an important role in algebra, field theory, and algebraic geometry.

Divisibility theory of integers

The ring of integers $\mathbb{\mathbb{Z}}$ is one of the main examples of an integral domain in divisibility theory.

Divisibility is defined by:

$a\mid b⟺\mathrm{\exists }k\in \mathbb{\mathbb{Z}}:b=ak$.

The units in $\mathbb{\mathbb{Z}}$ are:

$1,-1$.

Therefore:

$a\sim b$

if and only if:

$a=\pm b$.

In $\mathbb{\mathbb{Z}}$, every nonzero element can be expressed as a product of prime elements.

Divisibility theory of natural numbers

The set of natural numbers $\mathbb{\mathbb{N}}$ with divisibility is a fundamental example of divisibility theory.

For:

$a,b\in \mathbb{\mathbb{N}}$

we have:

$a\mid b⟺\mathrm{\exists }k\in \mathbb{\mathbb{N}}:b=ak$.

Example:

$4\mid 20$

since:

$20=4\cdot 5$.

In $\mathbb{\mathbb{N}}$, both exist:

• the greatest common divisor,
• the least common multiple.

Moreover:

$\gcd (a,b)\cdot \mathrm{lcm}(a,b)=a\cdot b$.

Prime numbers

Main article: Prime number

In divisibility theory of natural numbers, prime numbers play a fundamental role.

The set of prime numbers $\mathbb{\mathbb{P}}$ is defined as:

$\mathbb{\mathbb{P}}:=\{p\in \mathbb{\mathbb{N}}:p>1\wedge \mathrm{\neg }\mathrm{\exists }d\in \mathbb{\mathbb{N}}(1<d<p\wedge d\mid p)\}$.

Examples of prime numbers include:

$2,3,5,7,11,13,\dots$.

Modular arithmetic

Main article: Modular arithmetic

Divisibility is closely related to the notion of congruence modulo.

For integers:

$a,b,m\in \mathbb{\mathbb{Z}}$

with:

$m>0$

we write:

$a\equiv b(\mathrm{mod}m)$

if:

$m\mid (a-b)$.

This means that the difference between $a$ and $b$ is divisible by $m$.

For example:

$17\equiv 5(\mathrm{mod}12)$

since:

$12\mid (17-5)$.

Modular arithmetic is used in:

• number theory,
• cryptography,
• computer science,
• coding theory.

Many properties of divisibility can be expressed using congruences.

Prime elements

Main article: Prime element

An element $p\in A$ is called prime if $p$ is not a unit and whenever $p\mid ab$, then $p\mid a$ or $p\mid b$.

Prime elements are fundamental building blocks of multiplicative decompositions.

Irreducible elements

Main article: Irreducible element

An element $a\in A$ is called irreducible if $a\ne 0$ and whenever $a=bc$, then either $b$ or $c$ is a unit.

In general, every prime element is irreducible, but the converse does not always hold.

Factorization

Main article: Factorization

One of the central problems in divisibility theory is expressing elements as products of irreducible or prime elements. In unique factorization domains, every nonzero, non-unit element admits a factorization that is unique up to ordering and association of factors.

Unique factorization domains

Main article: Unique factorization domain

A ring $A$ is called a unique factorization domain (UFD) if every nonzero, non-unit element has a factorization into irreducible elements that is unique up to ordering and associated elements.

Euclidean domains

Main article: Euclidean domain

A ring $A$ is called Euclidean if there exists a function:

$d:A\setminus \{0\}\to \mathbb{\mathbb{N}}$

allowing division with remainder.

Every Euclidean domain is:

• a principal ideal domain,
• a unique factorization domain.

Euclidean algorithm

Main article: Euclidean algorithm

In the ring of integers, the greatest common divisor can be computed using the Euclidean algorithm.

If:

$a=bq+r$

then:

$\gcd (a,b)=\gcd (b,r)$.

This algorithm is one of the fundamental tools of divisibility theory.

Applications

Divisibility theory is used in:

• Number theory,
• Cryptography,
• Ring theory,
• Algebraic geometry.

It is used, among others, to study:

• structures of ideals,
• factorization algorithms,
• properties of prime numbers.

References

This article "Divisibility theory" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Divisibility theory. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---