I know that if $\gcd(a,m)=1$ then the congruence $$a x \equiv 1 (\operatorname{mod} m)$$ has exactly one solution for $x \in \{0,1,\dotsc,m-1\}$.
From some particular numerical examples, I guess that the congruence $$a_1 x_1 + a_2 x_2 + \dotsb + a_t x_t \equiv 1 (\operatorname{mod} m)$$ has $m^{t-1}$ solutions for $(x_1, \dotsc, x_t) \in \{0,1,\dotsc,m-1\}^t$, provided $\gcd(a_1, \dotsc, a_t, m)=1$.
Is that true? And if yes, how to prove that?
Best Answer
Let $m=p_1^{\alpha_1}\dots p_n^{\alpha_n}$. The equation $$a_1x_1+\dots+a_tx_t\equiv 1\mod m$$ is equivalent to $$a_1x_1+\dots+a_tx_t\equiv 1\mod p_i^{\alpha_i}\forall i$$
Let's count the solutions mod $p_i^{\alpha_i}$ for a fixed $i$. Since $\gcd(a_1,\dots,a_t,m)=1$ we have that there is some $a_s$ ($s$ depending on $i$) such that $p_i$ doesn't divide $a_s$. In particular, $a_s$ is invertible mod $p_i^{\alpha_i}$. So, if you choose $x_j$'s with $j\neq s$ then $x_s$ will be determined. We can choose $x_j$'s, $j\neq s$ in $(p_i^{\alpha_i})^{t-1}$ ways mod $p_i^{\alpha_i}$. So, the number of solutions mod $p_i^{\alpha_i}$ is $(p_i^{\alpha_i})^{t-1}$.
By Chinese remainder theorem, a collection of solutions $(x_{i,1},\dots, x_{i,t})\mod p_i^{\alpha_i}$, $i=1,\dots,n$ is in bijection with a solution mod $n$. Hence, the number of solutions mod $n$ is $\prod_i(p_i^{\alpha_i})^{t-1}=m^{t-1}$.