Congruence Class - Proof of a number divisble by 7

  • Thread starter thejinx0r
  • Start date
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 [tex]N = n_kn_{k-1}...n_0[/tex] is divisible by 7 if and only if when we let
[tex]M = n_1 n_2 . . . n_k [/tex] we have [tex] M - 2 n_0[/tex] 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 [tex] M - 2 n_0 = n_1 + 3 n_2 + 3^2 n_3 + ... + 3^{k-1} n_k [/tex]

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 [tex] M - 2 n_0[/tex] was divisible by 7.
 

fresh_42

Mentor
Insights Author
2018 Award
11,133
7,652
## 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*}
 

Want to reply to this thread?

"Congruence Class - Proof of a number divisble by 7" You must log in or register to reply here.

Related Threads for: Congruence Class - Proof of a number divisble by 7

  • Posted
Replies
9
Views
3K
  • Posted
Replies
2
Views
2K
  • Posted
Replies
22
Views
4K
Replies
3
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top