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

| cite | improve this answer | |
  • $\begingroup$ Very elegant solution, thanks a lot! Do you have a reference for this material? $\endgroup$ – Bart Jansen Nov 29 '16 at 11:56
  • $\begingroup$ 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. $\endgroup$ – Fedor Petrov Nov 29 '16 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.