Congruence Class - Proof of a number divisble by 7

[thejinx0r]

Hey Guys,

My teacher left us to do the proofs for the tricks that tell us a number is divisible by 3, 7 and 11.

For 3 and 11, they were pretty straight forward since I knew the trick before hand. (a number is divisible by 3 if the sums of the digits are divisible by 3. or divisible by 11 if the sum of the alternating digits is divisible by 11.)

But for 7, I had one trick, but I have to prove it using another trick, which I'm a little less familiar with.

Prove that a positive integer $$N = n_kn_{k-1}...n_0$$ is divisible by 7 if and only if when we let
$$M = n_1 n_2 . . . n_k$$ we have $$M - 2 n_0$$ is divisible by 7.

Where n_k is the k'th digit of the number N.

The only I have written is the expansion of $$M - 2 n_0 = n_1 + 3 n_2 + 3^2 n_3 + ... + 3^{k-1} n_k$$

The 3 comes from the fact that 10 == 3 mod 7.

I was going to do it by induction because you could have a really long number, such that you would have to do repeat the algorithm until you get a reasonable answer. But then I realized that it wouldn't matter since I could not prove that $$M - 2 n_0$$ was divisible by 7.

 

[fresh_42]

$3,189,572 \equiv 1 \mod 7$
$7\cdot 3,189,572 = 22,327,004 =:N$
$M= 72,322 - 2\cdot 4 = 72,314 \equiv 4 \neq 0 \mod 7$

The algorithm I have found is slightly different than yours:

1. drop the last digit
2. double this last digit
3. subtract this number from the number which is left after dropping the last digit (no reverses!)
4. if the difference is negative, drop the minus sign
5. has the result more than one digit, repeat steps 1 to 4
6. if we end up with $7$ or $0$, then the number has been divisible by $7$, otherwise not

\begin{align*}
N&=22,327,004 \\[6pt]
\longrightarrow \quad &2,232,700 - 8 =2,232,692\\
\longrightarrow \quad & 223,269-4 = 223,265\\
\longrightarrow \quad & 22,326-10=22,316\\
\longrightarrow \quad & 2,231-12=2,219\\
\longrightarrow \quad & 221-18=203\\
\longrightarrow \quad & 20-6=14\\
\longrightarrow \quad & 1-8=-7\\
\longrightarrow \quad & 7
\end{align*}