(06-29-2018 12:15 PM)Don Shepherd Wrote: [ -> ]Wow, I learned something new today, the divisibility by 11 test.
That's because 10 ≡ -1 (11); that is modulo 11.
Hence 10
2 ≡ 1 (11), 10
3 ≡ -1 (11), 10
4 ≡ 1 (11) and so on ...
A number say 4153 can be written as 4⋅10
3 + 1⋅10
2 + 5⋅10
1 + 3⋅10
0.
So we end up with: 4153 (11) ≡ 4⋅(-1) + 1⋅1 + 5⋅(-1) + 3⋅1 (11) ≡ - 4 + 1 - 5 + 3 (11) ≡ -5 (11) ≡ 6 (11).
And then of course if the remainder is 0 the number is divisible by 11.
There are a lot of other
divisibility rules.
For 23 we have:
Quote:Add 7 times the last digit to the rest.
2231
223 + 7⋅1 = 230
23 + 7⋅0 = 23
Thus we can conclude that: 23 | 2231
The reason is that since 70 ≡ 1 (23) we get:
7⋅(10a + b) ≡ 70⋅a + 7⋅b ≡ 1⋅a + 7⋅b ≡ a + 7⋅b (23)
Now 7 doesn't divide 23, so we see that:
10a + b ≡ 0 (23) ⇔ a + 7⋅b ≡ 0 (23)
This magic number can be found for each prime
p as the multiplicative inverse of 10 in ℤ
p.
For
p = 23 we have 7 since 7⋅10 = 70 ≡ 1 (23)
For
p = 7 we have 5 since 5⋅10 = 50 ≡ 1 (7)
We can use the
Euclidean algorithm to find this number for e.g.
p = 17.
We just try to represent the remainder
r in each step as:
r = a⋅10 + b⋅17 for integer values
a and
b.
7 = 17 - 10 = -1⋅10 + 1⋅17
3 = 10 - 7 = 2⋅10 - 1⋅17
1 = 7 - 2⋅3 = 3⋅17 - 5⋅10
Thus we end up with: 1 ≡ - 5⋅10 (17)
And thus the magic number is -5. Or 12 if you prefer since both are the same modulo 17.
This explains the mentioned rule:
Quote:Subtract 5 times the last digit from the rest.