Talk:Divisibility rule

From Wikipedia, the free encyclopedia

WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Mid Priority  Field: Basics
Divisibility rule was a good article nominee, but did not meet the good article criteria at the time. There are suggestions below for improving the article. Once these are addressed, the article can be renominated. Editors may also seek a reassessment of the decision if they believe there was a mistake.

Reviewed version: June 19, 2006

Contents

[edit] Good Article nomination has failed

The Good article nomination for Divisibility rule has failed, for the following reason(s):

almost non-existent lead; disorganization; inconsistent prose; informal tone; no referencing

[edit] major revision

I've noticed there was more or less the only one person still editing on that article within the last 9 months and before that a larger discussion of how to improve it (without being implemented).

I'm considering a major rewrite of the article and actually splitting it up in probably 3 different ones

  • basic ideas, few rules, generalizations of the ideas/concepts
  • a somewhat comprehensive list of divisibilitiy rules
  • proofs & techniques

The latter 2 are basically new articles and don't concern the original articles, however i'd like to use the occasion to completely rewrite (in particular shorten) the original article as well. That means most of its content would be deleted or moved to the other articles. However I don't want to do such extensive modifications without the original contributors being ok with it. So let me know if there any objection or if you have any suggestions for the rewrite.--Kmhkmh 16:53, 17 April 2007 (UTC)

I would definitely support such a movement and help where I could. As long as you cite what you replace, I have no problem with my work being redone... I'll ask Cryptic C62 to make a statement also, as he did quite a bit here a while back. -- Rmrfstar 22:24, 17 April 2007 (UTC)
Bah, a statement? Do what you will. All I ever did was crank out original researchy home-made rules. --Cryptic C62 · Talk 23:06, 17 April 2007 (UTC)

[edit] Split from Divisor topic

OK, I moved the material, although I'd still like to talk about a name change for the "new" topic. --Jay (Histrion) 20:23, 6 August 2005 (UTC)

how about "Divisibility test"? -- Yannick Gingras 15:30, August 7, 2005 (UTC)
I changed the visible part of the pipe over at Divisor to "properties". If that sticks there then maybe that is another potential name. Walt 00:06, 29 May 2006 (UTC)

[edit] Proofs

I agree that the proofs should be moved to another page but it is not clear yet if this should be a regular page or a subpage. User:Linas made a request for the subpages, maybe we should wait for the decision. -- Yannick Gingras 15:26, August 7, 2005 (UTC)

I don't think it's appropriate for the proofs to be here. The proofs are not too hard to work out and most mathematics pages on Wikipedia do without. — ciphergoth 22:24, August 7, 2005 (UTC)
I don't think that those are that easy to work out for someone who first learn about divisibility test. I find that knowing why it works helps a lot to remember them. Maybe some explanation with prose would be better but I fear that it might become too long. Most articles don't include the proofs but on W:WikiProject_Mathematics/Proofs it is said that including proofs can be helpfull if they are put aside from the main article. Act how you think will yield the greatest good for everyone, I won't start a revert war. -- Yannick Gingras 02:44, August 9, 2005 (UTC)
I've cut the proofs down to a representative sample and tidied them up a bit. Some were deleted because they would need to be fixed in order to stay: eg where it says "6 = 2 x 3" that's not nearly sufficient justification; as a counterexample to the explicit rule, 4|12 and 6|12 but (4 x 6) does not divide 12. — ciphergoth 07:57, August 9, 2005 (UTC)
I agree with shortening the proofs. About making proofs subpages (se e the very top comment in this section), I think the use of subpages is very discouraged on Wikipedia. Basically, proofs should be in the same text as the theorem, but proofs should be avoided or made sketches unless they add significant value in understanding the article. That's my 2c. Oleg Alexandrov 15:40, 9 August 2005 (UTC)
So do you think there's merit to my contention that we would probably be wisest to remove them altogether? — ciphergoth 22:09, August 9, 2005 (UTC)

Fine to me either way. Now the proofs are in a separate section, and that section is at the very bottom of the article, so there is not much harm done to keep then in. So I am not sure if I would strongly support removing them.

The situation was of course very different before the article was split off. Then the proofs took a lot of real estate in the middle of the article obscuring more important stuff.

So, I think keeping the proofs they way they are now is not too bad. But I would not object to them being removed or even more shortened either. Oleg Alexandrov 22:14, 9 August 2005 (UTC)

[edit] 53

I think 50 is enough. After that, it becomes useless information and Wikipedia is not the place for that. -- Rmrfstar 00:59, 25 March 2006 (UTC)

I agree, 50 is a good place to stop. There might even be a case for stopping much earlier. — ciphergoth 22:23, 26 March 2006 (UTC)
I somewhat strongly disagree to that, wikipedia can (and mayb even should) a large list of divisibility rules.Keep in mind the math portal is used as reference by mathematicians and for specific math facts as well.From my point of view it is more a question of properly organizing the material in either long article with sensible chapters (which could be skipped by a reader not interested in them) or perhaps even better

split it in serveral separate articles - for instance:

  • basics including a few rules
  • comprehensive list of rules
  • proofs

--Kmhkmh 12:11, 17 April 2007 (UTC)

I'm fine with that: if there's a dedicated list, I won't mind any extra rules because they won't interfere with the content. -- Rmrfstar 22:26, 17 April 2007 (UTC)


—The preceding unsigned comment was added by Kmhkmh (talkcontribs) 12:10, 17 April 2007 (UTC).

There might... -- Rmrfstar 00:05, 27 March 2006 (UTC)
The general form of a divisibility test is this. If x is not a prime power, then it's a product of prime powers a_1^{p_1} a_2^{p_2} ... and y is divisible by x if it is divisible by a_1^{p_1} and by a_2^{p_2} and so on. If x = 2^n or x = 5^n, then y is divisible by x if the last n digits of y are divisible by x. Otherwise, 10a + b is divisible by x if a + kb is divisible by x, where k is a number such that 10k -1 is divisible by x (ie the multiplicative inverse). k can be negative, which is often more convenient for keeping k small, and this works not just for prime powers but for any x not divisible by 2 or 5. Perhaps we should stop at 20 and then explain the general form in more detail? — ciphergoth 08:23, 27 March 2006 (UTC)
I support stopping at 20, except for notable or easy ones, like 25, 27, 32, and 37 (add 36, 49, 33). The rest can be an exercise for the reader :-) By the way, I'm hoping to make an easier to understand explanation soon. You can do it with algebra without using modular arithmetic. Walt 00:10, 29 May 2006 (UTC)

[edit] Text from Divisor

I'm storing the following here for integration with this article. It seems that if Divisibility Rule is a separate article, then this should not be there.


If an integer n is written in base b, and d is an integer with b ≡ 1 (mod d), then n is divisible by d if and only if the sum of its digits is divisible by d. The rules for d=3 and d=9 given above are special cases of this result (b=10).

We can generalize this method even further to find how to check divisibility of any integer in any base by any other (smaller integer). Let us say that we want to determine if d | a in base b. Then we first find a pair of integers (n, k) that solves the congruence bnk (mod d). Now rather than summing the digits, we take a (which has m digits) and multiply the first m-n digits by k and add the product to the last (or more precisely, smallest) k digits and repeat if necessary. If the result is a multiple of d then the original number is divisible by d.

A few examples will help demonstrate this. Since 103 ≡ 1 (mod 37) then the number 1523836638 gives 1+523+836+638 = 1998 which gives 1×1 + 998 = 999. We know that 999 is divisible by 37 because of the above congruence. Again, 102 ≡ 2 (mod 7) so 43106 gives 431×2 + 06 = 868 which gives 8×2+68 = 84 which is easily noted as being a multiple of 7.

Note that there is no unique triple (n, k, d) since for example 10 ≡ 3 (mod 7) so we could also have done 4310×3 + 6 = 12936 and 1293×3 + 6 = 3885 and 388×3 + 5 = 1169 and 116×3 + 9 = 357 and 35×3 + 7 = 112 and 11×3 + 2 = 35 and 3×3 + 5 = 14 and 1×3 + 4 = 7. Clearly this is not always efficient but note that each number in this series, 43106, 12936, 3885, 1169, 357, 112, 35, 14, 7 is a multiple of 7 and many series could contain trivially identifiable multiples. This method is not necessarily useful for some numbers (for example 104 ≡ 4 (mod 17) is the first n where k < 10) but lends itself to fast calculations in other cases where n and k are relatively small.

Walt 00:18, 29 May 2006 (UTC)

[edit] Revamping the page

I'm trying to make the page easier for someone who doesn't know a lot of math, and is looking for the rules to actually use them. The rest of us I'm sure can cope by looking at the proofs. I've removed a few rules and added some I think are easier, while also cleaning up (IMHO) the entries.

I hope anyone who doesn't like these changes will discuss it here first so we can satisfy everyone.

Walt 23:57, 29 May 2006 (UTC)

I love 'em. -- Rmrfstar 23:51, 14 June 2006 (UTC)
Thanks. Always nice to get some feedback (esp. positive) -- Walt 12:58, 15 June 2006 (UTC)

[edit] Cut text - trial divisors

I cut the following: the point of this page is that you can determine divisibility without determining the quotient. This may belong on a page of how to do mental math instead.


Proof using trial divisors For 21:

Choose a number n such that n>0. (2n)*10+n=21n, 21n/21=n
For example, 53: 53*2=106*10=1060+53=1113. 1113/21=53
You can also do this logically, noting that 20n+n=21n. That is to say, if 8 is multiplied by 20, the result is 160. If 8 is added to that product, the result is 168, which is divisible by 21, obviously. This stems from the known fact that multiplication is a simplified form of addition.

This rule for 21 will also apply for all numbers 10n+1 where n is an integer. That is to say, for instance, in order to test to 31, multiply the number by 3, then by 10, and add the number to itself. Thus, if a number can be broken up into two numbers and 1/3 of the first number is equal to the second number, then it is divisible by 31. E.g., 713 = 690 + 23. 69/3 = 23, thus 713 is divisible by 31.

Walt 01:46, 2 June 2006 (UTC)

[edit] overall form

I feel as if this article can not be made to fit the format of a traditional article... perhaps it should be made into an official list? -- Rmrfstar 03:51, 4 January 2007 (UTC)

[edit] Confusing Divisibility Rule for 17

216.167.135.24 20:46, 20 February 2007 (UTC) From: Danny (ooiyq2@yahoo.com)216.167.135.24 20:46, 20 February 2007 (UTC)


In the section entitled "2 through 20"... a chart lists various divisibility rules (for these 19 whole-numbers-- from 2 through 20)... I have been able to understand (& gratefully utilize) all of these rules... all, EXCEPT FOR ONE-- that one being: the second rule listed for the number 17.


The description of the "Divisibility Condition"... does NOT seem to match the given "Example". The named "Divisibility Condition" is described (with ambiguous wording) as follows: "Alternatively subtract and add blocks of two digits from the end, doubling the last block and halving the result of the operation, rounding any decimal end result as necessary."


Does this mean "doubling the last block" of those 2-digit blocks-of-digits which a person (in reverse order) does "[a]lternatively subtract and add"... or does this mean "doubling the last block" of the original number? Oddly, in the given "Example", though, every "block of two digits" EXCEPT FOR "the last block" of the original number... are ones which the article's readers can witness the said "Example" to be "doubling". Perhaps, the contributor had intended to say "doubling each 2-digit block-of-digits OTHER THAN the last block". The reader is left to guess.


Another wording leaves uncertainty, as well. Specifically, when does "halving the result of the operation" occur? To do so, immediately after doubling any 2-digit block-of-digits... would leave the same 2-digit block-of-digits which had existed prior to the original doubling (making that doubling-- be a pointless waste-of-time).


If, instead, the doubling should occur AFTER a doubled 2-digit block-of-digits has been subtracted from, or added to, another 2-digit block-of-digits... then, should that "halving" occur after EACH subtraction, or addition, of a (possibly, doubled) 2-digit block-of-digits... ONLY after the FIRST subtraction of a (possibly, doubled) 2-digit block-of-digits... or ONLY after ALL of the (possibly, doubled) 2-digit blocks-of-digits have been subtracted, or added?


Looking (for insight into these matters) to the provided "Example"... provides no clear answers... and, instead, only creates more questions.


The "Example" (for 209,865-- which commas divide... into each, said block of 2 digits-- as "20,98,65"), however, does not double the last block (i.e., of 65); but rather, that said "Example" doubles both the middle block (of 98... which becomes "(98x2)")... as well as the first block (i.e., of 20... becoming "40"). Plus, the "Example" does NOT remove the resulting decimal... by "rounding" (but rather, through multiplication by 10).


The said "Example" (which appears as: "20,98,65: (65 - (98x2)) : 2 + 40 = - 25.5 = 255 = 15x17")... CAN work, however, when expressed as follows: "209,865: ( [65 - (98•2) ] / 2) + (2•20) = [ (65 - 196) / 2] + 40 = (-131 / 2) + 40 = -65.5 + 40 = -25.5"... and "-25.5•10 = -255 = -15•17".


Despite my best efforts, though, NONE of my attempts to apply this divisibility rule to larger multiples of 17 (ones with more digits than the given "Example") have ever been successful. Please, either help me to understand this Divisibility Rule... or send this note to the contributor (of the said Divisibility Rule)... so that I'll learn how to apply the Divisibility Condition to this sizable multiple of 17: 9,349,990,820,016,829,983 (a whole-number which is the product of the following prime factors: 3 • 3 • 3 • 3 • 7 • 11 • 13 • 13 • 13 • 17 • 37 • 43 • 557 • 45,293).


Thanking you, in advance, for your prompt reply,

Danny

ooiyq2@yahoo.com


Hello Danny. I read a book, Vedic Mathematics that gives a general method for divisibility called osculation. It follows the vedic ideal of one-line notation. It requires no division, just multiplication and addition. Larry R. Holmgren March 4, 2007.

Example one: Is 209,865 divisible by 17? First convert the divisor 17 to the nines family. 17x7=119. Add one, drop the zero. The 12 is the Ekādhika, the multiplier. Start on the right, one digit at-a-time, moving to the left. If you finish with 17 (or a multiple of 17) or zero, then the number is divisible by 17, otherwise it is not divisible by 17. Ten multiples of 17: 17, 34, 51, 68, 85, 102, 119, 136, 153, 170.

The process: Multiply the first digit on the right by 12. Add the product to the next digit to the left. Write the result below that next digit. Multiply its units digit of the result by 12 and add that product to the other digits in the result and add to the next digit to the left. Set down this result below that digit. Repeat the process to the end on the left. Mental math: 5x12=60. 60+6=66. 6x12=72. 72+6+8=86. 6x12=72. 72+8+9=89. 9x12=108. 108+8+0=116. 6x12=72. 72+11+2=85.

2   0    9   8   6   5  
85  116  89  86  66 
YES. 

Example two: Is 9,349,990,820,016,829,983 divisible by 17? As above for a divisor of 17 the Ekādhika (multiplier) is 12. 18 steps of mental math: 3x12+8=44. 4x12+4+9=61. 1x12+6+9=27. 7x12+2+2=88. 8x12+8+8=112. 2x12+11+6=41. 1x12+4+1=17. 7x12+1+0=85. 5x12+8+0=68. 8x12+6+2=104. 4x12+10+8=66. 6x12+6+0=78. 8x12+7+9=112. 2x12+11+9=44. 4x12+4+9=61. 1x12+6+4=24. 4x12+2+3=53. 3x12+5+9=50.

9  3  4  9  9  9   0  8  2   0  0  1  6  8   2  9  9  8  3
50 53 24 61 44 112 78 66 104 68 85 17 41 112 88 27 61 44  
NO.

Larry R. Holmgren 11:23, 3 March 2007 (UTC)

Danny Please check the prime factorization of that 19-digit number again. 9,349,990,820,016,829,983 =? 3 • 3 • 3 • 3 • 7 • 11 • 13 • 13 • 13 • 17 • 37 • 43 • 557 • 45,293 ? I checked 9 by casting out nines. OK

Larry R. Holmgren 18:36, 3 March 2007 (UTC)

**********************************************************************************************

Hello, Larry.


Thank you for posting your reply.


Although I do appreciate the fact that you did provide a response to my inquiry... I am afraid that your analysis has something amiss about it. Using long-division, I have been able to verify my factoring. To start with, 9,349,990,820,016,829,983 (in fact) IS evenly divisible by 17. The quotient that results is 549,999,460,000,989,999. When 549,999,460,000,989,999 becomes the dividend... with a divisor of 45,293... the next quotient (again, using long-division) is 12,143,144,856,843. Then, next, when 12,143,144,856,843 is divided by 204,709,197 (i.e., the product of... 3 • 7 • 11 • 37 • 43 • 557)... the next quotient (again, using long-division) is 59,319. Finally, when a person divides 59,319 by 4,563 (i.e., the product of... 3 • 3 • 3 • 13 • 13)... the next quotient (again, via long-division) is 13.


Although, initially, I did have some difficulty in grasping the mechanics of these fascinating principles of Vedic Mathematics... eventually, I did comprehend them. You have taught me an invaluable lesson... for which I am very grateful; however, I do believe that I have identified the reason for you reaching the mistaken conclusion of the number not being evenly divisible by 17 (when, in fact, it is). Near the end of the process, you stated (perhaps, from a typographical error)... that (1 • 12) + 6 + 4 = 24. In fact, however, (1 • 12) + 6 + 4 = 22 (instead of 24). This tiny little glitch... led to two subsequent mistakes. Had this minor slip not happened... no doubt, you would have followed the result of 22... with the next two statements: (2 • 12) + 2 + 3 = 29 and (9 • 12) + 2 + 9 = 119... thereby, verifying the divisibility.


Even though I am glad to have learned this new technique (at least, that is, new to me)... the divisibility test (or rule)-- which I had referenced in my original inquiry... still, remains a mystery to me. Anyone, at all... please, post information about how to apply (to 9,349,990,820,016,829,983)... the divisibility rule (for 17) which says to: "Alternatively subtract and add blocks of two digits from the end, doubling the last block and halving the result of the operation, rounding any decimal end result as necessary."


Thanking you, in advance, for your prompt reply,


Danny

ooiyq2@yahoo.com



[edit] More on General Divisibility Rules

Interesting work there... though I warn you that yellow on white is barely legible. I certainly can't read it.

--Changed the fonts and presentation to make it readable. 2007.06.08

I think another component to general divisibility rules deserves some discussion. In particular, alternate bases than '10'. E.g. if a number is represented in binary or hexadecimal. For young programmers working on big-number representations and optimizations of associated functions (like 'isprime?') that would be quite a boon. Not that it hasn't been solved in the open-source world already... but a decent explanation would be nice.


Thank a lot for your contribution, really I don't know nothing about isprime, if you know about this we can collaborate in this, I am murad aldamen, who made this rule...

no problem for the font Donquimico 01:55, 9 June 2007 (UTC)

Danny, perhaps the algorithm for divisibility by 17 is the negative osculation algorithm, Vedic Mathematics. I can look it up later. Divisor, D=17. 17x7=119. Hence, the positive osculator, P = 12. One nine means use one digit at-a-time. Next, generate a double nine ending. 17x47=799. Hence, P=8, taking 2-digits at-a-time. And the negative osculator (multiplier) is 4? but alternating + and - signs, osculating right to left. If we let the negative osculator = Q, then P+Q=D. There is both positive and negative osculation as well as digit-wise, whole number, complex, and multiplex osculation.Larry R. Holmgren 17:36, 22 June 2007 (UTC)

I am the man 2859 03:22, 24 October 2007 (UTC) i still don't get how you do divisibility rule 11!

it is easily, see general divisibility test,... for examples: 121=120+1--> 12-1=11; another example, 143,...140+3=>14-3=11;...etc Donquimico —Preceding unsigned comment added by 81.203.145.59 (talk) 00:44, 2 March 2008 (UTC)

[edit] General rule

Thanks for working on this topic! I'd like to add a suggestion about adding some wording regarding a general rule, especially if you plan to cap the divisors at 50. I see that you've noted on the table for 7 that 'Double the number with the last two digits removed and add the last two digits' works. Let's extend that a little, assuming 'b' equals the last two digits and 'a' everything else.

If x is a coefficient equal to 100 - (the greatest multiple of the divisor less than 100), then divisor d is evenly divisible if xa+b is. For 7 that is obviously the 2a+b that you mention. For 19 it would be 5a+b, etc. For some numbers like 17, it's more trouble than it's worth (see below), but there are clearly some numbers where this is handy. If b is extended to three digits, then x = 1000 - (greatest multiple <1000), etc and the same formula works.

Or, you can subtract using the test xa-b, where x is a coefficient equal to (the smallest multiple of the divisor greater than 100) - 100. So for 17 the formula 2a-b is preferable to 15a+b.

Hope this is helpful. I've been looking around the web to see if anyone has a 'unified theory' that laypeople like myself would understand, and perhaps it's out there. Since I'm not planning to publish my childhood musings, here it is if you can use it.

Best of luck, George Wunder gfwunder @ gmail —Preceding unsigned comment added by 69.115.168.129 (talk) 17:55, 28 May 2008 (UTC)