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

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

$$a_1{x}_1+a_2{x}_2+\cdots +a_m{x}_m\equiv b(\mathrm{mod}n)$$

למשוואה זו קיים פתרון אם ורק אם $d\mid b$, כאשר $d=\gcd \{a_1,\dots ,a_m,n\}$.

משתנה יחיד

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

הוכחה

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

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

$\begin{array}{rl}{x}_0+t_1\frac{n}{d}& \equiv x_0+t_2\frac{n}{d}(\mathrm{mod}n),:0\le t_1<t_2\le d-1\\ t_1\frac{n}{d}& \equiv t_2\frac{n}{d}(\mathrm{mod}n),:\gcd \{\frac{n}{d},n\}=\frac{n}{d}\\ t_1& \equiv t_2(\mathrm{mod}d)\end{array}$

כלומר $d\mid (t_2-t_1)$. אבל $1<t_2-t_1<d$, בסתירה.

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

$\begin{array}{rl}{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}(\mathrm{mod}d)\end{array}$

ראו גם

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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