puzzle

[Thomas Klemm]

(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² ≡ 1 (11), 10³ ≡ -1 (11), 10⁴ ≡ 1 (11) and so on ...

A number say 4153 can be written as 4⋅10³ + 1⋅10² + 5⋅10¹ + 3⋅10⁰.
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.