sábado, 30 de agosto de 2014

FRACTIONED CUMULATIVE SUCCESSIVE SUBTRACTIONS


DIVISIBILITY BY 7, 11 AND 13


Successive cumulative subtractions using Modular Arithmetic applied to a series of values result in the alternation of the signs minus and plus regarding each value. 


The use of the modular additive inverse is the best way to reach this alternation. 


To this end the modular additive inverse of the first value is added to the next value and the additive inverse of the result obtained must be added successively to each next value till the procedure reaches the last value. 


Working with module 7, let us establish a series of values and verify the procedure: 


Series: 9; 3; 6; 9; 6


− 9 mod 7 + 3  8; − 8 mod 7 + 6  12; −12 mod 7 + 9  11;
( − 11 mod 7 + 6 ) mod 7  2
 


A practical and quicker way to reach the same result consists of the use of common language: 


9 to 14 = 5; 5 + 3 = 8; 8 to 14 = 6; 6 + 6 = 12; 12 to 14 = 2;

2 + 9 = 11; 11 to 14 = 3; 3 + 6 = 9; 9 − 7 = 2 


Observe that: 9 − 3 + 6 − 9 + 6 = 9 or 9 − 7 = 2, confirming the alternation of the signs minus and plus. 


From now on it will be used just common language. 


To verify the divisibility by 7 of the numbers formed by various periods it is applied the alternate additions and subtractions of the numbers formed by their periods. With a simple adaptation it is possible to verify divisibility by 7 using Modular Arithmetic. 


In this case, instead of working with three-digit numbers, it is necessary to split each period, separating the ones from the hundreds and tens, observing that sometimes the first period does not have the hundreds or both hundreds and tens. 


Two steps are necessary to verify the divisibility by 7 of a multi-period number: 


Step 1 - Apply the cumulative successive subtractions to the ones or to the pair hundreds/tens; if the first digit belongs to the ones, start with the ones, otherwise start with the tens or with the pair hundreds/tens. 


Step 2 - Apply the procedure to the remaining digit or pair of digits. 


Working with the hundreds/tens will result in the tens of a new number.


Working with the ones will result in the ones of a new number.If the new number is a multiple of 7 then the tested number is also a multiple of 7; if not, the new number mod 7 is equivalent to the remainder of the division of the tested number by 7. 


Examples: 


N = 1,554; 1 to 7 = 6; 6 + 4 − 7 = 3 (ones)                   

                  55 − 49 = 6 (tens)            

           63; 7|63 and 7|N 


N = 16,893,543; 1 to 7 = 6; 6 + 89 = 95; 95 to 98 = 3;

                           3 + 54 − 56 = 1 (tens)                            

                           6 to 7 = 1; 1 + 3 = 4; 4 to 7 = 3;

                           3 + 3 = 6 (ones)

                     16; 7∤16 and 16 − 14 = 2 (remainder of N/7)

 

N = 55.253,922,625;

                           48; 7∤48 and 48 − 42 = 6 (remainder of N/7) 


5 to 7 = 2; 2 + 25 = 27; 27 to 28 = 1 + 92 = 93;

93 to 98 = 5; 5 + 62 − 63 = 4 (tens)

5 to 7 = 2; 2 + 3 = 5; 5 to 7 = 2; 2 + 2 = 4;

4 to 7 = 3; 3 + 5 = 8 (ones)


This rule works for numbers of any magnitude. It works also for divisibility by 11 and 13.

 

The reasoning that led to the creation of this rule is so simple that it is incredible that nobody thought of it before.


It works because if 7|N the sum of the alternate numbers formed by the periods of N are equivalent mod 7.  

segunda-feira, 26 de maio de 2014

DIVISIBILITY BY 7 - A DIFFERENT APPROACH


AUTHOR: SILVIO MOURA VELHO
 (INDEPENDENT RESEARCHER)

The History of the Theory of Numbers records the creation of various mathematical rules to check whether a number is divisible by 7, but does not record the creation of a single rule for divisibility by 7, according to the following definition:
“A divisibility rule is a shorthand way of determining whether a given number is divisible by a fixed divisor without performing the division, usually by examining its digits.” (Wikipedia)

At this point, it is useful to add this definition: “A mathematical rule is a method or procedure that describes how to solve a problem.” (Pennsylvania Department of Education Standards Aligned Systems)

If the above-mentioned definitions are correct, only mathematical rules applied quickly (shorthand way) fit the definition of divisibility rule.

The famous north American writer of mathematical issues, Martin Gardner, who is considered "the best friend of Mathematics" and wrote during 25 years the "Mathematical Games" column for the magazine "Scientific American", in his book "Unexpected Hanging" after having addressed the matter divisibility rules, expressed himself this way :

“The reader has surely noticed a singular omission from the foregoing rules. How does one test for 7, the divine number of medieval numerology? It is the only digit for which no one has yet found a simple rule. This disorderly behavior on the part of 7 has long fascinated students of number theory. Dozens of curious 7 tests have been devised, all seemingly unrelated to one another; all, unfortunately, are almost as time-consuming as the orthodox division procedure.”

This page: http://en.wikipedia.org/wiki/Divisibility_rule presents a significant variety of mathematical rules used to check whether a number is divisible by 7, but none of those rules fit the specific definition of "divisibility rule" contained in the referenced page.

All such rules are applied very slowly and move away from the specific definition of divisibility rule, although they are mathematical rules.

The first record of a mathematical rule for divisibility by 7 is mentioned in the Talmud, the Jewish holy book, according to historians. This means that the first draft of a rule of divisibility by 7 began approximately two millennia ago. As until nowadays the mathematical community is divided over the existence or not of a rule of divisibility by 7, the conclusion is that, although elementary, this is a very difficult problem.

Some mathematicians reveal sometimes as a trick, sometimes as a rule, a procedure that well analyzed is not one thing nor the other. 

Let us see how Martin Gardner refers to this procedure, which is disclosed in the most math sites:

 “A bizarre 7 test, attributed to D.S. Spence, appeared in 1956 in The Mathematical Gazette (October, page 215). The method goes back to 1861; see L.E. Dickson, History of The Theory Of Numbers, Vol. 1, page 339, where it is credited to A. Zbikovski of Russia.) Remove the last digit, double it, subtract it from the truncated original number and continue doing this until one digit remains. The original number is divisible by 7 if and only if the final digit is 0 or 7.”

In fact, this test is now used to reduce the number tested to a two-digit number.

The procedure cannot be considered a trick because the explanation of why it works is of an extraordinary elementarity: the double of one-digit number (place value of tens or hundreds and tens) always results with that digit (place value of the ones) a multiple of 7.

Examples: 1 . 2 = 2 → 21; 2 . 2 = 4 → 42; 3 . 2 = 6 → 63 … 6 . 2 = 126; 8 . 2 = 16 → 168 etc.

So the “secret” of the procedure consists in successively subtract multiples of 7 of the original number; if after this sequence of subtractions the result is a number multiple of 7 it is evident that the tested number is a multiple of 7. A trick without a secret is not a trick.

THE PROCEDURE                          PARALLEL PROCEDURE
  
   N = 23,964                                           N = 23,964
             ─ 84 → 7|84                                       ─ 14 → 7|14          
         23,880                                                 23,950                            ─ 1,680 → 7|1,680                                ─ 350 → 7|350
         22,200                                                 23,600                        
        ─ 4,200                                              ─  5,600 → 7|5,600 
         18,000                                                 18,000

Elimingating the zeroes the result in both cases is 18.
7Ɨ18 and 7ƗN

It is important to notice that the procedure consists of successively subtract multiples of 7 of the tested number, until it is reduced to a two-digit number.
 
The parallel procedure excludes the multiplication by two; it needs only the deduction of the digit that forms a multiple of 7 with the excluded digit. It is simpler and possibly quicker, although it eliminates only one digit each time. Scholars did not approve this procedure evidently because its simplicity cannot delude anyone.

The procedure is undoubtedly a mathematical rule to test the divisibility of a number by 7, but because its application is approximately as slow as performing the division, it does not fit the specific definition of “divisibility rule” because surely it is not a “shorthand way” of testing divisibility by 7, especially if applied to large numbers.

A good example of this slowness consists of the application of the procedure to the ten-digit number: N = 3.218.576.8416 and then perform the division of this number by 7, in the orthodox way. A real rule of divisibility is always a shorthand way of verification regardless of the constitution or the quantity of digits of the tested number. Later, the mentioned number will be submitted to the application of a rule that fits the definition of divisibility rule created by me in 2008.

The mathematical community is usually rigorous and respectful towards definitions. Apparently, in the case of a rule of divisibility by 7, the usual rigor was put aside. What is most embarrassing? To adopt a false rule (trick?) or to admit the inexistence of a real rule? Many specialized mathematical sites adopted the second alternative. This fact can be easily confirmed googling the words: “divisibility by 7” and “no rule”.

Approximately, in 1992 I started my quest to create a rule of divisibility by 7. That was when I learned a rule of divisibility as slow as the others, but less publicized. I had the intuition that I would be able to create a better rule and started my studies. I interrupted my research several times, but I always resumed it.

I tried a different approach from that scholars had adopted in creating their rules. The rules created in two millennia of history are generally based in algorithms that eliminate just one digit each time, or in complicated and extremely slow procedures.

My rules, that I denominate as “Moura Velho” rules of divisibility by 7, are always applied in a simpler and quicker way because they eliminate two or more digits in each application of the respective algorithm.

In 2005 I created and made public the first “Moura Velho” rule of divisibility by 7, that fits the specific definition of “divisibility rule” that I consider the first real rule of divisibility by 7 of the History of The Theory of Numbers. Please, see a video of this rule: https://www.youtube.com/watch?v=plRO-L_0cto .

In the following years, I created new “Moura Velho Rules” of divisibility by 7 and in 2008 I created the rule I consider the simplest and quickest. Changing what must be changed, this rule works also for divisibility by 11 and 13. Derived of it, I created my last rule in 2013; it is a little more complex, but it is equally quick. Both rules may be watched, among others, on the site of Vimeo: https://vimeo.com/92571509 .

The “Moura Velho” rules of divisibility by 7 were all included (except the last) in a book inedited until now and officially registered as: “Divisibilidade por 7; o Fim de um Mito?” (“Divisibility by 7: the End of a Myth?”)

This is the algorithm of the rule I created in 2008:

N = a,bcd; a’ ≡ ( ─ cd mod 7 + a ) mod 7 → a’b;
if 7|a’b then 7|N

For larger numbers, the two last digits are eliminated and abcd dislocates to the left until the last pair of digits to the left is reached. If the last pair of digits to the left is incomplete, a zero must be mentally added to compensate for the absence of the digit "a". If the final result a’b is a multiple of 7 the same happens to the tested number.

─ cd mod 7 is the inverse additive mod 7 that corresponds to the difference between cd and the immediately superior multiple of 7.

Example: ─ 12 mod 7 ≡ 2; using common language: 12 to 14 equals 2.

Why it works:

The algorithm works because ─ cd mod 7 ≡ 6 cd mod 7 that is added to the place value of the thousands: + 6,000 cd. As cd is eliminated (subtracted) the procedure results in this operation: 6,000 cd ─ cd = 5,999 cd. As 7|5,999 the value of N mod 7 is preserved in each application of the algorithm. This fact is easily confirmed substituting the eliminated pair of digits by zeroes.

Note : ─ n mod x ≡ ( x ─ 1 ) . n mod x for n and for x.

How it works through a numerical example:

N = 3,218,576,816

This is the number mentioned before.

The algorithm may be applied repetitively from right to left, in an extremely quick and precise way, exclusively through mental calculations, with no need of any annotations.

The steps concerning the application of the rule will be described using the common language, to make easier the understanding.

Step 1: 16 to 21 = 5; 5 + 6 ─ 7 = 4 → 32185748
Step 2: 48 to 49 = 1; 1 + 5 = 6 → 321867
Step 3: 67 to 70 = 3; 3 + 1 = 4 → 3248
Step 4: 48 to 49 = 1; 1 + 3 = 4 → 42; 7|42 and 7|N

The final result (FR) = 42

How to determine the remainder of the division of N by 7:

If 7ƗN, to determine the remainder, it is necessary to perform the counting of number of pairs of digits (n) that form N and subtract : n ─ 1.

If ( n ─ 1 ) mod 3 ≡ 0; r ≡ RF mod 7
If ( n ─ 1 ) mod 3 ≡ 1; r ≡ 2 . RF mod 7
If ( n ─ 1 ) mod 3 ≡ 2; r ≡ 4 . RF mod 7

In 1654 Pascal made public his criterion for divisibility by 7 (theorem 2.5) that consists of multiplying each digit of a number by the following sequence of multipliers:
...231546231
The multiplication of FR by 1, 2 or 4 mod 7 to determine the remainder of the division of N by 7 is based on the sequence of multipliers corresponding to each digit of the ones of each pair of digits (in underline), from right to left.

Example: N = 82,324,544
Step 1 : 44 to 49 = 5; 5 + 4 ─ 7 = 2 → 823225
Step 2 : 25 to 28 = 3; 3 + 3 = 6 → 8262
Step 3 : 62 to 63 = 1; 1 + 8 ─ 7 = 2 → 22; 7Ɨ22 and 7ƗN
The remainder: n = 4; ( 4 ─ 1 ) mod 3 ≡ 0;
 então r = RF mod 7 → 22 mod 7 ≡ 1

The remainder of the division of N by 7 equals 1.

So I finish the presentation of my preferred Moura Velho Rule of divisibility by 7. I chose it because its algorithm is easily apprehended and its application is extremely quick and precise. However, any Moura Velho Rule of divisibility by 7 is quicker than any other rule created by other researchers in two millennia of history.

I hope that the mathematical community welcomes the “Moura Velho” rules of divisibility by 7 for the sake of justice and recognition of the enormous research I conducted over approximately twenty years. Mathematics as science has no ego; it has already hosted the “Moura Velho” rules of divisibility by 7.

quinta-feira, 15 de maio de 2014


Watch this video:

http://vimeo.com/92940268 

 

DETAILS OF THE FIFTH MOURA VELHO RULE


This post is designed to clarify details of the fifth Moura Velho rule of divisibility by 7 presented in a recent video as a bonus.Changing what must be changed, this rule works also to test divisibility by 13.

THE ALGORITHM


N = abc; xabc → 7|xa; S = x + bc; if 7|S then 7|N


For larger numbers, this algorithm must be applied repetitively to each period of N. The inverse additive mod 7 of each sum (S) must be added to the digit “x” of the next period and to the number formed by the two following digits.

The procedure must be applied until the rightmost period of N is reached. If 7|FR (final result) then 7|N. If 7ƗFR then FR mod 7 is the remainder of the division of N by 7.

If the initial period is incomplete, the algorithm must be applied partially.

WHY IT WORKS



Digit “x” is equivalente to 2a mod 7 and bc is equivalente to ( 3b + c ) mod 7. Then the sum of the products mod 7 obtained by the application of the algorithm is: SP = 2a + 3b + 1c and the multipliers are respectively: 2, 3 and 1, exactly the same multipliers established by Pascal in his criterion for divisibility by 7 (theorem 2.5) to the three digits of the period of the first order, as mentioned before.


Applying the inverse additive mod 7 to SP:

─ ( 2a + 3b + c ) mod 7 ≡ 5a + 4b + 6c.


For larger numbers, the following period is formed by the digits “def”. The application of the algorithm to the following period results in SP = 2d + 3e + f and the aggregated sum of both periods is SP = 5a + 4b + 6c + 2d + 3e + f, whose multipliers are: 5, 4, 6, 2, 3 and 1 that are the multipliers established by Pascal when he created his criterion for divisibility by 7.


If the number is formed by various periods, the successive and cumulative application of the inverse additive mod 7 to each sum obtained in the passage of one period to another implies the successive repetition of the multipliers established by Pascal: ...31546231546231


The application of this rule is valid because it is equivalent to the application in mod 7 of the multipliers established by Pascal in his criterion for divisibility by 7.


If 7|FR (final result) then 7|N; if 7ƗFR then FR mod 7 is equivalent to the remainder of the division of N by 7.


HOW IT WORKS AND REMAINDER


Mental calculation may be performed very quickly. Notes are used only to illustrate the application of the rule.


N = 62,324,452; 62; (6)324, (1)452
─ 62 mod 7 + 6 + 24 = 31; ─ 31 mod 7 + 1 + 52 = 57; 7Ɨ57 and 7ƗN; RF = 57; 57 mod 7 ≡ 1 = remainder of the division of N by 7.


N = 362,458,923,312; (6)362, (1)458, (4)923, (6)312
6 + 62 = 68; ─ 68 mod 7 + 1 + 58 = 61;

─ 61 mod 7 + 4 + 23 = 29; ─ 29 mod 7 + 6 + 12 = 30; 7Ɨ30 and 7ƗN; RF = 30; 30 mod 7 ≡ 2 = remainder of the division of N by 7.