6 ms·
Test for Divisibility by 13
- drfuchs 6y agoMy preferred way to test divisibility by 13: Take the number, cross off the one's digit, but multiply that digit by 9, and take the product and subtract it from the modified original number. Repeat until you only have a digit or two, and what's left is a multiple of 13 iff the original number was. Clearer as an example: Is 4173 divisible by 13? First iteration: 417 - (3 x 9) = 390. Second: 39 - (0 x 9) = 39. And 39 is divisible by 13, so 4173 is. (No worries if the last subtraction gives a negative result; same rule applies.) To test for divisibility by 7, do exactly the same thing, but multiply the one's digit by 2 instead of 9. For 17, use 5. For 11, use 1. I learned the divisible-by-7 trick from a book when I was a kid, but didn't figure out why it works, and how to generalize it, until I was embarrassingly adult. Left as an exercise for the reader.
- sverona 6y agoROT13: Xvyyvat gur ynfg qvtvg naq fhogenpgvat gjvpr gur ynfg qvtvg sebz jung'f yrsg vf whfg fhogenpgvat n zhygvcyr bs gjraglbar naq qvivqvat ol gra.
- drfuchs 6y agoWell said!
- dmurray 6y agoIt's obvious if you look at the version with 11 first. I find the alternating digit sum method is easier to use for 11. They're competely equivalent, but your method makes it seem like you need to remember more state. For example, to test 678101 for divisiblity by 11 you'd go "678101, 67809, 6771, 676, 61, nope". With the alternating digits method you go "1, 1, 2, -6, 1, -5, nope" only dealing with one-digit numbers at every step. Maybe with practice you learn to ignore the leading digits until you need them.
- eps 6y agoFor 11 the even faster method is to just do this: 678101 -> 6-7+8-1+0-1 = 5 -> no bueno 874632 -> 8-7+4-6+3-2 = 0 -> divides by 11 The exact same idea, but even less "state" needed as you put it.
- dmurray 6y agoThink you're doing the exact same as me but I started from the right. 1-0+1-7+8-6. This way you end up with the remainder mod 11, if you start from the left you sometimes need to flip the sign at the end.
- madcaptenor 6y agoWho wants to multiply by 9, though? The version of the 13 test I've seen has you multiply by 4 and add instead: 4173 -> 417 + (3 x 4) = 429 -> 42 + (9 x 4) = 78, which is divisible by 13, so 4173 is. Of course, these two tests work for the same reason. You're saying 10a + b is divisible by 13 iff a - 9b is, I'm saying 10a + b is divisible by 13 iff a + 4b is, and those differ by 13b.
- michaericalribo 6y agoBut multiplying by 9 is so easy! You can check you’re right if (a) the first digit of the result is 1 less than the number you started with, and (b) the digits sum to 9
- rmetzler 6y agoThat’s how I taught my daughter.
- vaccinator 6y agobut that only works up to 10.. my method works for any number, and you could adapt it for x11... see below
- alisonkisk 6y agoLucky for us, all digits are less than 10.
- vaccinator 6y agoWhat is 23 x 9 with that trick?
- cipherzero 6y agoJust going off the trick above would t it just be: 23 x 10 - 23 = 230 - 23 = 207... I guess I’m confused what point you’re making?
- michaelmior 6y agoThis brings back memories from my abstract algebra class in college when we had to derive similar rules. Of course I've completely forgotten how most of the theory works now.
- dragosmocrii 6y agoCrazy how we forget the things we don't use regularly, eh? I used to love calculus in school, but now I doubt I remember but the basics of vasics
- fairity 6y agoInteresting but what’s the reasoning to commit facts like this to memory when I have a calculator one swipe away?
- zamadatix 6y agoThe same type of reasoning that explains why it makes sense to create a calculator app instead of use one i.e. sometimes it's not the answer that matters rather the skills you learned to come up with the answer that you can now take with you to unsolved problems.
- taeric 6y agoI think it is slightly different. Just rote memorization of the facts can be done, yes. However, these facts require a lot of mechanics of numbers to work. Such that the benefit is less from remembering the facts and more from working them. Is akin to knowing the idea of how to drive a stick shift, and knowing how to drive a stick shift.
- recursive 6y agoThat way other people can use it too.
- tonyedgecombe 6y agoFor the exam. After that most of us will quickly forget it.
- MauranKilom 6y agoBecause breaking out your calculator when you want to figure out whether you can divide 22 students evenly into groups of three is going to get you laughed at. Divisibility by 13 is of course not as useful/applicable as divisibility by three, but the question is then more nuanced: "Why should I memorize this particular divisibility trick?"
- throwaway2245 6y agoIf you know that house number 235 is on the odd side of the road, you've committed a divisibility fact to memory. This involves less memory than knowing how to use your calculator app to check.
- bkkaggle 6y agoThis is pretty interesting especially since I just finished an assignment a couple of days ago for my proofs course that was all about proving the divisibility of large integers and the sums of their digits. Modular arithmetic, pretty fun stuff even if i'm incredibly bad at it.
- deleted 6y ago[deleted]
- phs 6y agoA more formal treatment can be found in "Elementary Number Theory and its Applications", Kenneth H. Rosen, 3rd Ed, specifically Chapter 4, "Applications of Congruences". The 7 * 11 * 13 = 1001 development in particular appears just after example 4.4 and is then generalized to arbitrary bases by theorem 4.3. For example to divide by five in octal, do the alternating sum trick on digits grouped in pairs, because 5 divides 8^2+1. Though it quickly stops being useful for manual checks, Fermat's Little Theorem is a fun gizmo. It says for any prime `p` (say, 17) and base `a` not divisible by it (10), we have that `a^(p-1) % p == 1`. Put another way, so long as we meet the criteria (prime, doesn't divide base), we can form a divisibility test by summing blocks of `p-1` (16) digits and testing the result, just like the `3` case. Further, since `p-1` is even we can take the square root of both sides (`a^((p-1)/2) % p == +/-1`) and use either the sum or alternating sum tricks with blocks half that size, depending on the sign of the final `1`.
- _Microft 6y agoYou might also like weighted digit sums. I'll copy the example from german Wikipedia article [0] as you might generalize from that easier as when I would write it down in mathematical notation: Here are the weights for 7: 1 ≡ 1 (mod 7) 10 ≡ 3 (mod 7) 100 ≡ 2 (mod 7) 1000 ≡ −1 (mod 7) 10000 ≡ −3 (mod 7) 100000 ≡ −2 (mod 7) 1000000 ≡ 1 (mod 7) ... 10^n ≡ a_n (mod 7) Then multiply the weights with the digit on the respective position and sum up. Repeat if you like. If the resulting number is divisible by 7, you know that the initial number also was. Example: 853629: 8x (-2) + 5x (-3) + 3x (-1) + 6x 2 + 2x 3 + 9x 1 = -16-15-3+12+6+9 = -7, therefore 853629 is divisible by 7. [0] https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme https://de.wikipedia.org/wiki/Quersumme#Gewichtete_Quersumme
- tgv 6y agoInteresting. I'll translate this bit from the entry: One can also find periodical sequences for other natural numbers. E.g., * for 11, the sequence +1, -1, ... * for 13, the sequence 1, -3, -4, -1, 3, 4, ... For most divisors, it is not practical to test divisibility this way, as there are only few easily remembered weight sequences.
- deleted 6y ago[deleted]
- ddxxdd 6y agoI came in the comments section with the intent of asking HN about generalized divisibility rules for any number N with any base B. Looks like you provided the goods.
- _Microft 6y agoYou are welcome, I am glad I could help :)
- suyjuris 6y agoInstead of remembering the weighted sequence, you can also compute it implicitly as you go (when reading the number from left to right). Example: 8 ^ 8 (mod 7) is 1, remember that 85 ^ 1 · 10 (mod 7) is 3, and 3 + 5 (mod 7) is 1, remember that 853 ^ 1 · 10 + 3 (mod 7) is 6 8536 ^ 6 · 10 + 6 (mod 7) is 3 85362 ^ 3 · 10 + 2 (mod 7) is 4 853629 ^ 4 · 10 + 9 (mod 7) is 0 Hence 853629 (mod 7) = 0 and it is divisible by 7. The corresponding code would be def modulo(number, k): val = 0; for digit in str(number): val = (val * 10 + int(digit)) % k return val Of course, you can apply the modulo within the intermediate calculations as well, so instead of multiplying by 10 you can e.g. multiply by 3 = 10 (mod 7) instead. The key idea is that you can go from one weight to the next by multiplying with 10 (mod 7), so if you sum some weighted digits you can update all the weights at once with a simple multiplication. The advantage is that you only need a small amount of memory (a single number between 0 and 6), so this is a kind of general divisibility rule where you only have to do small calculations in your head. If I may digress a bit into automata theory, this means that you can construct a finite state automaton that determines whether a number is divisible by 7 (or any other constant) by reading its digits from left to right. Additionally, if a finite state automaton can do something reading from left to right, there is another automaton doing the same thing but reading from right to left. This means that there is also a 'simple' divisibility rule when starting with the least significant digit, though it may be a bit harder to find.
- ineedasername 6y agoEdit: Modified because the downvotes maybe didn't realize I am honestly asking a question here: Take the divisible by 3 rule: digits add up to a number divisible by 3, then the original number is divisible by 3. But 144 will get you 9. What in number theory tells you that 9 is divisible by 3?
- clort 6y agowhile (n > 9) n = sum_digits(n); return (n == 3 || n == 6 || n == 9);
- tgv 6y agoIsn't the answer as simple as: the definition of multiplication (or division)? I mean: you can apply that definition also to the original numbers; these are just tricks to make it easier/faster.
- jbrot 6y agoThese algorithms all reduce the division problem into some fixed range. For instance, in the case of 3, we are able to reduce the divisibility of an arbitrary integer by 3 into the divisibility of a single digit number by 3. In the 13 case described in the article, we reduce the problem to a 3 digit number. The base case can then just be a lookup table. As for how to generate the base table, recall that we say a divides n provided there exists some b such that ab = n. In this case we're talking about integers, although this is the definition for any ring. Therefore, proving 3 divides 9 is as simple as noting that 3 * 3 = 9, and likewise we can prove 3 divides 6 by noting that 3 * 2 is 6. Proving a lack of divisibilty is a little bit trickier. For this, you'll want to first prove the division algorithm which, in the case of the integers, says that for any two integers a and n, there exists unique integers b and r with abs(r) < abs(a) such that ab + r = n. Given this, we can then note that, for instance, 7 = 3 * 2 + 1. Therefore 7 cannot be divisible by 3 as that would imply there exists some other integer b such that 7 = 3 * b + 0 contradicting that the integers from the division algorithm are unique. You might then wonder: well, how do we know 3 * 2 is 6? Well, to stop these questions from recursing endlessly, we need to define the integers. One reasonable definition is "the initial element in the ring category" which gives us that the integers are a ring by definition. As such, we have axiomatically that there are integers 0 and 1, a commutative operation + with identity 0 that is closed under inverses, an associative operation * with identity 1, and that * distributes over +. If we then define 2 to be 1 + 1, 3 to be 1 + 1 + 1, and 6 to be 1 + 1 + 1 + 1 + 1 + 1, we can use distributivity to prove that 3 * 2 = 3 * (1 + 1) = (3 * 1) + (3 * 1) = 3 + 3 = 6.
- tjpnz 6y ago>A number is divisible by 2 if its last digit is divisible by 2. How does this work when the last digit is 0?
- MrXOR 6y agoWhy won't Wordfence let me to see this website with Tor browser?