# Maximum size of linearly independent subsets of $\mathbb{Z}/m\mathbb{Z}$

Consider the integers modulo $m$, for composite $m$. Then an element $x$ only has a multiplicative inverse if it is relatively prime to $m$. Therefore, it is possible to have a set of more than one element, so that no element in the set can be written as a linear combination of the others; call such a set linearly independent. For example, $\{2,3\}$ is linearly independent mod 6.

1. What is the largest size of a maximum independent subset of the integers mod $m$, for arbitrary $m$? Can this be expressed in terms of the factors of $m$?

2. Conversely, given an arbitrary set $S \subseteq \mathbb{Z}/m\mathbb{Z}$, can we give an upper bound on the size of a smallest spanning subset $S'$ of $S$ in terms of the factors of $m$?

(Apologies if this question is too elementary; it came up in research in algorithm design.)

A subset $S$, $|S|>1$, is linearly independent if and only for any $a\in S$ there exists a prime $p|m$ such that $\nu_p(a)<\nu_p(b)$ for all $b\in S\setminus \{a\}$. Here $\nu_p(a)$ denotes the maximal $k$ such that $p^k$ divides both $a$ and $m$. Indeed, if it is the case, then $a$ is not a linear combination of other elements of $S$ simply modulo $p^{\nu_p(a)+1}$. But if there is no such $p$, then $a$ is divisible by the greatest common divisor of the set of integers $m\cup (S\setminus \{a\})$, hence it is a linear combination of the elements of this set.
Thus the answer to your question 1 is 'number of distinct prime divisors of $n$.' And the same numbers is always an upper bound for minimal $|S'|$ in question 2 (for any prime divisor $p$ of $m$ take to $S'$ an element of $S$ divisible by the smallest power of $p$.)
• I use only the following claim: the ideal of $\mathbb{Z}$ generated by a set $T$ is generated by an element $d=$gcd$(T)$, this is a common knowledge. – Fedor Petrov Nov 29 '16 at 12:21