Questions regarding solvability $Ax=w$ in $\mathbb{Z}/(p-1)\mathbb{Z}$ Dear mathstack exchange,
Currently I`m working on my bachelor thesis. I want to answer the following:


*

*$Ax=w$ is solveable in $\mathbb{Z}/(p-1)\mathbb{Z}$ if and only if
$\mbox{det}(A) \bmod (p-1) \in (\mathbb{Z}/(p-1)\mathbb{Z})^{\times}$


(already answered thanks to aRaRa)


*How to deal with zero divisors in $\mathbb{Z}/(p-1)\mathbb{Z}$ for $Ax=w$


I hope you can help me!  
 A: But "if and only if" is wrong.
Let $p=13$, so $q:=p-1=12$.
Look at the following linear equation in $\mathbb{Z}/q\mathbb{Z}$:
$$\pmatrix{5 & 5\\11 & 1}\, x=\pmatrix{1\\11}\,, $$
it has the solution
$$w=\pmatrix{3\\2} \, ,$$
but
$$\det \pmatrix{5 & 5\\11 & 1} = 10\not\in (\mathbb{Z}/q\mathbb{Z})^\times=\{1,5,7,11\} \, .$$
The "if" part (see here):
\begin{align}
A\, x & = w\\
\mathrm{adj}(A) A \, x &= \mathrm{adj}(A) \,w \\
\det(A)\cdot E\, x &= \mathrm{adj}(A) \, w\\
x &= \det(A)^{-1}\mathrm{adj}(A) \, w\, .
\end{align}
$E$ is simply the identity matrix here. I could divide the equation by $\det(A)$ because we stipulated that $\det(A)$ is in the unit group of the ring.
A: Regarding how to deal with zero divisors:
Do all the steps as in my first answer till you get to this:
$$\det(A)\cdot E\, x = \mathrm{adj}(A) \, w$$
Now since you can't simply divide by $\det(A)$, what can we do?
This equation is just a system of many simple equations with one variable ($N=\dim(A)$):
\begin{align} 
\mathrm{1.} \quad \det(A) \, x_1 & \equiv \bigl(\mathrm{adj}(A)\, w\bigr)_1 \bmod{(p-1)} \\
\mathrm{2.} \quad \det(A) \, x_2 & \equiv \bigl(\mathrm{adj}(A)\, w\bigr)_2 \bmod{(p-1)} \\
&\vdots \\
\mathrm{N.} \quad \det(A) \, x_N & \equiv \bigl(\mathrm{adj}(A)\, w\bigr)_N \bmod{(p-1)} \\
\end{align}
How can we solve them?
You can use the following theorem:

The equation $$  a x \equiv b \bmod{n} \; \quad a, b \in \mathbb{Z}\, , n \in \mathbb{N}
$$ with $d:= \gcd(a,n)$ has no solution if $d \nmid b$. But if $d \mid b$, it is equivalent to $$
  x \equiv y \frac{b}{d} \bmod{\frac{n}{d}}
$$ with $y\in \mathbb{Z}$ chosen so, that $y a + z n = d$ for a $z \in \mathbb{Z}$.

You get $y$ (and $z$) by the extended Euclidean algorithm.
Just solve them one after another with this theorem and you're done!
Of course the equation doesn't need to have a solution, which happens if there is a $k \in \{1, \ldots, N\}$ for which the greatest common divisor of $\det(A)$ and $p-1$ doesn't divide $\bigl(\mathrm{adj}(A)\, w\bigr)_k$.
A: This is only about the additional case, when we don't know that $\det A$ is invertible modulo $p-1$. I am addressing the problem in aRaRa's second answer, where multiplying the system by $\mathrm{adj}\, A$ occasionally introduces unwanted solutions. Possibly many of them.
We can think of $A$ as having integer entries (for a little while - bear with me). I intend to use the so called Smith normal form. It says that there exists square matrices 
with integer entries $P$ and $Q$ such that
$$
A=PDQ,
$$
where


*

*$D$ is a diagonal matrix with entries $d_1,d_2,\ldots$ such that $d_i\mid d_{i+1}$ for all applicable $i$, and

*the matrices $P$ and $Q$ are unimodular, i.e. they have inverses with integer entries as well (in other words their determinants are $\pm1$).


The system $Ax=w$ is thus equivalent to the system $PDQx=w$. Because of unimodularity $P^{-1}$ and $Q^{-1}$ also make sense over the ring $\Bbb{Z}_n, n=p-1$. Therefore the original system is equivalent to the system of congruences
$$
DQx\equiv P^{-1}w\pmod n.\qquad(*)
$$
How can we all the solutions of the system of linear congruences $(*)$? We need to introduce a helper set of new variable $y$ defined by $y=Qx$. Because $Q$ is unimodular as well the correspondence $y=Qx$ is bijective (Sorry about playing Capt'n Bbvious here - $Q$ is invertible modulo $n$). So if we can find all the vectors $y$, we can find all the solution vectors $x$ as well.
But the remaining system 
$$
Dy=P^{-1}w
$$
has a diagonal matrix of coefficients! There we can find all the solutions of all the components $y$ with the method in aRaRa's 2nd answer. It is possible that there are none, but them's the breaks.

As an example consider the congruence from aRaRa's 1st answer
$$
\left(\begin{array}{rr}5&5\\-1&1\end{array}\right)
\left(\begin{array}{r}x_1\\x_2\end{array}\right)\equiv\left(\begin{array}{r}1\\11\end{array}\right)\pmod{12}.
$$
Here
$$
A=\left(\begin{array}{rr}5&5\\-1&1\end{array}\right)
=P\left(\begin{array}{rr}1&0\\0&10\end{array}\right)Q
$$
with the unimodular matrices
$$
P=\left(\begin{array}{rr}5&1\\1&0\end{array}\right),\qquad
Q=\left(\begin{array}{rr}-1&1\\1&0\end{array}\right).
$$
Let's write 
$$
\left(\begin{array}{r}y_1\\y_2\end{array}\right)=
Q\left(\begin{array}{r}x_1\\x_2\end{array}\right)=\left(\begin{array}{c}x_2-x_1\\x_1\end{array}\right).
$$
We have
$$
P^{-1}\left(\begin{array}{r}1\\11\end{array}\right)\equiv\left(\begin{array}{r}11\\6\end{array}\right)\pmod{12},
$$
so we want to solve the pair of congruences 
$$
\left\{\begin{array}{rcr}y_1&\equiv& 11\\10y_2&\equiv& 6\end{array}\right.$$
both modulo $12$. Clearly we must have $y_1\equiv 11\equiv-1$, but for $y_2$ we get two possibilities $y_2\equiv3$ and $y_2\equiv -3\equiv9$. Given that $x_1\equiv y_2$ and $x_2\equiv y_1+y_2$ this leads to the two solutions $(x_1,x_2)\equiv(3,2)$ and $(x_1,x_2)\equiv(9,8)$.
