Talk:Divisibility rule

From Wikipedia, the free encyclopedia

Divisibility rule is a former good article candidate. There are suggestions below for which areas need improvement to satisfy the good article criteria. Once the objections are addressed, the article can be renominated as a good article. If you disagree with the objections, you can seek a review. Date of review: No date specified. Please edit template call function as follows: {{FailedGA|insert date in any format here}}

Contents 1 Good Article nomination has failed 2 Split from Divisor topic 3 Proofs 4 53 5 Text from Divisor 6 Revamping the page 7 Cut text - trial divisors

[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] 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)

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 bⁿ ≡ k (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 10³ ≡ 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, 10² ≡ 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 10⁴ ≡ 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)