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

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

$$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$. נקבל כי

${\begin{aligned}x_{0}+t{\frac {n}{d}}&=x_{0}+(qd+r){\frac {n}{d}}\\&=x_{0}+qn+r{\frac {n}{d}}\\&\equiv x_{0}+r{\frac {n}{d}}\!\!\!{\pmod {d}}\end{aligned}}$

ראו גם

• משוואה דיופנטית
• חשבון מודולרי
• משפט השאריות הסיני

קישורים חיצוניים

• קונגרואנציה ליניארית, באתר MathWorld (באנגלית)