[Math] Divisibility rules based on modulo arithmetic.

modular arithmetic

In Uspensky's text 'Elementary Number Theory' on pg. 131 there are 3 rules given for division by $9, 3, 11$. I am detailing below, with the exercise part for the same for $7$:

Let a number $N$ be represented in the decimal notation as :
$$N = a + 10b + 10^2c + 10^3d + …$$

(i) Rule for divisibility by $9$:
Notice that :
$$10 \equiv 1, 10^2 \equiv 1, 10^3 \equiv 1,…\pmod 9 $$

So, if the sum of digits ($a+b+c+..$) is divisible by $9$, then divisible by $9$.

— same for divisibility by $3$, as $10 \equiv 1, 10^2 \equiv 1, 10^3 \equiv 1,…\pmod 3$.
.

(ii) Rule for divisibility by $11$:
Notice that :
$$10 \equiv -1, 10^2 \equiv 1, 10^3 \equiv -1,…\pmod {11} $$

So, if the sum of alternating sign digits ($a-b+c-d+e…$ ) is divisible by $11$, then number is divisible by $11$.


But, how to find such modulo based division rule for $7$, which has no easy pattern.
$$10 \equiv 3, 10^2 \equiv 2, 10^3 \equiv 6, 10^4 \equiv 4, 10^5 \equiv 5, 10^6 \equiv 1, …\pmod 7 $$
This cycle repeats after every 6 digits.

So my incomplete attempt is:
$n = 1\cdot g + 5\cdot f + 4\cdot e + 6\cdot d + 2\cdot c + 3\cdot b + a$
for first 7 digits, so need consider only groups of $6$ digits:
$n = 5\cdot f + 4\cdot e + 6\cdot d + 2\cdot c + 3\cdot b + a$ for first 6 digits.

Best Answer

Let's take a number $x = \overline{abcde}$

Now, $x = 10 \cdot \overline{abcd} + e$. Note that multiplying $x$ by values that are not $7$ change its value $\mod 7$ but do not change its divisibility.

$$5x = 50\cdot \overline{abcd} + 5e \equiv \overline{abcd} + 5e\mod7 $$

This process can continue onwards, where you add all digits except the last, then add $5$ times the last.

I'll give an example to help out

$$x=7142835$$ Clearly this is divisible by $7$ by quick inspection. $$x = 10(714283) + 5$$ Now we can take this modulo $7$ $$x = 10(714283) + 5 \equiv \ ? \mod 7$$ Assume this is divisible by $7$ $$x \equiv 0 \mod 7$$ Then, $$5x \equiv 5 \cdot 0 \equiv 0\mod 7$$ However, if $x$ is anything else $\mod 7$, then itwill NEVER become zero if you keep multiplying by $5$

Therefore,

$$\text{if } 10(714283) + 5 \equiv 0 \mod 7$$ $$10(714283) + 5 \equiv 50(714283) + 25 \equiv (714283) + 25 \equiv714308 \mod 7$$ $$714308 \equiv 10(71430) + 8\equiv 71430 + 40 \equiv71470$$ $$71470 \to 7147$$ $$7147 \to 714 + 35 = 749$$ $$749 \to 74+9 = 63$$ Which you should now know is divisible by $7$

Related Question