Why no quick check for divisibility by 7?

Question

Quick rules posters for checking divisibility of numbers by integers 2 through 9 never give a quick rule for divisibility by 7. What is the best explanation of the reason for this?

Answer 1

N is divisible by 7 if subtracting twice the last digit of N from the remaining digits gives a multiple of 7 (e.g. 658 is divisible by 7 because 65 - 2 x 8 = 49, which is a multiple of 7.

= = = = =

Prove that when a number is divisible by 7, the result when subtracting twice the last digit from the number formed by the remaining digits is a multiple of 7.

Let the number be N=10a+b, where b is the last digit of N and a is the number formed by the remaining digits.

Now we have to prove that if a−2b is divisible by 7, then N=10a+b must be also divisible by 7.

Let a−2b=7k, where k is an integer, and multiply this equation by 10 and add b to both sides. Then you'll get

10a−20b+b=70k+b.

Now move −20b to the right, and you'll get

10a+b=N=70k+21b,

which is a multiple of 7

= = =

Note to tutor Stanton D.: [ see the RSA Problem article on Wikipedia. ] "RSA public key requires that N be a large semiprime (i.e., a product of two large prime numbers)..." To divide key N by primes less than SQRT(N) ... sounds simple.

Answer 2

This essential question might come in various disguises: "Select the best reason .... from the list", or "how much more work is it ...."

Consider the multiplicative inverses for the integers 2 – 9. All of them have a short repeat sequence, shown in parentheses (): ½ = 0.5(0)..., 1/3 = 0.(3) … , ¼ = 0.25(0) … , 1/5 = 0.2(0) …, 1/6 = 0.(16) … , 1/8 = 0.125(0) …, 1/9 = 0.(1) … . All except for 1/7 = 0.(142857) … !

Since checking for divisibility entails some operation using these inverses, this is a cumbersome task for divisibility by 7. Essentially (if you really get into it), you must write your number in groups of 6 digits (starting from the ones place and moving left), multiply placewise by the mask “546231”, and sum all these products. If the obtained result is divisible by 7, so is the original number. As an example,

2 2 2 2 2 2 2 2 4 is placewise multiplied:

x 2 3 1 5 4 6 2 3 1 (note that the mask is aligned R->L)

= 4 + 6 + 2 +10 +8 +12 +4 +6 + 4 = 56; 56/7 = 8 exactly, so 222,222,224 is divisible by 7. Obviously this whole rigmarole is more lengthy than just dividing the original number outright, so it's never taught or used (ordinarily … but if you're into factoring public key cryptographic code, you have to start somewhere....).