Divisibility, Co-primes, and Euler’s Totient on the Prime Vector Grid

Michael Emmerich – 29 June 2025

1. Introduction

Positive integers and their fundamental building blocks, the prime numbers, exhibit a rich combinatorial structure. This essay is part of a series that aims to derive some of the intriguing properties of integers using only elementary mathematical tools, thereby making them accessible to a broader audience. We do this by adopting the prime-vector representation (Emmerich, 2025), in which rational numbers can be placed naturally on a grid whose axes correspond to prime bases and their exponents. In this picture, number theory becomes a combinatorial game of rearranging positions on the grid and counting possibilities.

In this essay, we revisit the fundamental notions four: coprimality, divisibility, and the arithmetic functions that measure them, in particular the Euler totient function, through the lens of representation of the prime vector (Emmerich, 2025). By recasting every positive rational as a vector of prime exponents, arithmetic collapses to ordinary integer addition and subtraction of coordinates. Within this coordinate system

coprimality and the totient function emerge as simple sign-pattern conditions on pairs of prime vectors;
divisibility properties translate to component-wise ordering of vectors; and
the divisor-counting function ${\tau(n)}$ becomes a lattice-point enumeration problem.

Special attention is given to Euler’s totient function, which has a nice interpretation in a group-partition scheme, which we will also employ to reprove Gauss’s sum of totients lemma. This lemma provides one interesting bridge between additive and multiplicative structures in positive integers.

2. Prime-Vectors

Let us briefly review the basics of the prime vector representation, as introduced in (Emmerich, 2025). Prime vectors are in several aspects a convenient representation of positive rational numbers. Prime vectors make it possible to handle rational numbers in their reduced form, using only integers in their representation, and to combine integers, as well as positive integers, multi-dimensionally by means of integer vector addition and subtraction. Let ${\{p_1,p_2,p_3,\dots\}=\{2,3,5,\dots\}}$ be the ordered primes. Every positive rational number ${q}$ factors uniquely as

$\displaystyle q=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots , \qquad a_i\in\mathbb Z,$

and is represented by its prime vector

$\displaystyle P(q)=\bigl(a_1,a_2,a_3,\dots\bigr)\in\mathbb Z^{\infty},$

with only finitely many non-zero entries. In this representation, multiplication and division of rational numbers can be reduced to integer addition and subtraction.

Lemma 1 (Component-wise operations) For all positive rationals ${q_1,q_2}$
$\displaystyle P(q_1q_2)=P(q_1)+P(q_2), \qquad P\!\left(\frac{q_1}{q_2}\right)=P(q_1)-P(q_2),$

where the addition/subtraction is component-wise.

The beauty of this reformulation of integer division and multiplication is that these operations can now be naturally performed as simple geometric shifting operations on a grid with the coordinate axis being the prime bases and their exponents. See Figure 1 for an example.

Another notable advantage of the prime vector representation is that it encapsulates rational numbers in their simplified or reduced form, where the numerator is denoted by the positive component, and the divisor is denoted by the negative component (Emmerich, 2025). For example, the prime vector ${(2,-1,-1,1, 0,\dots)}$ uniquely represents the fraction ${2\cdot2\cdot7 / 3\cdot 5 = 28/15}$ .

Observe the analogy with logarithmic rules; however, in this framework, all computations are purely integer-based, avoiding the use of transcendental numbers altogether.

3. Divisibility

It is well known that all divisors of a positive integer can be constructed by combinations of its prime factors. Then it is easy to verify the following theorems that relate prime vectors to divisors.

Lemma 2 Let ${n}$ and ${k}$ denote two positive integers with ${k\leq n}$ then ${k}$ divides ${n}$ (in symbols: ${k \mid n}$ , iff ${P(n)-P(k) \geq 0}$ , i.e. the difference of the prime vectors has only non-negative components.

and we can now find the set of all divisors.

Lemma 3 The set of all positive integer divisors of the positive integer ${n}$ with ${P(n)=(a_1, a_2, \dots)}$ is provided by ${\{ (b_1, b_2, \dots ) \in \mathbb{N}_{0}^* : (b_1 \leq a_1), ( b_2 \leq a_2), \dots)\},}$ and we can count the number of divisors by product: ${(a_1+1)\cdot (a_2+1) \cdot \dots}$ .

Example: Let us find the divisors of ${12}$ . In the prime vector notation, 12 is represented as ${(2,1,0, 0, \dots)}$ . Thus we can find its set of divisors as ${(0, \dots)}$ , ${(1,0, \dots)}$ , ${(2,0 \dots)}$ , ${(0,1,0, \dots)}$ , ${(1,1,0, \dots)}$ , ${(2,1,0, \dots)}$ . And these are ${(2+1) \cdot (1+1) = 6}$ divisors.

4. Co-primality

Co-primality can be regarded as the conceptual antithesis to divisibility. In this context, the focus is on identifying integers whose sets of prime factors exhibit no commonality.

Lemma 4 (Coprimality criterion) Let ${\mathbf a=(a_i)}$ and ${\mathbf b=(b_i)}$ be the prime vectors of two positive integers. They are co-prime if and only if their positive coordinates do not overlap, that is:
$\displaystyle \forall i : a_i>0\Longrightarrow b_i=0 \quad\text{and}\quad b_i>0\Longrightarrow a_i=0.$

Example. Let ${ q_1 = 18 = 2 \cdot 3^2 }$ and ${ q_2 = 25 = 5^2 }$ . Then:
$\displaystyle P(q_1) = (1,2,0,0,\dots), \qquad P(q_2) = (0,0,2,0,\dots),$
and their positive coordinates are in disjoint positions. Hence, ${ q_1 }$ and ${ q_2 }$ are co-prime.
In contrast, let ${ q_3 = 12 = 2^2 \cdot 3 }$ , so ${ P(q_3) = (2,1,0,0,\dots) }$ . Then ${ P(q_1) }$ and ${ P(q_3) }$ both have positive entries in the same indices, so ${ q_1 }$ and ${ q_3 }$ are not co-prime.

Corollary 5 (Sign pattern of the difference) For coprime integer vectors ${ \mathbf a, \mathbf b }$ ,
$\displaystyle \mathbf a - \mathbf b = (a_i - b_i)_i$
is exactly positive at the coordinates where ${ \mathbf a }$ is positive and negative exactly where ${ \mathbf b }$ is positive.
Equivalently,
$\displaystyle \mathbf a = \bigl(\mathbf a - \mathbf b\bigr)^{+}, \quad \text{where } \mathbf x^{+} := \max(0, x_i)\text{ component-wise.}$

Remark 1 Observe that the positive part of a prime vector ${\mathbf x}$ which we denote with ${\mathbf x^+}$ can be interpreted as the prime vector of the numerator, while the analogously defined negative part of a prime vector ${\mathbf x}$ denoted with ${\mathbf x^-} (= \min(0, x_i))$ serves as the prime vector of the divisor in the simplified fraction ${P^{-1}(\mathbf{x})}$ . Take, for example, the vector ${(1,2,-2,0,...)}$ , which corresponds to the fraction ${\frac{2*9}{3*3}=\frac{18}{25}}$ .

Example. Using the co-prime ${ q_1 = 18 }$ and ${ q_2 = 25 }$ from above:

$\displaystyle \mathbf a = P(18) = (1,2,0,\dots), \quad \mathbf b = P(25) = (0,0,2,0,\dots),$

$\displaystyle \mathbf a - \mathbf b = (1,2,-2,0,\dots), \quad (\mathbf a - \mathbf b)^+ = (1,2,0,0,\dots) = \mathbf a.$

5. Euler’s totient function

Euler’s totient function ${\varphi(n)}$ counts how many positive integers smaller than ${n}$ are relatively prime to ${n}$ (that is, co-prime). Its deceptively simple definition conceals a web of deep connections: It drives Euler’s theorem and the RSA cryptosystem, linking multiplication and addition through prime factors and divisors, which themselves can be viewed as recombinations of the main constituents of a number.

Definition 6 (Euler’s totient) For a positive integer ${n}$ the Euler totient is defined as
$\displaystyle \varphi(n)=\#\{\,k\in\{1,\dots ,n\}\mid\gcd(k,n)=1\,\}$
with ${\gcd(k,n)}$ being the largest common divisor.

The arithmetic function ${\varphi}$ was studied systematically by Euler (cf. Euler, 1763); the noun totient was introduced by Sylvester according to (Tou, 2017). It turns out that Euler’s totient function can be computed using a remarkably simple formula, which follows directly from the elementary number theory (see, e.g., Wilson, 2020).

Lemma 7 Let ${ q = p_1^{a_1} p_2^{a_2} p_3^{a_3} \dots }$ be the prime factorization of a positive integer ${ q }$ . Then:
$\displaystyle \varphi(q) = p_1^{a_1 - 1}(p_1 - 1)\, p_2^{a_2 - 1}(p_2 - 1)\, p_3^{a_3 - 1}(p_3 - 1) \dots$

Proof: The totient function ${\varphi(q)}$ counts the number of positive integers less than or equal to ${q}$ that are co-prime to ${q}$ .

Let us first compute the formula for the totient of a prime power:

$\displaystyle \varphi(p^a) = p^a - p^{a-1} = p^a \left(1 - \frac{1}{p}\right).$

We are counting the number of integers ${ 1 \leq k \leq p^a }$ that are coprime to ${ p^a }$ . The only integers not coprime to ${ p^a }$ are those divisible by ${ p }$ , i.e., the multiples of ${ p }$ up to ${ p^a }$ . In total, there are ${ \frac{p^a}{p} = p^{a-1} }$ such numbers. Therefore, the count of integers coprime to ${ p^a }$ is: ${\varphi(p^a) = p^a - p^{a-1}.}$ . Since the totient function is multiplicative for coprime arguments, we have:

$\displaystyle \varphi(q) = p_1^{a_1 - 1}(p_1 - 1)\, p_2^{a_2 - 1}(p_2 - 1)\, p_3^{a_3 - 1}(p_3 - 1) \dots$

as claimed. $\Box$

6. Euler’s Totient Function from a Prime-Vector Perspective

We now characterize Euler’s totient function in terms of prime vectors. Fix a positive integer ${ n \in \mathbb{N} }$ . For each ${ 1 \le i < n }$ , define the prime vector difference.

$\displaystyle \Delta_i = P(n) - P(i) = P(n/i).$

Then ${ \gcd(i, n) = 1 }$ if and only if

$\displaystyle \bigl(\Delta_i\bigr)^+ = P(n),$

i.e., the positive part of the vector difference recovers the original vector ${ P(n) }$ . This leads to the following alternative formulation of the totient function:

Corollary 8 (Totient count via prime vectors) Let ${ n \in \mathbb{N} }$ . Then:
$\displaystyle \varphi(n) = \# \left\{\, i < n \middle| \bigl(P(n) - P(i)\bigr)^+ = P(n) \right\}.$

Example: For ${ n = 12 }$ in Figure 2, we compute all values ${ P(12/i) = P(12) - P(i) }$ and group them by their positive parts ${ \bigl(P(12/i)\bigr)^+ }$ . The group ${A}$ is the subset with the property ${\bigl(P(n) - P(i)\bigr)^+ = P(n)}$ and its size is the value ${\varphi(12)=4}$ .

This structure reveals a natural path to Gauss’s classical identity:

Theorem 9 (Gauss’ sum of totients identity) For every positive integer ${ n }$ ,
$\displaystyle \sum_{d \mid n} \varphi(d) = n.$

Before stating a proof of this theorem, which was first proved by Gauss (Gauss, 1801) let us look at an example.

Example: Let us looking at the sum of totient rule for the example ${n=12}$ where in in Figure 2 we form groups by positive parts of the prime vectors of ${P(n/i)}$ , ${i=1,\dots, 12}$ .

Group A ${q=1, d=12}$	${(2,1,0,0,0)=P(12)}$ , indices ${1,5,7,11}$ ( ${4=\varphi(12)}$ )
Group B ${q=6, d=6}$	${(1,1,0,0,0)=P(6)}$ , indices ${2,10}$ ( ${2=\varphi(6)}$ )
Group C ${q=3, d=4}$	${(2,0,0,0,0)=P(4)}$ , indices ${3,9}$ ( ${2=\varphi(4)}$ )
Group D ${q=4, d=3}$	${(0,1,0,0,0)=P(3)}$ , indices ${4,8}$ ( ${2=\varphi(3)}$ )
Group E ${q=6, d=2}$	${(1,0,0,0,0)=P(2)}$ , indices ${6}$ ( ${1=\varphi(2)}$ )
Group F ${q=12, d=1}$	${(0,0,0,0,0)=P(1)}$ , index ${12}$ ( ${1=\varphi(1)}$ )

Adding the group sizes ${4+2+2+2+1+1}$ reproduces ${12}$ , exactly as Gauss’s theorem predicts.

Let us now proof Gauss’s sum of totient identity by making some use of prime vector notation. Let ${ P(n) = (n_1, n_2, \dots) }$ be the prime vector of ${ n }$ . For each ${ i = 1, \dots, n }$ , define the row (as in Figure 2:

$\displaystyle (i, n/i, P(n/i), P(n/i)^+).$

Note that the unique prime vector representation of the reduced-form rationals ensures that all rows are distinct (see (Emmerich,2025)), so we get exactly ${n}$ distinct rows.

Group the rows by their fourth entry, the positive part ${P(n/i)^+}$ . This yields a partition.

$\displaystyle \Pi_n = \{G_1,\dots,G_k\}$

of the index set ${\{1,\dots,n\}}$ .

Each block ${G_j}$ can be associated with a divisor ${d_j \mid n}$ ; The divisor is given by ${P(n/i)^+}$ and it is easy to verify that ${P(n/i)^+}$ is a divisor, since ${P(n/i)^+ \leq P(n)}$ , componentwise.

Lemma 10 shows that the size of a group ${G_j}$ is associated with the divisor ${d_j}$ of ${n}$ precisely is the totient of ${d_j}$ , in other words ${\# G_j = \varphi(d_j)}$ .

Lemma 10 (Lemma on Group Sizes) For a block ${G_j \in \Pi_n}$ choose any index ${\ell \in G_j}$ and set
$\displaystyle d_j := P^{-1}(P\!\bigl(n/\ell\bigr)^+).$

Then ${\# G_j = \varphi(d_j)}$ .

Proof: Firstly, let us explain why a group ${G_j}$ is at least the size of the number of coprimes of to ${d_j = d(G_j)}$ . Fix the group and ${q_j = n/d_j}$ . The complete set of integer divisors is ${\{1, ..., n\}}$ , and includes the numbers ${1, 1 \cdot q_j, \dots, k \cdot q_j, \dots, d_j \cdot q_j }$ . We can now perform the divisions ${n/i}$ in two steps as illustrated below:

$\displaystyle \underbrace{(n / q_j)}_{=d_j} / 1, \dots ,\underbrace{(n / q_j)}_{=d_j} / d_j.$

The first step is to divide ${n}$ by ${q_j}$ and we obtain ${d_j = n/q_j}$ . then we divide by ${k}$ to obtain ${d_j/k}$ , ${k \in 1, \dots, d(i)}$ , and only in the case where ${j}$ is a co-prime ${d(i)}$ we have ${P(d_j) = P(d_j/k)^+}$ .

Let us now argue why no additional elements to the ones discussed above can join the group ${G_j}$ : Let us consider two cases for ${\ell \in L}$ :

Firstly, consider ${d_j\mid \ell}$ . In this case ${d_j q_j = \ell}$ with ${q_j}$ being an integer that due to the definition of ${L}$ is not coprime with ${d_j}$ . Hence, when dividing ${n/q_j}$ we do not get ${(P(n/\ell))^+ = P(d_j)}$ .

Secondly, consider the other case, that is, ${d_j \nmid \ell}$ . Then it is also impossible to get ${(P(n/\ell))^+ = P(d_j)}$ because ${P(\ell)}$ and ${P(d_j)}$ consists of only positive integer components and ${P(n) - P(\ell)^+ \neq P(d_j))^+}$ . Thus, we conclude the proof of the auxiliary lemma. $\Box$

The sum of totient lemma follows from the auxiliary lemma and the fact that the group sizes sum up to ${n}$ , as each prime vector ${n/i}$ , ${i=1, ..., n}$ belongs to exactly one of the groups.

The foregoing argument closely mirrors the classical proof that counts reduced fractions. However, expressed in prime-vector language, every rational automatically appears in lowest terms because each exponent is split into its positive and negative parts. This coordinate-wise view might make the divisibility reasoning more transparent.

7. Conclusion

Expressing numbers in prime-vector form makes questions of divisibility and related prime-number properties surprisingly transparent. In this framework we were able to give elementary derivations for criteria of coprimality, the divisor function ${\tau(n)}$ , and Euler’s totient ${\varphi(n)}$ .

So far, however, prime-vector notation has not produced decisively simpler proofs of the deeper results about ${\varphi(n)}$ , nor has it resolved the classic open problems of prime-number theory. A striking example is Carmichael’s conjecture, which asserts that every value taken by~ ${\varphi}$ is attained by at least two distinct integers —a statement that remains unproved.

Computer science reminds us that choosing the right data structure can turn an opaque problem into an elegant algorithm. By analogy, refining number representations that are tailored to arithmetic structure may yet unlock new methods for studying the positive integers. Pursuing such representations — and the combinatorial reasoning they invite — therefore appears to be a promising direction for further research.

References

Emmerich, M. T. M. (2025, January 12). On prime vectors and unique factorization of rationals. Mathematical Playground. http://www.emmerix.net

L. Euler, Theorematum quorundam ad numeros primos spectantium demonstratio (A proof of certain theorems regarding prime numbers), Commentarii Academiae Scientiarum Petropolitanae 8 (1741), 141–146. Eneström index E54. Latin original and an English translation by D. Zhao available at the Euler Archive.

L. Euler, Theoremata arithmetica nova methodo demonstrata (Demonstration of a new method in the theory of arithmetic), Novi Commentarii Academiae Scientiarum Petropolitanae 8 (1763), 74–104. Eneström index E271. Facsimile at the Euler Archive.

L. Euler, Speculationes circa quasdam insignes proprietates numerorum (Speculations about certain outstanding properties of numbers), Acta Academiae Scientarum Imperialis Petropolitinae 4 (1784), 18–30. Eneström index E564. Latin original and an English translation by J. Bell available at the Euler Archive.

C. F. Gauss, Disquisitiones Arithmeticae. Leipzig: Gerhard Fleischer, 1801. (English translation by A. A. Clarke, Yale University Press, 1965.)

E.R. Tou, “Math Origins: The Totient Function,” Convergence (MAA), September 2017. DOI:\,10.4169/convergence20170923.

R. Wilson, Number Theory: A Very Short Introduction, Oxford University Press, 2020.

Divisibility, Co-primes, and Euler’s Totient on the Prime Vector Grid

Share this:

Leave a comment Cancel reply