If $AX=B$ has an integer solution and $A$ and $B$ are matrices with integer entries, show that the system has a solution in $\mathbb{F}_p\ \forall p$.

My attempt: Suppose we have the following map $$\phi: \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$$

Let $a,b \in \mathbb{Z}$

$\phi(ab):=ab \mod n$

$\phi(a):=x \equiv a \mod n$

$\phi(b):= y \equiv b \mod n$

By definition of modular congruence,

$\phi(a)\phi(b)=xy\equiv ab \mod n=\phi(ab)$

Thus, $\phi$ is a homomorphism and since $\mathbb{Z}/n\mathbb{Z}\cong\mathbb{F_p}$ if $AX=B$ has an integer solution then it also has a solution in $\mathbb{F_p}$.

Point: I feel like there is still more to show to this proof.


1 Answer 1


Yes, you just need to use the fact that the map $\phi$ from $\mathbb{Z}$ into $\mathbb{Z}/p\mathbb{Z}$ defined by $x \mapsto x \pmod p$ is a homomorphism. So suppose $a_{11} x_1 + a_{12} x_2 + \cdots +a_{1n} x_n = b_1$. We can apply $\phi$ to both sides of this equation, and we have $\phi(LHS)=\phi(RHS)$. Now use the fact that $\phi$ preserves sums and products, and we get a solution over $\mathbb{Z}/p\mathbb{Z}$ also.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .