माना x वह सबसे छोटी संख्या है जिसे 16, 28, 40 और 77 से भाग देने पर प्रत्येक स्थिति में 7 शेष बचता है, लेकिन 19 से विभाज्य है। जब x को 219 से विभाजित किया जाता है तो शेषफल क्या होगा?

दिया गया है:

सबसे छोटी संख्या 'x' को 16, 28, 40 और 77 से भाग देने पर 7 शेष बचता है।

संख्या 'x', 19 से विभाज्य है।

प्रयुक्त सूत्र:

यदि किसी संख्या N को 'd' से भाग देने पर 'r' शेष बचता है, तो N = qd + r, या N ≡ r (mod d).

यदि किसी संख्या N को कई संख्याओं d₁, d₂, ..., d_n से भाग देने पर 'r' शेष बचता है, तो N = LCM(d₁, d₂, ..., d_n) x k + r, जहाँ k एक पूर्णांक है।

गणना:

16, 28, 40 और 77 का LCM।

16 का अभाज्य गुणनखंड = 2⁴

28 का अभाज्य गुणनखंड = 2² x 7

40 का अभाज्य गुणनखंड = 2³ x 5

77 का अभाज्य गुणनखंड = 7 x 11

LCM(16, 28, 40, 77) = 2⁴ x 5 x 7 x 11

⇒ LCM = 16 x 5 x 7 x 11 = 6160

LCM के पदों में संख्या 'x'।

चूँकि 'x' को 16, 28, 40 और 77 से भाग देने पर 7 शेष बचता है:

x = 6160k + 7 (जहाँ k एक धनात्मक पूर्णांक है)

यह शर्त कि 'x', 19 से विभाज्य है।

x ≡ 0 (mod 19)

6160k + 7 ≡ 0 (mod 19)

जब 6160 को 19 से विभाजित किया जाता है तो शेषफल:

6160 = 19 x 324 + 4

इसलिए, 6160 ≡ 4 (mod 19)

इसे संग्रुह में प्रतिस्थापित करें:

4k + 7 ≡ 0 (mod 19)

⇒ 4k ≡ -7 (mod 19)

⇒ 4k ≡ 12 (mod 19) (चूँकि -7 + 19 = 12)

k को हल करने के लिए, हम 19 मॉड्यूलो 4 का गुणात्मक व्युत्क्रम ज्ञात कर सकते हैं। हम एक संख्या 'm' की तलाश करते हैं जैसे कि 4m ≡ 1 (mod 19)। m = 5 के लिए, 4 x 5 = 20 ≡ 1 (mod 19).

4k ≡ 12 (mod 19) के दोनों पक्षों को 5 से गुणा करें:

5 x 4k ≡ 5 x 12 (mod 19)

20k ≡ 60 (mod 19)

चूँकि 20 ≡ 1 (mod 19) और 60 = 3 x 19 + 3, इसलिए 60 ≡ 3 (mod 19):

⇒ k ≡ 3 (mod 19)

k का सबसे छोटा धनात्मक पूर्णांक मान 3 है।

x = 6160k + 7 में k = 3 प्रतिस्थापित करें:

x = 6160 x 3 + 7

x = 18480 + 7

⇒ x = 18487

18487 को 219 से विभाजित करें:

18487 ÷ 219

18487 = 219 x 84 + 91

शेषफल 91 है।

∴ जब x को 219 से विभाजित किया जाता है तो शेषफल 91 है।