Linear congruence

In number theory, linear congruence denotes a Diophantine equation in the form of congruence

${\displaystyle ax\equiv b\mod m}$.

Be

${\displaystyle \operatorname {ggT} (a,m)=d}$

This congruence has solutions if and only if is a factor of : ${\displaystyle d}$ ${\displaystyle b}$

${\displaystyle d|b}$.

If there is a special solution, then the solution set consists of different congruence classes. ${\displaystyle r}$ ${\displaystyle d}$

The solutions then have the representation ${\displaystyle x}$

${\displaystyle x=r+t\cdot {\frac {m}{d}},\quad t\in \mathbb {Z} }$.

proof

First, let the linear congruence be solvable and be a solution. Ways are and . The condition is equivalent to . Choose so that . Equivalent forming and insertion provide: ${\displaystyle ax\equiv b\mod m}$ ${\displaystyle r\in \mathbb {Z} }$ ${\displaystyle \operatorname {ggT} (a,m)=d}$ ${\displaystyle a':={\frac {a}{d}}\in \mathbb {Z} }$ ${\displaystyle m':={\frac {m}{d}}\in \mathbb {Z} }$ ${\displaystyle ar\equiv b\mod m}$ ${\displaystyle m|(ar-b)}$ ${\displaystyle z\in \mathbb {Z} }$ ${\displaystyle zm=ar-b}$

${\displaystyle b=ar-zm=da'r-zdm'=d(a'r-zm')}$.

Here is . So or . ${\displaystyle a'r-zm'\in \mathbb {Z} }$ ${\displaystyle d|b}$ ${\displaystyle \operatorname {ggT} (a,m)|b}$

Now apply . Now choose so that . The lemma Bézout provides the existence of so . Insertion into the previous equation yields: . This is equivalent to or . So because of what is equivalent to . Hence, a solution of the linear congruence is given by. ${\displaystyle \operatorname {ggT} (a,m)=d|b}$ ${\displaystyle z\in \mathbb {Z} }$ ${\displaystyle b=zd}$ ${\displaystyle s,t\in \mathbb {Z} }$ ${\displaystyle d=sa+tm}$ ${\displaystyle b=z(sa+tm)=zsa+ztm}$ ${\displaystyle ztm=b-zsa}$ ${\displaystyle -ztm=zsa-b}$ ${\displaystyle -zt\in \mathbb {Z} }$ ${\displaystyle m|(zsa-b)}$ ${\displaystyle zsa\equiv b\mod m}$ ${\displaystyle r:=zs}$ ${\displaystyle ax\equiv b\mod m}$

Finally, let us again assume a special solution of linear congruence. For each is . This modulo are therefore found different solutions. To convince yourself that these are all the solutions, one can realize that a linear Diophantine equation is given and in this context all solutions for and can be found. ${\displaystyle r\in \mathbb {Z} }$ ${\displaystyle t\in \mathbb {Z} }$ ${\displaystyle b\equiv ar\equiv ar+{\frac {a}{d}}\cdot tm=ar+at\cdot {\frac {m}{d}}=a(r+t\cdot {\frac {m}{d}})\mod m}$ ${\displaystyle m}$ ${\displaystyle d}$ ${\displaystyle ax\equiv b\mod m\Leftrightarrow m|ax-b\Leftrightarrow \exists z\in \mathbb {Z} :zm=ax-b\Leftrightarrow \exists z\in \mathbb {Z} :ax+(-z)m=b}$ ${\displaystyle x}$ ${\displaystyle z}$

example

Find all solutions of linear congruence

${\displaystyle 6x\equiv 3\mod 27}$.

a special solution can be found through trial and error and reads . ${\displaystyle r=14}$

Since , there are three different solutions modulo 27 and thus three equivalence classes, namely ${\displaystyle \operatorname {ggT} (6,27)=3}$

${\displaystyle \left[{14}\right]_{27},\left[{14-9}\right]_{27}=\left[5\right]_{27},\left[{14+9}\right]_{27}=\left[{23}\right]_{27}}$

Alternatively, you can also use the calculation rules for congruences to find a solution more quickly:

${\displaystyle 6x\equiv 3\mod 27\Leftrightarrow 2x\equiv 1\mod 9\Leftrightarrow _{\operatorname {ggT} (9,2)=1}x\equiv 5\mod 9}$

by first shortening the equation by 3 (this also changes the modulus, because the ) and then multiplying by the inverse of 2. The equivalence class of the solutions is then obtained ${\displaystyle \operatorname {ggT} (27,3)=3\neq 1}$

${\displaystyle \left[{5}\right]_{9}}$

literature

• Kristina Reiss , Gerald Schmieder: Basic knowledge of number theory . 3. Edition. Springer Spectrum, Berlin 2014, ISBN 978-3-642-39773-8 , 8. Linear and quadratic congruences.