Null Space Modulo A Non-Prime Integer

Question

Suppose I have some matrix $A$. I can find the null vectors of $A\mod3$ and $A\mod5$ in the math software that I use, but when I try to find the nullspace of $A\mod15$ I am given the error that the modulus is composite. I assume that this has to do with the fact that $15$ is not prime. My question is, do there exist nullvectors of $A\mod15$ such that these nullvectors are not a linear combination of the nullvectors from $A\mod3$ and $A\mod5$?

Answer 1

You're right, the issue with your software is that 15 isn't a prime number, so integers modulo 15 are not a field (meaning: don't have a division operation). Your software may use division to find the null space via row reduction. Related, the mod 15 "vectors" you are multiplying $A$ by technically don't live in a vector space, by definition, since scalars are required to come from a field. Putting terminology issues aside...

Every null vector mod 15 reduces, mod 3 and mod 5, to a null vector. Conversely, a vector of integers is null mod 15 if and only if it is null mod 3 and mod 5. To see this, suppose $A$ has $m$ rows and $n$ columns, and suppose row $i$ of your matrix $A$ is $(a_{i,1}, \dots, a_{i,n})$. I will multiply vectors on the left.

Let $(v_1, \dots, v_n)$ be a vector of integers that is null for $A \mod{15}$, meaning we have equations $$ a_{i,1} v_1 + \cdots + a_{i, n} v_n \equiv 0 \pmod{15} $$ for $1 \le i \le m$. This means the integer $a_{i,1}v_1 + \cdots + a_{i,n}v_n$ is a multiple of $15$ for $1 \le i \le m$, and so in particular is also a multiple of $3$ and $5$. Thus, $(v_1, \dots, v_n)$ is a null vector mod 3 and 5, too. If we start at the end of this argument, we see that if $(v_1, \dots, v_n)$ is null mod $3$ and $5$, then $a_{i,1}v_1 + \cdots + a_{i,n}v_n$ is divisible by $3$ and $5$, so is also divisible by $15$.

Just another comment: the null space for $A \mod{3}$ might be larger in dimension than that of $A \pmod{5}$, or the other way around. For example, if $A$ is a matrix of all 3's, then it has rank $1$ mod $5$ but rank $0$ mod $3$. The argument above shows that the rank of $A$ mod $15$ is the max of the ranks mod $3$ and mod $5$.