Congruence MCQ Quiz in हिन्दी - Objective Question with Answer for Congruence - मुफ्त [PDF] डाउनलोड करें

व्याख्या:

संग्रह संबंध \(2x \equiv 1 \mod{7}\) को हल करने के लिए, हमें एक पूर्णांक x ज्ञात करने की आवश्यकता है

जिसका 2 से गुणा करने पर, 7 से भाग देने पर शेषफल 1 बचता है।

हमें एक पूर्णांक y ज्ञात करने की आवश्यकता है जिससे:

\(2y \equiv 1 \mod{7}\)

हम y के मान 1 से 6 तक जाँच सकते हैं:

y = 1 के लिए: 2 . 1 = 2 (1 के तुल्य नहीं है)

y = 2 के लिए: 2 . 2 = 4 (1 के तुल्य नहीं है)

y = 3 के लिए: 2 . 3 = 6 (1 के तुल्य नहीं है)

y = 4 के लिए: 2 . 4 = 8 \(\equiv 1 \mod{7}\)

इसलिए, y = 4, 2 का 7 मॉड्यूलो में गुणात्मक प्रतिलोम है।

अब हम मूल संग्रह \(2x \equiv 1 \mod{7}\) के दोनों पक्षों को

4 से गुणा कर सकते हैं,

\(4 \cdot (2x) \equiv 4 \cdot 1 \mod{7}\)

इसलिए विकल्प 1 सही है।

प्रयुक्त अवधारणा:

एक धनात्मक पूर्णांक n के लिए, ऑयलर का टॉसेन्ट फलन इस प्रकार परिभाषित है:

\( \phi(n) = \text{number of positive integers } k \leq n \text{ such that } \text{gcd}(n, k) = 1\)

यहाँ, gcd(n, k), n और k का महत्तम समापवर्तक है।

ऑयलर के टॉसेन्ट फलन के कुछ गुणों में शामिल हैं:

• ϕ(1) = 1, क्योंकि 1 के पास स्वयं से कम कोई धनात्मक पूर्णांक नहीं है।

व्याख्या:

दिया गया है: f(x) = x2 - 4x + 4

f(x) = 0

⇒ x2 - 4x + 4 = 0

⇒ (x - 2)2 = 0

⇒ x - 2 = 0

⇒ x = 2

इस प्रकार, दिए गए समीकरण f(x) = 0 का केवल एक हल x = 2 है।

इस प्रकार, n = 1.

इस प्रकार, ϕ(n) = ϕ(1) = 1

1 न तो अभाज्य है और न ही सम संख्या है।

इस प्रकार, विकल्प 1 और 2 गलत हैं।

1, 3 का गुणज भी नहीं है, इसलिए विकल्प 4 भी सही नहीं है।

इस प्रकार, सही विकल्प विकल्प 3 है।

स्पष्टीकरण -

हम 26 और 5 के बीच अंतर के संभावित गुणनखंडों पर विचार करके शुरुआत कर सकते हैं, जो 26 - 5 = 21 है।

21 के गुणनखंड 1, 3, 7 और 21 हैं।

अब, आइए जाँच करते है कि इनमें से कौन सा मान 26 ≡ 5 (mod x) को संतुष्ट करता है।

x = 1 के लिए, 26 और 5 सर्वांगसम नहीं हैं क्योंकि किसी भी पूर्णांक को 1 से विभाजित करने पर शेषफल सदैव वही संख्या प्राप्त होती है।

x = 3 के लिए, 26 ≡  5 (mod 3) है क्योंकि 3 से विभाजित करने पर 26 और 5 दोनों में समान शेषफल 2 प्राप्त होता हैं।

x = 7 के लिए, 26 ≡ 5 (mod 7) है क्योंकि 7 से विभाजित करने पर 26 और 5 दोनों में समान शेषफल 5 प्राप्त होता हैं।

x = 21 के लिए, 26 ≡ 5 (mod 21) है क्योंकि 21 से विभाजित करने पर 26 और 5 दोनों में समान शेषफल 5 प्राप्त होता हैं।

इसलिए, 26 ≡ 5 (mod x) को संतुष्ट करने वाले x के मानों का समुच्चय {3, 7, 21} है।

अतः, विकल्प (4) सही है।

अवधारणा:

रैखिक सर्वांगसमता: रूप ax ≡ b(मोड m) की सर्वांगसमता जहाँ x एक अज्ञात पूर्णांक है, एक चर में रैखिक सर्वांगसमता कहलाती है, जहाँ,

a, b और m पूर्णांक हैं जिनमें m अभाज्य संख्या होनी चाहिए।

विल्सन प्रमेय: इस प्रमेय के अनुसार, यदि p एक अभाज्य संख्या है, तो

(p - 1)! = -1 (मोड P)

दूसरे शब्दों में, जब (P-1)! को P से भाग दिया जाता है तो शेष p - 1 है

⇒ \(\rm Rem\ \left[\dfrac{(P - 1)!}{P}\right] = P \ - \ 1\)

जहाँ  n! = n(n - 1)(n - 2).......3.2.1

उसी प्रकार

(P - 2)! = 1(मोड P)

\(\rm (P\ - \ 3)!\ = \dfrac{P - 1}{2}(mod \ P)\)

गणना:

दिया गया है 

27! = x (मोड 29)  ---(1)

हम देख सकते हैं कि, P = 29 जो अभाज्य संख्या है। इसलिए, विल्सन प्रमेय का उपयोग किया जा सकता है।

हम जानते हैं कि

(P - 2)! = 1(मोड P)

इस गुण के साथ (1) की तुलना करने पर, हम प्राप्त करेंगे

x = 1

अतः विकल्प 1 सही विकल्प है।

संकल्पना:

चीनी शेष प्रमेय (CRT):

मान लीजिए a और b दो अपेक्षाकृत अभाज्य (सहअभाज्य) संख्याएँ हैं जैसे कि 0 r < a और 0 s < b। एक अद्वितीय संख्या N मौजूद है जैसे कि 0 N

\(r\ \equiv N \ mod(a)\)

\(s\ \equiv N \ mod(b)\)

अर्थात N के पास a से भाग देने पर r शेष रहता है और b से भाग देने पर s शेष रहता है।

गणना:

दी गई एक साथ सर्वांगसमताएं हैं

\(x\ \equiv 5 \ mod(25)\) ---- (1)

\(x\ \equiv 32 \ mod(23)\) ---- (2)

इसका अर्थ है कि हमें x को इस प्रकार ज्ञात करना है कि जब इसे 25 से विभाजित किया जाए तो शेषफल 5 प्राप्त होता है और 23 से भाग देने पर शेषफल 32 प्राप्त होता है।

⇒ x = 25a + 5

जहां, a = 0, 1, 2,....

⇒ x = 5, 30, 55, 80,.....

x = 23b + 32

⇒ x = 32, 55, 87,.... 

x दोनों समीकरणों को एक साथ संतुष्ट करेगा।

x = 55

∵ 25 & 23 का  LCM is 575 है।

अत: x का सामान्य  मान  55 + 575K होगा।

अवधारणा:

फेरमाट की छोटी प्रमेय: इसका आशय है कि यदि p एक अभाज्य संख्या है, तो किसी भी पूर्णांक a के लिए, संख्या a p - a, p का एक पूर्णांक गुणज है।

• यहाँ p एक अभाज्य संख्या है a^p ≡ a (मोड p).
• यदि 2^p ≡ 2 (mod p) अर्थात 2p - 2, p से भाज्य है। 

दिया गया है:

X = 3 (mod 9), X = 7 (mod 13)

अवधारणा:

चीनी शेषफल प्रमेय:

यदि m1, m2, .., mk युग्मानुसार अपेक्षाकृत अभाज्य पूर्णांक हैं, और यदि a1, a2, .., ak कोई पूर्णांक हैं, तो

समकालिक सर्वांगसमताएं

x ≡ a1 (mod m1),

x ≡ a2 (mod m2)

x ≡ ak (mod mk)

एक हल है, और हल अद्वितीय मोड्युलो M है, जहाँ 

M = m1m2⋅⋅⋅mk .

अब, x का हल दिया गया है

X = M1X1a1 + M2X2a2+......... + MkXkak 

जहाँ, 

\(M_i = \frac{M}{m_i}\), I = 1, 2, 3, ....K    

और

MiXi  ≡ 1 mod(mi)

गणना:

हमारे पास दिया गया है,

x = 3 (mod9),

x = 7 (mod13)

m1 = 9 और m2 = 13 जो अपेक्षाकृत सह अभाज्य है।

और, a1 = 3 और a2 = 7, जो पूर्णांक है। 

अत: चीनी शेषफल प्रमेय की स्थिति संतुष्ट होती है।

इसलिए, प्रमेय के अनुसार, मॉड्यूलो के लिए x का अद्वितीय हल होगा

M = 9 × 13 = 117

अब, संबंध का उपयोग करने पर,

 \(M_i = \frac{M}{m_i}\)     

हमें प्राप्त होगा

M1 = 13 और M2 = 9

X1 और X2 की गणना करने के लिए हम संबंध का उपयोग कर सकते हैं,

MiXi  ≡ 1 (mod mi)

⇒ 13X1  ≡ 1 (mod 9)

⇒  4X1  ≡ 1 (mod 13)

दोनों पक्षों को 7 से गुणा करने पर, हमें निम्न प्राप्त होगा

28X1  ≡ 7 (mod 9)

⇒ X1  ≡ 7 (mod 9)

⇒ X1 = 7

पुन:, उपरोक्त संबंध का उपयोग करने पर,

9X2  ≡ 1 mod(13)

⇒ 27X2  ≡ 3 mod(13)

⇒ X2  ≡ 3 mod(13)

⇒ X2  = 3

अत: x का अद्वितीय हल होगा

X = M1X1a1 + M2X2a2

⇒ X = 13 × 7 × 3 +  9 × 3 × 7 = 138

⇒ X ≡ 462 mod(117)

⇒ X ≡ 111 mod(117)

संकल्पना:

फर्मेट का प्रमेय:

• यदि p एक अभाज्य है और p, a को विभाजित नहीं करता है, तो a p - 1 ≡ 1(mod p)
• यदि a ≡  b (mod n) और c ≡  d (mod n) तो a + c ≡ b + d (mod n) जहां a, b, c, d कोई पूर्णांक हैं।

गणना:

यहाँ 7 एक अभाज्य है

और gcd(2, 7) = gcd(3, 7) = gcd(4, 7) = gcd(5, 7) = gcd(11, 7) = 1

अत: फर्मेट की प्रमेय का प्रयोग करते हुए,

निम्न पर विचार करें,

27 - 1 ≡ 1(mod 7)

⇒ 26 ≡ 1(mod 7)

⇒ ( 26)3 ≡ 1(mod 7)

⇒ 218 ≡ 1(mod 7)

2² से सर्वत्र गुणा करें, हमें मिलता है

⇒ 218 . 22  ≡ 22 (mod 7)

⇒ 220 ≡ 4(mod 7)       .....(1)

आगे निम्न पर विचार करें,

37 - 1 ≡ 1(mod 7)

⇒ 36 ≡ 1(mod 7)

⇒ ( 36)5 ≡ 1(mod 7)

⇒ 330 ≡ 1(mod 7)       ......(2)

आगे निम्न पर विचार करें,

47 - 1 ≡ 1(mod 7)

⇒46 ≡ 1(mod 7)

⇒ ( 46)6 ≡ 1(mod 7)

⇒ 436 ≡ 1(mod 7)

44 से सर्वत्र गुणा करें, हमें मिलता है

⇒ 436. 44​  ≡ 44 (mod 7)

⇒ 440 ≡ 256 (mod 7) 

⇒ 440 ≡ 4(mod 7)  ......(3)

आगे निम्न पर विचार करें,

57 - 1 ≡ 1(mod 7)

⇒56 ≡ 1(mod 7)

⇒ ( 56)8 ≡ 1(mod 7)

⇒ 548 ≡ 1(mod 7)

5² से सर्वत्र गुणा करें, हमें मिलता है

⇒ 548 . 52 ≡ 52  (mod 7)

⇒ 550 ≡ 25  (mod 7)

⇒ 550 ≡ 4  (mod 7)       ....(4)

अंत में निम्न पर विचार करें,

117 - 1 ≡ 1(mod 7)

⇒116 ≡ 1(mod 7)

सर्वत्र 11 से गुणा करने पर हमें प्राप्त होता है

⇒116 . 11 ≡ 11 (mod 7)

⇒ 117  ≡ 11(mod 7)

⇒ 117  ≡ 4(mod 7)       ......(5)

अब (1), (2), (3), (4) और (5) को जोड़ने पर हमें प्राप्त होता है,

220 + 330 + 440 + 550 + 117 ≡ (4 + 1 + 4 + 4 + 4 )(mod 7)  | (6) का उपयोग करके

⇒ 220 + 330 + 440 + 550 + 117 ≡ 17 (mod 7)

⇒ 220 + 330 + 440 + 550 + 117 ≡ 3 (mod 7)

इसलिए सही उत्तर विकल्प 4) है

अवधारणा :

किसी निश्चित पूर्णांक n > 1 के लिए और किसी भी स्वेच्छ पूर्णांक a, b, c और d के लिए।

यदि a b (मॉड n) और c ≡ d (मॉड n) तो

• a + c b + d (मॉड n) और
• ac ≡ bd (मॉड n)

प्रमाण:

सबसे पहले,

दिया गया है कि, a ≡ b(मॉड n) और c ≡ d (मॉड n)

⇒ n | (a - b) और n | (c - d)

⇒ a - b = hn और c - d = kn; कुछ पूर्णांकों h और k के लिए --- (1)

अब विचार करें, a - b + c - d = nh + nk

⇒ (a + c) - (b + d) = n(h + k)           ( ∵ h + k एक पूर्णांक है )

⇒ n | [ (a + c) - (b + d) ]

⇒ a + c ≡ b + d(मॉड n)

अगला,

(1) से हमारे पास है,

a = b + hn और c = d + kn

मान लीजिए, ac = (b + hn) × (d + kn)

⇒ ac = bd + bkn + hnd + hknn

⇒ ac - bd = n (bk + hd + hkn) 

⇒ n | ac - bd                                   ( ∵ (bk + hd + hkn) एक पूर्णांक है )

⇒ ac ≡ bd (मॉड n)

अत: सही उत्तर विकल्प 3 है)

दिया है:

X = 3 (मोड 5), X = 5 (मोड 7)

अवधारणा:

चीनी शेष प्रमेय:

यदि m1, m2, .., mk जोड़ीवार अपेक्षाकृत अभाज्य धनात्मक पूर्णांक हैं, और यदि a1, a2, .., ak कोई पूर्णांक हैं, तब

एक साथ सर्वांगसमताएँ

x ≡ a1 (मोड m1),

x ≡ a2 (मोड m2)

x ≡ ak (मोड mk)

एक हल है, और हल अद्वितीय सापेक्ष M है, जहाँ

M = m1m2⋅⋅⋅mk

अब, हल x द्वारा दिया गया है

X = M1X1a1 + M2X2a2+......... + MkXkak 

जहाँ,

\(M_i = \frac{M}{m_i}\), I = 1, 2, 3, ....K

और

MiXi  ≡ 1 मोड(mi)

सापेक्ष या मापांक या मोड: यह एक संख्या को दूसरी संख्या से विभाजित करने के बाद का शेष है।

गणना:

हमें दिया गया है,

m1 = 5 और m2 = 7 जो अपेक्षाकृत सह-अभाज्य हैं।

साथ ही, a1 = 3 और a2 = 5, जो पूर्णांक हैं।

इसलिए चीनी शेष प्रमेय की स्थिति संतुष्ट है।

इसलिए, प्रमेय के अनुसार, सापेक्ष के लिए x का अद्वितीय हल होगा

M = 5 × 7 = 35

अब, संबंध का प्रयोग करते हुए,

  \(M_i = \frac{M}{m_i}\)     

हमें मिलेगा

M1 = 7 और M2 = 5

X1 और X2  की गणना करने के लिए हम संबंध का प्रयोग कर सकते हैं,

MiXi  ≡ 1 मोड(mi)

⇒ 7X1  ≡ 1 मोड(5)

⇒  2X1  ≡ 1 मोड(5)

दोनों भुजाओं को 3 से गुणा करने पर, हमें प्राप्त

6X1  ≡ 3 मोड(5)

⇒ X1  ≡ 3 मोड(5)

⇒ X1 = 3

पुनः, उपरोक्त संबंध का प्रयोग करते हुए

5X2  ≡ 1 मोड(7)

⇒ 15X2  ≡ 3 मोड(7)

⇒ X2  ≡ 3 मोड(7)

⇒ X2  = 3

इसलिए x का अद्वितीय हल होगा

X = M1X1a1 + M2X2a2

⇒ X = 7 × 3 × 3 +  5 × 5 × 3 = 138

⇒ X ≡ 138 मोड(35)

⇒ X ≡ 33 मोड(35)

अवधारणा:

रैखिक सर्वांगसमता: रूप ax ≡ b(मोड m) की सर्वांगसमता जहाँ x एक अज्ञात पूर्णांक है, एक चर में रैखिक सर्वांगसमता कहलाती है, जहाँ,

a, b और m पूर्णांक हैं जिनमें m अभाज्य संख्या होनी चाहिए।

विल्सन प्रमेय: इस प्रमेय के अनुसार, यदि p एक अभाज्य संख्या है, तो

(p - 1)! = -1 (मोड P)

दूसरे शब्दों में, जब (P-1)! को P से भाग दिया जाता है तो शेष p - 1 है

⇒ \(\rm Rem\ \left[\dfrac{(P - 1)!}{P}\right] = P \ - \ 1\)

जहाँ  n! = n(n - 1)(n - 2).......3.2.1

उसी प्रकार

(P - 2)! = 1(मोड P)

\(\rm (P\ - \ 3)!\ = \dfrac{P - 1}{2}(mod \ P)\)

गणना:

दिया गया है 

27! = x (मोड 29)  ---(1)

हम देख सकते हैं कि, P = 29 जो अभाज्य संख्या है। इसलिए, विल्सन प्रमेय का उपयोग किया जा सकता है।

हम जानते हैं कि

(P - 2)! = 1(मोड P)

इस गुण के साथ (1) की तुलना करने पर, हम प्राप्त करेंगे

x = 1

अतः विकल्प 1 सही विकल्प है।

गणना:

माना b ∈ Z इस तरह है कि a^b ≡ 1(mod n).

हम विभाजन एल्गोरिथ्म को b और k पर लागू करते हैं, तो हमारे पास है,

b = kq + r जहाँ 0 ≤ r ≤ k

विचार कीजिये, a^b = a^{kq + r} = (a^k)^q . a^r

परिकल्पना ab ≡ 1(mod n) और ak ≡ 1(mod n) करने पर

अतः, ar ≡ 1(mod n) जहाँ 0 ≤ r ≤ k

∴ r को शून्य के बराबर होना चाहिए और अन्यथा k का विकल्प सबसे छोटा धनात्मक पूर्णांक होता है जैसे कि ak ≡ 1(mod n) का खंडन किया जाएगा।

अतः, b = qk

⇒ k | b

⇒ k, b को विभाजित करता है

अतः, सही उत्तर विकल्प 2) है।

अवधारणा:

जैसा कि हम जानते हैं

a \(\equiv\) r (माप b) का अर्थ है जब a को b से विभाजित किया जाता है तो r शेषफल है या इसे इस प्रकार लिखा जा सकता है 

a = bq + r जहाँ q एक घनात्मक पूर्णांक है  

यूलर के मानदंड:

यदि p एक अभाज्य है जहाँ p | a है, तब द्विघात सर्वांगसमता x²  \(\equiv\) a (मापm) के हल हैं या हल नहीं हैं, निर्भर करता है यदि \(a^\left({\frac{p-1}{2}}\right)=1. modp\)  या   \(a^\left({\frac{p-1}{2}}\right)=-1. modp\)

गणना:

x2 + 1 ≡ 0 (माप p)

स्थिति I: x = 1 के लिए

सर्वांगसमता और मापांक की परिभाषा के अनुसार हमारे पास है

p | x² + 1 

माना, x = 1 तब p | 1² + 1 \(\Rightarrow \) p | 2

जैसा कि, p को 2 से विभाजित किया जा सकता है जब p = 2 हो

स्थिति II: x > 1 के लिए

यूलर के मानदंड के अनुसार, p | x² + 1 केवल तब जब \((-1)^\left({\frac{p-1}{2}}\right)=1. modp\) हो

उपरोक्त शर्त केवल तभी सत्य हो सकती है जब (-1) का घातांक सम हो। (जैसा कि (-1)ⁿ = 1 केवल तब जब n सम हो)

इस प्रकार, \(\frac{p-1}{2}\) सम या 2 का गुणक हो सकता है

किसी पूर्णांक m के लिए \(\Rightarrow \frac{p-1}{2}= 2m\) 

\(\Rightarrow p-1= 4m\)

p = 4m + 1 जो p ≡ 1 (माप 4) के बराबर है   

अतः, यदि 'p' एक अभाज्य है, तो सर्वांगसमता x² + 1 ≡ 0 (माप p) का एक हल केवल तभी है जब p = 2 या p ≡ 1 (माप 4) है।

संकल्पना:

चीनी शेष प्रमेय: मान लीजिए n1, n2, ... ,nr ऐसे धनात्मक पूर्णांक हैं जैसे कि i ≠ j के लिए (ni, nj) = 1। तब रैखिक सर्वांगसमता x ≡ ai (mod ni) 1 ≤ i ≤ r की प्रणाली का युगपत समाधान है जो अद्वितीय मॉड्यूलो n1, n2, ... ,nr है।

और उपरोक्त रैखिक सर्वांगसमता प्रणाली का समाधान x = a1N1x1 + a2N2x2 + ... + akNkxk द्वारा दिया गया है।

गणना:

दिया गया,

x ≡ 1(mod 3) ;  x ≡ 2(mod 5) ;  x ≡ 3(mod 7)

हमारे पास n1 = 3 , n2 = 5, n3 = 7 है

और a1 = 1, a2 = 2, a3 = 3

और, gcd(3, 5) =  gcd(5, 7) = gcd(3, 7) = 1

मान लीजिए n = n1. n2. n3

= 3 . 5 . 7

= 105

n = 105

फिर, N1 = n/n1 = 105/3 = 35

N2 = n/n2 = 105/5 = 21

N3 = n/n3 = 105/7 = 15

अब x1, x2 और x3 को खोजने के लिए निम्न सर्वांगसमताओं पर विचार करें

N1x1 ≡ 1(mod n1)

⇒ 35x1 ≡ 1(mod 3)

⇒ x1 = -1

N2x2 ≡ 1(mod n2)

⇒ 21x2 ≡ 1(mod 5)

⇒ x2 = 1

इसी तरह, N3x3 ≡ 1(mod n3)

⇒15x3 ≡ 1(mod 7)

⇒ x3 = 1

अत: x = a1N1x1 + a2N2x2 + a3N3x3 में सभी मानों को प्रतिस्थापित करने पर

x = 1 × 35 × (-1) + 2 × 21 × 1 + 3 × 15 × 1

x = 87 - 35

x = 52

अत: सही उत्तर विकल्प 4) है