# Congruence Class - Proof of a number divisble by 7

1. Oct 5, 2008

### 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.
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.