1911 Encyclopædia Britannica/Number/Linear Congruences

30. Linear Congruences.—The congruence $a'x=b'{\pmod {m'}}$ has no solution unless $\operatorname {dv} (a',m')$ is a factor of $b'$. If this condition is satisfied, we may replace the given congruence by the equivalent one $ax\equiv b{\pmod {m}}$, where $a$ is prime to $b$ as well as to $m$. By residuation (§§ 24, 25) we can find integers $h,k$ such that $ah-mk=1$, and thence obtain $x\equiv bh{\pmod {m}}$ as the complete solution of the given congruence. To the modulus $m'$ there are $m'/m$ incongruent solutions. For example, $12x\equiv 30{\pmod {21}}$ reduces to $2x\equiv 5{\pmod {7}}$ whence $x\equiv 6{\pmod {7}}\equiv 6,13,20{\pmod {21}}$. There is a theory of simultaneous linear congruences in any number of variables, first developed with precision by Smith. In any particular case, it is best to replace as many as possible of the given congruences by an equivalent set obtained by successively eliminating the variables $x,y,z,\dots$ in order. An important problem is to find a number which has given residues with respect to a given set of moduli. When possible, the solution is of the form $x\equiv a{\pmod {m}}$, where $m$ is the least common multiple of the moduli. Supposing that $p$ is a prime, and that we have a corresponding table of indices, the solution of $ax\equiv b{\pmod {p}}$ can be found by observing that $\operatorname {ind} \ x=\operatorname {ind} \ b-\operatorname {ind} \ a{\pmod {\overline {p-1}}}$.