Is there a row vector $x$ with integer entries such that no entry of $xM$ is $0 \text{ (mod }p\text{)}$? Let $p$ be a prime and let $M$ be an $n \times m$ matrix with integer entries such that $M\vec{v} \not\equiv \vec{0} \text{ (mod }p\text{)}$ for any column vector $\vec{v} \neq \vec{0}$ whose entries are $0$ or $1$.
Is there a row vector $\vec{x}$ with integer entries such that no entry of $\vec{x}M$ is $0 \text{ (mod }p\text{)}$?
 A: This is a proof of @LucGuyot 's statement:
For $p=2$, the assumption is linear independence of $m$ columns. Thus, $M$ has column rank $m$. Also, it has row rank $m$. In particular $n\geq m$, otherwise $\mathrm{rank}M=m$ is impossible. For any nonzero $w\in\mathbb{F}_2^m$, there is $x\in\mathbb{F}_2^n$ such that $x M = w$. 
For $p>m$, consider the vectors $v_1=Me_1$, $\ldots$, $v_m=Me_m$, where $e_i$ is a column vector which has $1$ on $i$-th entry and $0$ otherwise. 
By assumption, these vectors $v_1, \ldots, v_m$ are nonzero. Thus, their orthogonal complement $(\mathbb{F}_p v_i)^{\perp}$ is $n-1$-dimensional over $\mathbb{F}_p$. But, we have
$$
|\cup_{i=1}^m (\mathbb{F}_p v_i)^{\perp}|\leq m p^{n-1}.
$$
If we choose $x\in \mathbb{F}_p^n - \cup_{i=1}^m (\mathbb{F}_p v_i)^{\perp}$, then for each $1\leq i\leq m$, 
$$
xMe_i \neq 0.
$$
Choosing $x$ is possible in case $p>m$ because 
$$
p^n - mp^{n-1} = p^{n-1}(p-m) >0.
$$
A: It can be reduced to the case that $m\ge p+1$.
I think it is more natural to think about the filed $F$ with $p$ elements instead of the integers. Let $H_i$ be the orthogonal complement of the comlumn $i$ relativelly to the dot product. As each column must be different from zero, then each $H_i$ is an hyperplane of $F^n$. If $xM$ has a zero entry for all $x\in F^n$, then $F^n=H_1\cup\cdots\cup H_m$ and, therefore, $m\ge p+1$ (Indeed, pick an affine line $L$ parallel to $H_m$, we have for each $i$, $|H_i\cap L|\le 1$ and $|H_1\cap L|+\cdots|H_{m-1}\cap L|\ge |L|=p$).
A: It seems that my previous answer was completely wrong, and that the fact is true for all nonzero integer (not necessarily prime) $p$.
Let $M=[m_{ij}]_{i\leq n,\;j\leq m}$. If there is no $x$ satisfying the requirements (we regard all entries as integers, not residues!), then one of the sums of the form $\sum_{i\leq n} m_{ij}x_i$, $j\leq m$, is divisible by $p$ for every integer vector $x$. Equivalently,
$$ 
  \prod_{j\leq m}\left(1-\exp\left(\frac{2\pi i}p\sum_{i\leq n} m_{ij}x_i\right)\right)=0
$$
for every integral vector $x$.
After expanding all the brackets, we get the equality of the form
$$
  \sum_k c_k\xi_{1k}^{x_1}\dots \xi_{nk}^{x_n}=0,
$$
where $c_i$ are some (integer) numbers, and $\xi_{ik}$ are some nonzero complex numbers; after collecting terms, we may assume that all the $n$-tuples $(\xi_{1k},\dots,\xi_{nk})$ are distinct. Due to the usual Vandermonde argument, this may happen only if $c_k=0$ for all $k$. This means, in particulat, that the term $1^m$ cancels with some other term, which has the form
$$
  (-1)^t\prod_{j\in T}\exp\left(\frac{2\pi i}p\sum_{i\leq n} m_{ij}x_i\right)
  =(-1)^t\prod_{i\leq n}\left(\exp\left(\frac{2\pi i}p\sum_{j\in T}m_{ij}\right)\right)^{x_i}.
$$
for some $\varnothing\neq T\subseteq \{1,2,\dots,m\}$ with $t=|T|$. This yields that $\sum_{j\in T}m_{ij}$ is divisible by $p$ for all $i\leq n$, so the characteristic column of $T$ (taken as $v$) violates the condition imposed on $M$. 
Moreover, one may notice that there is such $T$ with odd cardinality; so we have proved that $v$ may be chosen with odd number of ones in it. 
ADDENDUM. The `usual Vandermonde argument' I meant consists in the following. Assume that $(\xi_{1,k},\dots,\xi_{n,k})$, $k=1,\dots,K$, are distinct tuples of complex numbers. Then the arrangements $(\xi_{1,k}^{x_1}\cdots\xi_{n,k}^{x_n})_{x_i\in\mathbb Z}$ are linearly independent. The proof goes by the induction on $n$; the base case $n=1$ is classical Vandermonde. For the step of induction, assume the linear dependence, collect the terms with identical $\xi_{1,k}$ and apply first the hypothesis (to prove that one of the coefficients of $\xi_{1,k}^{x_i}$ does not vanish for some choice of $x_2,\dots,x_n$) and then the base to finish the step.
