בתורת המספרים, קונגרואנציה ליניארית היא משוואה מודולרית מן הצורה
![{\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)
למשוואה זו קיים פתרון אם ורק אם
, כאשר
.
לקונגרואנציה קיים פתרון אם ורק אם , כאשר . במקרה זה זהו גם מספר הפתרונות השונים מודולו .
קונגרואנציה זו שקולה למשוואה דיופנטית מהצורה , אשר לה קיים פתרון אם ורק אם .
אם פתרון למשוואה זו, אזי כל פתרונות המשוואה הם מהצורה כאשר .
נוכיח כי עבור הפתרונות שונים מודולו :
נניח בשלילה כי שנים מהם שקולים זה לזה. נקבל כי
-
כלומר . אבל , בסתירה.
נוכיח עתה כי לכל שאר פתרונות המשוואה שקולים לאיברי קבוצה מצומצמת זו:
לפי אלגוריתם החילוק קיימים מספרים שלמים עבורם מתקיים כאשר . נקבל כי
-