קונגרואנציה ליניארית

בתורת המספרים, קונגרואנציה ליניארית היא משוואה מודולרית מן הצורה

a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{m}x_{m}\equiv b\!\!\!{\pmod {n}}

למשוואה זו קיים פתרון אם ורק אם $d\mid b$ , כאשר $d=\gcd\{a_{1},\ldots ,a_{m},n\}$ .

משתנה יחיד

לקונגרואנציה $ax\equiv b\!\!\!{\pmod {n}}$ קיים פתרון אם ורק אם $d\mid b$ , כאשר $d=\gcd\{a,n\}$ . במקרה זה זהו גם מספר הפתרונות השונים מודולו $n$ .

הוכחה

קונגרואנציה זו שקולה למשוואה דיופנטית מהצורה $ax-ny=b$ , אשר לה קיים פתרון אם ורק אם $d\mid b$ .
אם $(x_{0},y_{0})$ פתרון למשוואה זו, אזי כל פתרונות המשוואה הם מהצורה $(x,y)=\left(x_{0}+t{\frac {n}{d}},y_{0}+t{\frac {a}{d}}\right)$ כאשר $t\in \mathbb {Z}$ .

נוכיח כי עבור $0\leq t\leq d-1$ הפתרונות $x=x_{0}+t{\frac {n}{d}}$ שונים מודולו $n$ :
נניח בשלילה כי שנים מהם שקולים זה לזה. נקבל כי

{\begin{aligned}x_{0}+t_{1}{\frac {n}{d}}&\equiv x_{0}+t_{2}{\frac {n}{d}}\!\!\!{\pmod {n}},\qquad :0\leq t_{1}<t_{2}\leq d-1\\t_{1}{\frac {n}{d}}&\equiv t_{2}{\frac {n}{d}}\!\!\!{\pmod {n}},\qquad \qquad :\gcd \!\left\{{\frac {n}{d}},n\right\}={\frac {n}{d}}\\t_{1}&\equiv t_{2}\!\!\!{\pmod {d}}\end{aligned}}

כלומר $d\mid (t_{2}-t_{1})$ . אבל $1<t_{2}-t_{1}<d$ , בסתירה.

נוכיח עתה כי לכל $t\in \mathbb {Z}$ שאר פתרונות המשוואה שקולים לאיברי קבוצה מצומצמת זו:
לפי אלגוריתם החילוק קיימים מספרים שלמים $q,r$ עבורם מתקיים $t=qd+r$ כאשר $0\leq r\leq d-1$ . נקבל כי