[proofplan] Let $d=\gcd(a,n)$. Necessity follows by rewriting the congruence as an equality $ax-b=nt$ and observing that every common divisor of $a$ and $n$ divides $b$. For sufficiency, Bezout's identity produces an explicit solution after multiplying a Bezout relation for $a$ and $n$ by $b/d$. Finally, dividing the congruence by $d$ reduces the problem to a congruence modulo $n/d$ with a coefficient coprime to the modulus, which has one solution class modulo $n/d$; lifting that class back modulo $n$ gives exactly $d$ solution classes. [/proofplan] [step:Derive the divisibility condition from an existing solution] Set \begin{align*} d := \gcd(a,n). \end{align*} Since $n \in \mathbb{N}$, Androma's convention gives $n>0$, so $d$ is a positive integer. Suppose $x \in \mathbb{Z}$ satisfies \begin{align*} ax \equiv b \pmod{n}. \end{align*} By the definition of congruence modulo $n$, there exists $t \in \mathbb{Z}$ such that \begin{align*} ax-b = nt. \end{align*} Equivalently, \begin{align*} b = ax-nt. \end{align*} Because $d \mid a$ and $d \mid n$, there exist $\alpha,\nu \in \mathbb{Z}$ such that $a=d\alpha$ and $n=d\nu$. Hence \begin{align*} b = d\alpha x-d\nu t = d(\alpha x-\nu t). \end{align*} Since $\alpha x-\nu t \in \mathbb{Z}$, this proves \begin{align*} d \mid b. \end{align*} [guided] We begin from the meaning of the congruence. Let \begin{align*} d := \gcd(a,n). \end{align*} Since $n$ is a positive integer, $d$ is positive. Assume that an integer solution exists, and choose one such solution $x \in \mathbb{Z}$. The statement \begin{align*} ax \equiv b \pmod{n} \end{align*} means precisely that $n$ divides $ax-b$. Therefore there is an integer $t \in \mathbb{Z}$ with \begin{align*} ax-b = nt. \end{align*} Solving this equality for $b$ gives \begin{align*} b = ax-nt. \end{align*} Now we use the definition of $d$ as a common divisor of $a$ and $n$. Since $d \mid a$ and $d \mid n$, there are integers $\alpha,\nu \in \mathbb{Z}$ such that \begin{align*} a = d\alpha \end{align*} and \begin{align*} n = d\nu. \end{align*} Substituting these expressions into the equality for $b$, we obtain \begin{align*} b = d\alpha x-d\nu t. \end{align*} Factoring out $d$ gives \begin{align*} b = d(\alpha x-\nu t). \end{align*} The number $\alpha x-\nu t$ is an integer, so this is exactly the assertion that $d \mid b$. Thus every solution forces the divisibility condition $\gcd(a,n)\mid b$. [/guided] [/step] [step:Construct a solution from Bezout coefficients] Conversely, assume \begin{align*} d \mid b. \end{align*} Choose $c \in \mathbb{Z}$ such that \begin{align*} b = dc. \end{align*} By Bezout's identity applied to $a$ and $n$, there exist $u,v \in \mathbb{Z}$ such that \begin{align*} au+nv = d. \end{align*} Define $x_0 \in \mathbb{Z}$ by \begin{align*} x_0 := uc. \end{align*} Multiplying the Bezout relation by $c$ gives \begin{align*} aux_0/u + nvc = dc \end{align*} when $u \neq 0$, but to avoid division by $u$ we compute directly from $x_0=uc$: \begin{align*} ax_0+nvc = dc. \end{align*} Since $dc=b$, this becomes \begin{align*} ax_0-b = -nvc. \end{align*} Thus $n \mid ax_0-b$, and therefore \begin{align*} ax_0 \equiv b \pmod{n}. \end{align*} So the congruence has an integer solution. [/step] [step:Reduce the solution set to a coprime congruence modulo $n/d$] Assume now that $d \mid b$, and keep $c \in \mathbb{Z}$ with $b=dc$. Define integers $a_0,b_0,n_0 \in \mathbb{Z}$ by \begin{align*} a_0 := \frac{a}{d} \end{align*} \begin{align*} b_0 := \frac{b}{d} \end{align*} \begin{align*} n_0 := \frac{n}{d}. \end{align*} Then $n_0 \in \mathbb{N}$, $b_0=c$, and \begin{align*} \gcd(a_0,n_0)=1. \end{align*} For any $x \in \mathbb{Z}$, \begin{align*} ax \equiv b \pmod{n} \end{align*} holds if and only if \begin{align*} n \mid ax-b. \end{align*} Using $a=da_0$, $b=db_0$, and $n=dn_0$, this is equivalent to \begin{align*} dn_0 \mid d(a_0x-b_0). \end{align*} Since $d>0$, this is equivalent to \begin{align*} n_0 \mid a_0x-b_0. \end{align*} Therefore the original congruence is equivalent to \begin{align*} a_0x \equiv b_0 \pmod{n_0}. \end{align*} [/step] [step:Find the unique solution class modulo $n/d$] Since $\gcd(a_0,n_0)=1$, Bezout's identity applied to $a_0$ and $n_0$ gives $r,s \in \mathbb{Z}$ such that \begin{align*} a_0r+n_0s=1. \end{align*} Let $x_* \in \mathbb{Z}$ be defined by \begin{align*} x_* := rb_0. \end{align*} Multiplying the Bezout relation by $b_0$ gives \begin{align*} a_0x_*+n_0sb_0=b_0. \end{align*} Hence \begin{align*} a_0x_* \equiv b_0 \pmod{n_0}. \end{align*} Thus $x_*$ is a solution of the reduced congruence. If $x \in \mathbb{Z}$ is any solution of the reduced congruence, then \begin{align*} a_0x \equiv b_0 \pmod{n_0} \end{align*} and \begin{align*} a_0x_* \equiv b_0 \pmod{n_0}. \end{align*} Subtracting the two congruences gives \begin{align*} a_0(x-x_*) \equiv 0 \pmod{n_0}. \end{align*} Multiplying by $r$ and using $ra_0 \equiv 1 \pmod{n_0}$ gives \begin{align*} x-x_* \equiv 0 \pmod{n_0}. \end{align*} Therefore the reduced congruence has exactly one residue class of solutions modulo $n_0$, namely \begin{align*} x \equiv x_* \pmod{n_0}. \end{align*} [/step] [step:Lift the single class modulo $n/d$ to exactly $d$ classes modulo $n$] The solutions of the original congruence are exactly the integers $x \in \mathbb{Z}$ satisfying \begin{align*} x \equiv x_* \pmod{n_0}. \end{align*} Since $n=dn_0$, every such integer can be written as \begin{align*} x = x_*+n_0q \end{align*} for some $q \in \mathbb{Z}$. By the [division algorithm](/theorems/725) applied to $q$ with divisor $d$, there exist unique integers $m,\ell \in \mathbb{Z}$ such that \begin{align*} q=md+\ell \end{align*} and \begin{align*} 0 \le \ell < d. \end{align*} Thus \begin{align*} x=x_*+\ell n_0+mn. \end{align*} Therefore every solution lies in one of the $d$ residue classes modulo $n$ \begin{align*} x \equiv x_*+\ell n_0 \pmod{n} \end{align*} with $\ell \in \{0,1,\ldots,d-1\}$. It remains to check that these $d$ residue classes are distinct modulo $n$. Suppose $\ell_1,\ell_2 \in \{0,1,\ldots,d-1\}$ and \begin{align*} x_*+\ell_1 n_0 \equiv x_*+\ell_2 n_0 \pmod{n}. \end{align*} Then \begin{align*} n \mid (\ell_1-\ell_2)n_0. \end{align*} Since $n=dn_0$ and $n_0>0$, this implies \begin{align*} d \mid \ell_1-\ell_2. \end{align*} But $-(d-1)\le \ell_1-\ell_2 \le d-1$, so the only multiple of $d$ in this range is $0$. Hence $\ell_1=\ell_2$. The $d$ residue classes are distinct, and the solution set is exactly their union. This proves the claimed count of solution classes modulo $n$. [/step]