Phil,
Perhaps your "ambiguity" is that the ordinary long division algorithm
provides a reasonable "divisibility rule" for ALL numbers. But assume for a
moment that by "divisibility rule" we mean an algorithm that uses only
adding, subtracting, and multiplying, (not "how many times does 7 go into
58") and tests the divisibility of a number N with on the order of log N
steps. For example, we want to test whether 29376 is divisible by 7 using
only adding, subtracting, and multiplying using an algorithm with no more
than O(log 29376) steps.
In the domain of whole numbers you can derive "divisibility rules" for any
number you desire. But as others have already warned, the rules are
typically as messy as long division would be. But in case anyone has an
interest in how such rules can be derived, here is the derivation for
"divisibility by 7": (If you have no such interest, NOW would be a good
time to hit the delete key!)
The key to divisibility is "remainder", or "modular" arithmetic and the
structure of base-10 notation.
So replace the question, "Is 29376 divisible by 7?" with the question
"Does 29376=0 (mod 7)?"
And remember that 29376 (base-10) is actually
2*10^4 + 9*10^3 + 3*10^2 + 7*10^1 + 6*10^0.
Thus we need to determine the remainders, modulo 7, of various powers of 10.
10^0 = 1 (mod 7)
10^1 = 1*10 = 10 = 3 (mod 7)
10^2 = 3*10 = 30 = 2 (mod 7)
10^3 = 2*10 = 20 = 6 = -1 (mod 7)
10^4 = 6*10 = 60 = 4 = -3 (mod 7)
10^5 = 4*10 = 40 = 5 = -2 (mod 7)
10^6 = 5*10 = 50 = 1 (mod 7)
and clearly this cycle will repeat.
Then, to check if 29376=0 (mod 7), we work from right to left, and multiply
the 6 by 1,
the 7 by 3,
the 3 by 2,
the 9 by -1,
the 2 by -3,
and add these products together. This sum of 18 will be equivalent, modulo
7, to 29376. In fact, as when "casting out nines", this process may be
repeated on the number 18: working from right to left, we multiply
the 8 by 1,
the 1 by 3,
and add these products together. This sum of 11 will be equivalent, modulo
7, to both 18 and 29376. One more time, working from right to left, multiply
the 1 by 1,
the 1 by 3,
and add these products together. Now we see that
29376 = 18 = 11 = 4 (modulo 7)
so that 29376 divided by 7 gives a remainder of 4.
As another example, we test 36881194 for divisibility by 7.
We work from right to left, multiplying:
the 4 by 1,
the 9 by 3,
the 1 by 2,
the 1 by -1,
the 8 by -3,
the 8 by -2,
the 6 by 1,
the 3 by 3
and adding the products together, giving a sum of 7. This work shows that
36881194 = 7 = 0 (mod 7). Thus 36881194 is divisible by 7.
In the same fashion, divisibility rules can be derived for any whole number
whatsoever. However, unless the powers of 10 give a cycle of remainders
that 1) is short and 2) uses small positive and negative numbers, the
"divisibility rule" that you obtain will be hard to remember, and most
people would prefer our standard long division algorithm.
***Why is it that I can remember number theory like this that I learned 15
years ago and never used, but my students can't remember math they learned
last semester?
***For that matter, why can't I remember a student's name the day after I
learn it? :)
Kevin Broussard broussard@siskiyous.edu
College of the Siskiyous
800 College Avenue
Weed, CA 96094
****************************************************************************
* To post to the list: email mathedcc@archives.math.utk.edu *
* To unsubscribe, send mail to: majordomo@archives.math.utk.edu *
* In the mail message, enter ONLY the words: unsubscribe mathedcc *
* Words in the Subject: line are NOT processed! *
* Archives at http://archives.math.utk.edu/hypermail/mathedcc/ *
****************************************************************************