General divisibility tests of form $\, 7\mid10b+a\!\iff\! 7\mid b-2a\!\iff\! 7\mid b+5a$.

Question

I am currently helping a friend with their problem sheet. They have been given the question

Let $n\in\mathbb{N}$ have digits $a_r, \dots a_1,a_0$, so that

$$n=10^ra_r+\dots+10^2a_2+10a_1+a_0 = 10b+a_0$$

Prove that $\,7\mid n\,$ if and only if $\,7\mid 10^{r-1}a_r+\dots+a_1-2a_0 = b-2a_0$.

I have attempted this. First, I remarked that 10 is congruent to 3 mod 7, which gives us $(10)^s\equiv (3)^s\mod 7$, and hence $n\equiv a_0+3a_1+\dots+(3)^ra_r\mod 7$. So $7|n\iff n\equiv0\mod 7$.

However I'm unsure as to where to go from here. If I continue in the same manner I reach a result that is nothing like that which I am required to prove.

Could I have some elucidation as to which way I should go from here?

Answer 1

Hint: From $n$, subtract $21\cdot a_0$, and then divide the result by $10$.

Answer 2

Because $\gcd(10,7) = 1$ then $7|k\iff 7|10k$.

And $7|m \iff 7|m + 7*j$ for any $j\in \mathbb Z$.

....

Notice

$n = \sum_{i=0}^r a_i10^i$ and $m =-2a_0 + \sum_{i=1}^r a_i10^{i-1}$.

$10m = -20a_0 + \sum_{i=1}^r a_i10^{i}$

$10m + 21a_0 = a_0 + \sum_{i=1}^r a_i10^{i}=\sum_{i=0}^r a_i10^{i}=n$

.....

$7|m \iff 7|10m \iff 7|10m + 21a_0=n$

Answer 3

Let $N=10a+b$

$$N=7a+(3a+b)$$ $$N=14a+(6a+2b)$$ $$N=21a+(-a +2b)$$ $$-N=-21a+(a-2b)$$ $$21a-N=(a-2b)$$ $$21a-(a-2b)=N$$

If $7|A$ and $7|B$, then $7|(A-B)$ and $7|(A+B)$ by the distributive property.

So $21a$ is clearly divisible by 7. Then if $7|(a-2b)$, $7|N$.

Conversely, $21a-N=(a-2b)$. If $7|N$, then $7|(a-2b)$.

So $7|N$ iff $7|(a-2b)$

By similar reasoning, $7|N$ iff $7|(3a+b)$.

You might want to try a similar proof for :

Given, $N=100a+10b+c$, $7|n$ iff $7|(2a+3b+c)$

Answer 4

[Below we use congruence (modular) arithmetic, notably the congruence sum and product rules. Readers unfamiliar with congruences please skip ahead to "Without mod" below, and note that the notation $\ a\mid b\ $ means $\ a\,$ divides $\,b,\,$ i.e. $\, an = b\,$ for some integer $\,n$].

Let's derive the test. Let $\, n = 10b + a\,$ for $\,a = $ units digit. Working $\!\bmod 7,\,$ the idea is to simplify $\,b$'s coefficient $\,10\,$ to $\,1,\,$ by scaling $\,n\,$ by $\,\color{#c00}{10^{-1}\equiv -2},\ $ by $\, \color{#c00}{-2\cdot 10\equiv 1}\pmod{\!7},\,$ i.e.

$$\begin{align} 7\ \mid\ 10b+a\ \,&\\ \iff\qquad\! 10 b+a\ \,& \equiv 0\pmod{\!7}\\ \color{red}\iff \color{#c00}{-2}\,(\color{#c00}{10}b+a)&\equiv 0\ \ \ \ {\rm by\ \ } {-2} \times \rm prior\\ \iff\qquad\ \ b\color{#0a0}{-2}a\ &\equiv 0\ \ \ \ {\rm by}\ \ \color{#c00}{{-}20\equiv 1}\\ \iff\qquad\ \ b\color{#0a0}{+5}a\ &\equiv 0\ \ \ \ {\rm by}\ \ \color{#0a0}{{-}2\ \equiv\ 5} \end{align}\qquad\qquad$$

$${\rm so}\ \quad \bbox[6px,border:1px solid #c00]{7\mid 10b+a\iff 7\mid b-2a\iff 7\mid b+5a}\qquad\qquad\qquad $$

The same works for any divisor $\,d\,$ coprime to $10$ using $\,\color{#c00}{c\equiv 10^{-1}\pmod{\!d}}$

$$\begin{align} d\ \mid\ 10b+a\ \,&\\ \iff\qquad\! 10 b+a\ \,& \equiv 0\pmod{\!d}\\ \color{red}\iff \ \ \ \color{#c00}c\,(\color{#c00}{10}b+a)&\equiv 0\ \ \ \ {\rm by\ \ } c \times \rm prior\\ \iff\qquad\ \ b+\color{#c00}{c}a\ &\equiv 0\ \ \ \ {\rm by}\ \ \color{#c00}{10c\equiv 1}\\ \end{align}\qquad\qquad\ \ \ $$

$${\rm so}\ \quad \bbox[6px,border:1px solid #c00]{d\mid 10b+a\iff d\mid b+\color{#c00}c\:\!a,\,\ \color{#c00}{c\equiv 10^{-1}}\!\!\!\!\!\pmod{\!d}}\qquad\qquad\quad $$

The $\color{#c00}{\rm second}\!\!\color{red}{\iff}$ is bidirectional since scaling by an invertible element is an invertible operation: $ $ to invert scaling by $\color{#c00}{-2}\,$ we scale by its inverse $\color{#c00}{10}$, i.e. $10\,\times$ the second congruence yields the first. Generally - like equations - scaling a congruence by an invertible number yields an equivalent congruence (recall a modular integer is invertible $\!\iff\!$ it is coprime to the modulus, by Bezout).

This method works for any coprime divisor $\,d\,$ and radix $\,r\,$ exactly as above, i.e. $$\bbox[6px,border:1px solid #c00]{d\mid r\:\!b\!+\!a\iff d\mid b\!+\color{#c00}{\hat r}a,\ \ {\rm for}\ \ \color{#c00}{\hat r \equiv r^{-1}}\!\!\!\!\!\pmod{\!d}}\qquad $$

Without mod $\ $ Eliminating congruence language above yields more elementary proofs

By $\color{#90f}{\rm Lemma}$: $\ \gcd(\color{#c00}{7,-2})=1\, $ so $\, 7\mid 10\,b\,+\,a\ \iff\ \ \color{#c00}{7\,\mid\! {-}2}(10b\!+\!a)\!\color{#0a0}{+\!7(3b)} = b - 2a$

By $\color{#90f}{\rm Lemma}$: $\ \gcd(\color{#c00}{7,\,5})\:=\:1\,$ so $\ 7\mid 10\,b\,+\,a\ \iff\,\ \color{#c00}{7\, \mid\,\ 5}\:(10b\!+\!a)\!\color{#0a0}{-\!7(7b)} =\, b +5a$

$\color{#90f}{\bf Lemma}\ $ If $\, \gcd(\color{#c00}{7,c})=1\,$ then $\ 7\mid n\!\!\!\!\overset{\rm EL\!\!}\iff\!\! \color{#c00}{7\mid c}n\!\!\iff\! \!\color{#c00}{7\mid\, c}\,n \color{#0a0}{+7\, m}\, $ by $\rm EL = $ Euclid's Lemma

Remark $ $ The divisibility test works for all integers $\,a,b\,$ (not only digits in decimal radix rep), e.g. $\,a,b\,$ can be negative. Said in fractions: $\,10b+a\equiv0\iff b\equiv -a/10\equiv 2a\pmod{\!7}.\,$ Note that the special case $\,a\equiv -1\,$ yields the inverse of $10,\,$ namely $\,1/10\equiv -2.\,$ Exactly the same method as above works for any divisor $\,d\,$ coprime to the radix $\,r\,$ $(\!\!\iff\! r\,$ is invertible $\!\bmod d)$.

Alternatively we can use the universal divisibility test which - unlike the above divisibility test which computes only a binary truth value - has the advantage of computing the remainder, so can be used to check arithmetic, etc, as in casting out nines and elevens.

---

Below is a common variant of such divisibility tests, e.g. see here (deleted), or here (brilliant.org)

Theorem $ $ If $\,10c\!-\!ud=\color{#c00}1\,$ then $\,10t\!+\!u\mid 10b\!+\!a \iff 10t\!+\!u\mid b\!+\!(c\!+\!dt)a,\,$ e.g.

$$\!\begin{align}&n=10t\!+\!1 \mid 10b\!+\!a\iff n\mid b\!+\!(1\!+\!9t)a \iff n\mid b-t\:\!a\\[.1em] &n=10t\!+\!3\mid 10b\!+\!a\iff n\mid b\!+\!(1\!+\!3t)a\\[.1em] &n=10t\!+\!7\mid 10b\!+\!a\iff n\mid b\!+\!(5\!+\!7t)a \iff n\mid b\!-\!(2\!+\!3t)a\\[.1em] &n=10t\!+\!9\mid 10b\!+\!a\iff n\mid b\!+\!(1+\:\!t)a\end{align}\qquad\ $$

Proof $\bmod \!10t\!+\!u\!:\ 10\,(b\!+\!(c\!+\!dt)a) = 10b\!+\!(\color{#c00}1)a\,$ by $\,10t\equiv -u,\,$ hence

$$n=10t\!+\!u\mid 10b+a\iff \color{#0a0}{n\mid 10}\,(b\!+\!(c\!+\!dt)a)\iff n\mid b\!+\!(c\!+\!dt)a\qquad$$

follows by Euclid's Lemma, since $\color{#0a0}{(n,10)} = (10t\!+\!u,10)=(u,10)=\color{#c00}1.\ \small\bf QED$

$10c\!-\!ud=1\Rightarrow\bmod 10\!:\ d\equiv -u^{-1},\,$ e.g. we can choose $\,d = -u^{-1}\bmod 10.$

E.g. $\,u = 1\Rightarrow\, d\equiv -1/1\equiv 9 ,\,$ so $\,c = (1\!+\!ud)/10 = 1,\,$ so

$\qquad\qquad\begin{align}n=10t\!+\!1\mid 10b\!+\!a\iff& n\mid b\!+\!(1\!+\!9t)a\\ \iff& n\mid b-t\:\!a\end{align}$

E.g. $\,u = 3\Rightarrow\, d\equiv -1/3\equiv 9/3\equiv 3,\,$ so $\,c = (1\!+\!ud)/10 = 1,\,$ so

$\qquad\qquad n=10t\!+\!3\mid 10b\!+\!a\iff n\mid b\!+\!(1\!+\!3t)a$

E.g. $\,u = 7\Rightarrow\, d\equiv -1/7\equiv 9/(-3)\equiv -3\equiv 7,\,$ so $\,c = (1\!+\!ud)/10 = 5,\,$ so

$\qquad\qquad\begin{align}n=10t\!+\!7\mid 10b\!+\!a\iff& n\mid b\!+\!(5\!+\!7t)a\\ \iff& n\mid b\!-\!(2\!+\!3t)a\end{align}$

E.g. $\,u = 9\Rightarrow\, d\equiv -1/9\equiv 9/9\equiv 1 ,\,$ so $\,c = (1\!+\!ud)/10 = 1,\,$ so

$\qquad\qquad n=10t\!+\!9\mid 10b\!+\!a\iff n\mid b\!+\!(1\!+\!t)a$