17
ܾܽ . Therefore, using
The only term in the expression that is not a multiple of n is
cd ൌ ab ሺmod nሻ
the addition law,
3) Power
If a ؠ b ሺmod nሻ, then a ୩ ؠ b ୩ ሺmod nሻ Proof:
Let b ൌ a pn ՜ b ୩ ൌ ሺa pnሻ ୩ =
܉ ܓ ൫ ୩ ଵ ൯ a ୩ିଵ ሺpnሻ ଵ +
൫ ୩ ଶ ൯ a ୩ିଶ ሺpnሻ ଶ +......+
ሺpnሻ ଶ୩
From the binomial expansion, the only term not divisible by ݊ is ܽ . ࡼ࢘࢈ࢋ : ࢃࢎ࢟ ࢙ ࢇ ࢚ࢋࢍࢋ࢘ ࢊ࢙࢜࢈ࢋ ࢈࢟ ࢌ ࢇࢊ ࢟ ࢌ ࢚࢙ ࢊࢍ࢚ ࢙࢛ ࢙ ࢊ࢙࢜࢈ࢋ ࢈࢟ ? A quick check on a few examples can be shown to be consistent with this rule. ૠ ൌ 3x119 Digit sum check: 3 5 7 ൌ 15 ൌ 3x5 ൌ 10x3. . .2 Digit sum check: 3 2 ൌ 5 ൌ 3x1 2 This fact amazed me when I first encountered it, but I never understood why it works until I read about modular arithmetic. Proof: Notice that each integer can be broken down into a sum of integers that are multiples of powers of 10. ૠ ൌ 300 50 7 ൌ 30 2 We can express them individually as multiples of powers of 10. 300 ൌ 3x10 ଶ 50 ൌ 5x10 7 ൌ 7 Notice that 10 ؠ 1ሺmod 3ሻ . Using the power law, 10 ୩ ؠ 1 ୩ ሺmod 3ሻ , thus 10 ୩ ؠ
Made with FlippingBook - Online Brochure Maker