Exercise 1.3.8 (A test for divisibility by $7$.)

Question

A test for divisibility by $7$. Starting with any positive integer $n$, subtract double the units digit from the integer obtain from $n$ by removing the unit digit, giving a smaller integer $r$. For example, if $n = 41283$ with unit digit $3$, we subtract $6$ from $4128$ to get $r = 4122$. The problem is to prove that if either $n$ or $r$ is divisible by $7$, so is the other. This gives a test for divisibility by $7$ by repeating the process. From $41283$ we pass to $4122$, then to $408$ by subtracting $4$ from $412$, and then to $24$ by subtracting $16$ from $40$. Since $24$ is not divisible by $7$, neither is $41283$.

Richard Ganaye · Accepted Answer

\begin{proof} Let $n = \overline{a_ma_{m-1}\cdots a_0} = \sum\limits_{i=0}^m a_i 10^i$. The integer $n'$ obtained by removing the unit digit is 
$$n'=  \overline{a_ma_{m-1}\cdots a_1} = \frac{n -a_0}{10}.$$
Then
\begin{align*}                                                                    
r = n' -2a_0 = \frac{n-a_0}{10} - 2a_0 = \frac{n-21a_0}{10}.
\end{align*}
Now we prove 
$$r = n' -2a_0 = \frac{n-21a_0}{10} \equiv 5 n \pmod 7.$$
($5$ is the inverse of $10$ modulo $7$.)

Indeed, $\frac{n-21a_0}{10}$ is an integer, and since $7$ is prime with $10$,
\begin{align*}
 7 \mid \left (5n -  \frac{n-21a_0}{10}ight) & \iff 7 \mid 10 \left(5n - \frac{n-21a_0}{10} ight) \
 &\iff 7 \mid  50n - n + 21 a_0 =  49n +21 a_0 = 7(7 + 3a_0).\
 \end{align*}
 Since the last proposition is true, this shows that
 $$r  \equiv 5 n \pmod 7.$$
 Therefore $7 \mid n$ if and only if $7 \mid 5n$, if and only if $7 \mid r$. If either $n$ or $r$ is divisible by $7$, so is the other.
\end{proof}

Exercise 1.3.8 (A test for divisibility by $7$.)

Answers

Comments

Exercise 1.3.8 (A test for divisibility by $7$.)

Answers

Comments

Add answer