# Number of solutions of linear congruence

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?

• It's true, the proof follows from CRT and counting the solutions mod a prime power. Commented Jun 10, 2019 at 23:15

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}$$.