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

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

למשוואה זו קיים פתרון אם ורק אם , כאשר .

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

הוכחה
קונגרואנציה זו שקולה למשוואה דיופנטית מהצורה , אשר לה קיים פתרון אם ורק אם .
אם  פתרון למשוואה זו, אזי כל פתרונות המשוואה הם מהצורה  כאשר .

נוכיח כי עבור  הפתרונות  שונים מודולו :
נניח בשלילה כי שנים מהם שקולים זה לזה. נקבל כי

כלומר . אבל , בסתירה.

נוכיח עתה כי לכל  שאר פתרונות המשוואה שקולים לאיברי קבוצה מצומצמת זו:
לפי אלגוריתם החילוק קיימים מספרים שלמים  עבורם מתקיים  כאשר . נקבל כי

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

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


קטגוריה:תורת המספרים
קטגוריה:משוואות דיופנטיות