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

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

a_{1} x_{1} + a_{2} x_{2} + \dots + a_{m} x_{m} \equiv b (\mod n)

למשוואה זו קיים פתרון אם ורק אם $d ∣ b$ , כאשר $d = gcd {a_{1}, \dots, a_{m}, n}$ .

משתנה יחיד

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

הוכחה

קונגרואנציה זו שקולה למשוואה דיופנטית מהצורה $a x - n y = b$ , אשר לה קיים פתרון אם ורק אם $d ∣ b$ .תבנית:ש אם $(x_{0}, y_{0})$ פתרון למשוואה זו, אזי כל פתרונות המשוואה הם מהצורה $(x, y) = (x_{0} + t \frac{n}{d}, y_{0} + t \frac{a}{d})$ כאשר $t \in ℤ$ .

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

\begin{matrix} x_{0} + t_{1} \frac{n}{d} & \equiv x_{0} + t_{2} \frac{n}{d} (\mod n), : 0 \leq t_{1} < t_{2} \leq d - 1 \\ t_{1} \frac{n}{d} & \equiv t_{2} \frac{n}{d} (\mod n), : gcd {\frac{n}{d}, n} = \frac{n}{d} \\ t_{1} & \equiv t_{2} (\mod d) \end{matrix}

כלומר $d ∣ (t_{2} - t_{1})$ . אבל $1 < t_{2} - t_{1} < d$ , בסתירה.

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

\begin{matrix} x_{0} + t \frac{n}{d} & = x_{0} + (q d + r) \frac{n}{d} \\ = x_{0} + q n + r \frac{n}{d} \\ \equiv x_{0} + r \frac{n}{d} (\mod d) \end{matrix}

ראו גם

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

תבנית:MathWorld

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

תוכן עניינים

משתנה יחיד

הוכחה

ראו גם

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

תפריט ניווט

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

משתנה יחיד

הוכחה

ראו גם

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

תפריט ניווט

חיפוש