בתורת המספרים, קונגרואנציה ליניארית היא משוואה מודולרית מן הצורה
![{\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{m}x_{m}\equiv b\!\!\!{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e41890a310f7379de957f149cf9d9d092730b98a)
למשוואה זו קיים פתרון אם ורק אם
, כאשר
.
משתנה יחיד
לקונגרואנציה
קיים פתרון אם ורק אם
, כאשר
. במקרה זה זהו גם מספר הפתרונות השונים מודולו
.
קונגרואנציה זו שקולה למשוואה דיופנטית מהצורה
, אשר לה קיים פתרון אם ורק אם
.
אם
פתרון למשוואה זו, אזי כל פתרונות המשוואה הם מהצורה
כאשר
.
נוכיח כי עבור
הפתרונות
שונים מודולו
:
נניח בשלילה כי שנים מהם שקולים זה לזה. נקבל כי
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74b1221e73d74bbb1b92c1130738dc8a7a192d16)
כלומר
. אבל
, בסתירה.
נוכיח עתה כי לכל
שאר פתרונות המשוואה שקולים לאיברי קבוצה מצומצמת זו:
לפי אלגוריתם החילוק קיימים מספרים שלמים
עבורם מתקיים
כאשר
. נקבל כי
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2fb3aa61ea971de31cb1238ae204edee1989a57)
ראו גם
קישורים חיצוניים
38179360קונגרואנציה ליניארית