18
1ሺmod 3ሻ for all integers k . Now, using the multiplication law, we have: 300 ൌ 3x10 ଶ ؠ ሺ3ሻx1 ؠ 3ሺmod 3ሻ 50 ൌ 5x10 ؠ ሺ5ሻx1 ؠ 5 ሺmod 3ሻ 7 ൌ 7x1 ؠ ሺ7ሻx1 ؠ 7 ሺmod 3ሻ
357 ؠ 0 ሺmod 3ሻ if and only if the digit sum is divisible
Using the addition law,
by 3. Something for you to try: Can you find any patterns within numbers divisible by 9 or 11 using modular arithmetic? ࡼ࢘࢈ࢋ : ࡿࢎ࢝ ࢚ࢎࢇ࢚, ࢌ࢘ ࢋ࢜ࢋ࢘࢟ ࢙࢚࢜ࢋ ࢚ࢋࢍࢋ࢘ , െ ૢ െ ሺെሻ ࢙ ࢇ࢝ࢇ࢙࢟ ࢊ࢙࢜࢈ࢋ ࢈࢟ . ሺ࢚࢙࢘ࢎ ࡹࢇ࢚ࢎࢋࢇ࢚ࢉࢇ ࡻ࢟ࢇࢊ ሻ This problem may look a bit daunting at first sight. However, modular arithmetic can simplify the problem rather nicely. Taking modulo 2000 directly would lead you to nowhere, but we can break down 2000 after which modular arithmetic may be useful. We first express 2000 ൌ 2 ସ x 5 ଷ If the expression is divisible by 16 and 125 , it is divisible by 2000 because 16 and 125 are coprime. This naturally leads us to take modulo 2000 in its prime factors. Solution:
16 and modulo 125. Using the power law,
121 ୬ ؠ 9 ୬ ሺmod 16ሻ 25 ୬ ؠ 9 ୬ ሺmod 16ሻ 1900 ୬ ؠ 12 ୬ ሺmod 16ሻ ሺെ4ሻ ୬ ؠ 12 ୬ ሺmod 16ሻ 9 ୬ െ 9 ୬ 12 ୬ െ 12 ୬ ؠ 0 ሺmod 16ሻ
The whole expression:
121 ୬ ؠ 121 ୬ ሺmod 125ሻ 25 ୬ ؠ 25 ୬ ሺmod 125ሻ
Similarly,
Made with FlippingBook - Online Brochure Maker