रेखीय समांगताएँ (Linear Congruences)

परिचय

संख्या सिद्धांत (Number Theory) में रेखीय समांगता (Linear Congruence) मॉड्यूलर अंकगणित की एक प्रमुख अवधारणा है। यह उन समीकरणों का अध्ययन करता है जो इस प्रकार लिखे जाते हैं:

a x ≡ b (mod m)

यह समीकरण बताता है कि जब ax और b को m से विभाजित किया जाता है, तो दोनों का शेषफल समान होता है। रेखीय समांगताएँ क्रिप्टोग्राफी, कंप्यूटर विज्ञान, एल्गोरिद्म और डेटा साइंस में अत्यंत महत्वपूर्ण हैं, विशेष रूप से तब जब हमें किसी संख्या का मॉड्यूलर इनवर्स (Modular Inverse) या सुरक्षित एन्क्रिप्शन कुंजी निकालनी होती है।

रेखीय समांगता का सामान्य रूप

रेखीय समांगता का सामान्य रूप होता है:

a x ≡ b (mod m)

जहाँ:

• a, b, और m पूर्णांक (Integers) हैं
• m > 0 (मॉड्यूलस)
• x वह अज्ञात चर (Unknown Variable) है जिसे खोजना होता है

समाधान की शर्त (Condition for Solution)

समीकरण a x ≡ b (mod m) का समाधान तभी संभव होता है जब:

GCD(a, m) | b

अर्थात a और m का महत्तम समापवर्तक (GCD) b को विभाजित करता हो। यदि यह शर्त पूरी नहीं होती, तो समीकरण का कोई समाधान नहीं होगा।

समाधान की संख्या (Number of Solutions)

यदि GCD(a, m) = d और d | b, तो समाधान की संख्या d होगी। सभी समाधान इस प्रकार लिखे जा सकते हैं:

x ≡ x₀ + (m/d)k (mod m)

जहाँ x₀ एक मूल समाधान (Particular Solution) है और k = 0, 1, 2, …, (d – 1)

उदाहरण 1

समीकरण: 3x ≡ 6 (mod 9)

यहाँ, a = 3, b = 6, m = 9 GCD(3, 9) = 3, और 3 | 6 ⇒ समाधान संभव।

समीकरण को सरल करें:

(3/3)x ≡ (6/3) (mod 9/3) ⇒ x ≡ 2 (mod 3)

अतः x = 2, 5, 8 समाधान होंगे।

उदाहरण 2

समीकरण: 14x ≡ 30 (mod 100)

GCD(14, 100) = 2 और 2 | 30 ⇒ समाधान संभव। समीकरण को 2 से विभाजित करें:

7x ≡ 15 (mod 50)

अब GCD(7, 50) = 1 ⇒ एकल समाधान मौजूद। Modular Inverse of 7 (mod 50) = 43 (क्योंकि 7×43 ≡ 1 mod 50)

अतः x ≡ 15 × 43 (mod 50) = 645 mod 50 = 45 → x ≡ 45 (mod 50)

Modular Inverse की अवधारणा

यदि a और m सहाभाज्य (Coprime) हैं (अर्थात GCD(a, m) = 1), तो a का Modular Inverse एक संख्या a⁻¹ होती है जिसके लिए:

a × a⁻¹ ≡ 1 (mod m)

इस Inverse को खोजने के लिए Extended Euclidean Algorithm का उपयोग किया जाता है।

उदाहरण:

Find the inverse of 3 mod 7:

3 × x ≡ 1 (mod 7) → x = 5 क्योंकि 3×5 = 15 ≡ 1 mod 7

रेखीय समांगता को हल करने की विधियाँ

1. 1. Euclidean Method: GCD निकालने के लिए।
2. 2. Extended Euclidean Algorithm: Modular Inverse खोजने के लिए।
3. 3. Substitution Method: छोटे मॉड्यूलस के लिए ट्रायल द्वारा।
4. 4. Simplification Method: समीकरण को m और a के सामान्य GCD से विभाजित कर सरल बनाना।

रेखीय समांगता के अनुप्रयोग

• क्रिप्टोग्राफी में एन्क्रिप्शन और डीक्रिप्शन कुंजी का निर्माण।
• Modular Arithmetic में संख्यात्मक गणनाएँ।
• डेटा साइंस में साइकलिक पैटर्न विश्लेषण।
• कंप्यूटर नेटवर्क में Key Scheduling और Hash Generation।

वास्तविक जीवन उदाहरण

मान लीजिए किसी पासवर्ड सिस्टम में प्रत्येक इनपुट को इस समीकरण से सत्यापित किया जाता है:

7x ≡ 3 (mod 26)

यह प्रणाली अक्षरों (A–Z) के आधार पर सुरक्षित है, और केवल वही x स्वीकार्य हैं जो इस समीकरण को संतुष्ट करें। इस प्रकार, यह समांग समीकरण सुरक्षित एन्क्रिप्शन में प्रयोग किया जा सकता है।

निष्कर्ष

रेखीय समांगताएँ संख्या सिद्धांत का व्यावहारिक और शक्तिशाली उपकरण हैं। इनका उपयोग मॉड्यूलर इनवर्स, डेटा एन्क्रिप्शन, साइकलिक पैटर्न और एल्गोरिद्म डिज़ाइन में होता है। डेटा साइंस और क्रिप्टोग्राफी में यह अवधारणा सुरक्षित और कुशल गणना प्रणालियों की नींव प्रदान करती है।