Finding divisibility of a number using modular arithmetic

Question

Let N = 12345678910111213141516171819. How can I use modular arithmetic to show that N is (or isn't) divisible by 11? In general, how can I apply modular arithmetic to determine the divisibility of an integer by a smaller integer? I am finding modular arithmetic very confusing and unintuitive. I can understand "simple" modular arithmetic like the 24-hour day etc. but when it comes down to finding the modulo of high raised powers, or checking divisibility of large integers, I am totally lost.

Answer 1

First, since $10\equiv -1$ (mod $11$), notice that $10^k\equiv (-1)^k$ (mod $11$). Then, given your number, which can be written more generally as $$ d_n10^n+d_{n-1}10^{n-1}+\dots+d_1\cdot10+d_0, $$ consider what the above expression is (mod $11$). When the above is looked at "with mod 11 goggles on," all of the instances of $10^k$ can be replaced with $(-1)^k$, which leaves an alternating sum of digits.

Answer 2

You want to find what that number is mod 11. The good thing is, you don't have to get the answer in one go. You just keep applying the rule 'any multiple of 11 goes away'. Notice that at the start of the number you have some power of 10 times 12. That it therefore the same as that multiple of 10 times 1. So replace the 12 by a 1. Now your number starts with a 13, which can be replaced with a 2...

Answer 3

Hint:

$f(x)=\displaystyle\sum_{i=0}^mc_ix^i\ \ (c_i \in \mathbb{Z} \ \forall i)\land a\equiv b \pmod n \implies f(a)\equiv f(b) \pmod n$

Answer 4

$N = a,bcd$; $a' \equiv (− cd \mod 11 + a) \mod 11 \rightarrow a'b$

$N = bcd;$ $a' \equiv (−cd \mod 11 + 0) \mod 11 \rightarrow a'b$

If $11 |a 'b$ then $11|N$

Apply the algorithm repetitively from right to left, always eliminating the last two digits.If the result is a multiple of $11$ then the tested number is also a multiple of $11$. This algorithm works quickly for divisibility by $7$, $11$ and $13$.

Regarding divisibility by $7$, Google: Youtube, "divisibility by $7$", "large number"