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.)



Maximum size of linearly independent subsets of $\mathbb{Z}/m\mathbb{Z}$
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$.)


