Integer Constraints via Linear Independence

In this article, we study a fascinating problem that beautifully bridges elementary number theory and linear algebra.

Despite its discrete setup, this problem can be solved by mapping exponents of primes into a vector space and applying dimension constraints.

Problem

Let $a_1 < a_2 < \dots < a_n \le x$ be a set of positive integers such that no $a_i$ divides the product of the others. Prove that $n \le \pi(x)$.

Solution

Let $m = \pi(x)$ be the number of primes less than or equal to $x$. Let these primes be denoted as $p_1, p_2, \dots, p_m$.

Since every integer $a_i$ is less than or equal to $x$, its prime factorization can only consist of primes from this set. We can write each $a_i$ as

\[a_i = p_1^{e_{i,1}} p_2^{e_{i,2}} \cdots p_m^{e_{i,m}}\]

where each exponent $e_{i,j} \ge 0$ is an integer.

Vector Representation of Exponents

We map each integer $a_i$ to an exponent vector in the real vector space $\mathbb{R}^m$

\[v_i = (e_{i,1}, e_{i,2}, \dots, e_{i,m})\]

The Divisibility Condition

The problem states that for any $i$, $a_i$ does not divide the product $\prod_{j \neq i} a_j$.

In terms of prime factorizations, $a \mid b$ if and only if every prime exponent in $a$ is less than or equal to the corresponding prime exponent in $b$. Because $a_i$ does not divide the product of the others, there must exist at least one specific prime index $k$ (where $1 \le k \le m$) such that the exponent of $p_k$ in $a_i$ is strictly greater than the sum of the exponents of $p_k$ in all other numbers

\[e_{i,k} > \sum_{j \neq i} e_{j,k}\]

Proving Linear Independence

Suppose for contradiction that the vectors $v_1, \dots, v_n$ are linearly dependent. Then there exists $c_1, \dots, c_n$, not all zero, such that

\[\sum_{j=1}^n c_j v_j = \mathbf{0}\]

Since not all coefficients are zero, let $i$ be the index such that \(|c_i| = \max{(|c_1|,|c_2|, \dots, |c_n|)}.\)

Consider the $k^{th}$ coordinate of the linear combination, \(\sum_{j=1}^n c_j v_j = \mathbf{0}\), we have

\[c_i e_{i,k} + \sum_{j \neq i} c_j e_{j,k} = 0\]

Rearranging the terms,

\[c_i e_{i,k} = - \sum_{j \neq i} c_j e_{j,k}\]

Taking the absolute value of both sides and applying the triangle inequality,

\[|c_i| e_{i,k} = \left| \sum_{j \neq i} c_j e_{j,k} \right| \le \sum_{j \neq i} |c_j| e_{j,k}\]

Since $|c_i| \ge |c_j|$,

\[|c_i| e_{i,k} \le \sum_{j \neq i} |c_i| e_{j,k}\] \[e_{i,k} \le \sum_{j \neq i} e_{j,k}\]

This contradicts the established fact above that \(e_{i,k} > \sum_{j \neq i} e_{j,k}\).

Dimension Constraint

Because the assumption of linear dependence leads to a contradiction, the set of vectors ${v_1, v_2, \dots, v_n}$ must be linearly independent.

We now have $n$ linearly independent vectors residing in $\mathbb{R}^m$. A fundamental theorem of linear algebra states that the number of linearly independent vectors in a finite-dimensional vector space cannot exceed the dimension of that space.

Therefore, $n \le m$. Since $m = \pi(x)$, we conclude that

\[\boxed{n \le \pi(x)}\]

Note: This method reflects a broader mathematical principle. Discrete algebraic structures can be embedded into vector spaces where multiplicative relations become additive and structural constraints become linear. Dimension bounds then limit how complex such systems can be. Similar representation ideas appear in quantitative modeling, where discrete features are encoded into continuous vector spaces to enable geometric and linear analysis.