Rule of division by 23.


by MathematicalPhysicist
Tags: division, rule
MathematicalPhysicist
MathematicalPhysicist is offline
#1
Dec22-08, 09:06 AM
P: 3,176
What is the rule of division by 23?

Thanks in advance.
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
tiny-tim
tiny-tim is offline
#2
Dec22-08, 11:57 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by loop quantum gravity View Post
What is the rule of division by 23?

Thanks in advance.
Do you mean this?
HallsofIvy
HallsofIvy is offline
#3
Dec22-08, 01:26 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,894
Nice link, tiny tim.

MathematicalPhysicist
MathematicalPhysicist is offline
#4
Dec22-08, 01:55 PM
P: 3,176

Rule of division by 23.


Well another question of mine is how do you prove these division rules, do we know for every prime number the rule of division, or not?

Obviously, you need some trial and error but afterwards you need to prove it.

For example I am now rechecking the law of division by 3, and I know I should look at expansion in basis ten, i.e if [tex]a_m a_{m-1}.....a_{1}=3n[/tex] where a_m,a_m-1,....,a_1 are the digits of the number, [tex]\sum_{k=0}^{m}a_{k}10^k=3n[/tex], I need to prove that a_1+....+a_m is divisible by 3, any pointers?

Thanks in advance.
robert Ihnot
robert Ihnot is offline
#5
Dec22-08, 03:47 PM
PF Gold
P: 1,059
[tex]\sum_{k=0}^{m}a_{k}10^k=3n[/tex]

Since 10 ==1 Mod3, so are all its powers.
tiny-tim
tiny-tim is offline
#6
Dec22-08, 06:36 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by loop quantum gravity View Post
Well another question of mine is how do you prove these division rules, do we know for every prime number the rule of division, or not?
Hi loop quantum gravity !

I don't think there's a general rule

you just have to find a suitable multiple of the prime that ends in 9 or 1

for 23, it's 69 (= 3 x 23), = 70 - 1

so you add the unit times 70 to the tens and upward.

(if 23 | 10a + b, then also 23 | 10a + 70b)
CRGreathouse
CRGreathouse is offline
#7
Dec22-08, 06:41 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by loop quantum gravity View Post
Well another question of mine is how do you prove these division rules, do we know for every prime number the rule of division, or not?
Yes, but most are dumb like those for 7 and 23. Here's a link to some for the first thousand primes:
http://front.math.ucdavis.edu/0001.5012
robert Ihnot
robert Ihnot is offline
#8
Dec22-08, 08:53 PM
PF Gold
P: 1,059
GFGreathouse: Yes, but most are dumb like those for 7 and 23. Here's a link to some for the first thousand primes:
http://front.math.ucdavis.edu/0001.5012

However, they use the minus numbers, and for 23 that's 16. However, sometimes, it is easier to use the positive numbers that you add on, and that's 23-16 = 7. (I don't see that they made that especially clear, though tiny-tim had already done that for 23.)
MathematicalPhysicist
MathematicalPhysicist is offline
#9
Dec22-08, 10:57 PM
P: 3,176
Quote Quote by robert Ihnot View Post
[tex]\sum_{k=0}^{m}a_{k}10^k=3n[/tex]

Since 10 ==1 Mod3, so are all its powers.
I'm not sure I understand, I need to prove that it's divisible iff [tex]a_0+...+a_m[/tex] is a multiple of 3.
What does the fact that the residue of 10 by 3 is 1 helps me here?
tiny-tim
tiny-tim is offline
#10
Dec23-08, 02:58 AM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by loop quantum gravity View Post
I'm not sure I understand, I need to prove that it's divisible iff [tex]a_0+...+a_m[/tex] is a multiple of 3.
What does the fact that the residue of 10 by 3 is 1 helps me here?
Because if a = b = 1 (mod3), then ab = 1 (mod 3)

so 10n = 1 (mod3),

and ∑ an10n = ∑ an (mod3)
MathematicalPhysicist
MathematicalPhysicist is offline
#11
Dec23-08, 07:01 AM
P: 3,176
Quote Quote by tiny-tim View Post
Because if a = b = 1 (mod3), then ab = 1 (mod 3)

so 10n = 1 (mod3),

and ∑ an10n = ∑ an (mod3)
I figured it out eventually for both 3 and 5, the next task of mine is to prove it for 7, wish me luck. (-:

Cheers.
CRGreathouse
CRGreathouse is offline
#12
Dec23-08, 12:45 PM
Sci Advisor
HW Helper
P: 3,680
So on the subject of division rules:
It's clear that there are different sorts of divisibility rules here.
  • Some, like those for 2 and 5, allow testing a huge number in one step -- they just look at a fixed number of digits, one in these cases.
  • Others, like those for 3 and 9, reduce testing the number to testing a number a fraction of its size. In particular, each application of the rule reduces the number logarithmically: 123456789 is divisible by 3 iff 1+2+3+4+5+6+7+8+9 = 45 is.
  • Finally, some rules reduce the size of the number by only a fixed number of digits, like the tests for 7 and 23.

It's clear that any number of the form 2^m * 5^n has a test of the first sort. This is because base 10 factors as 2 * 5 so only the last max(m, n) digits need be considered.

It's clear that numbers n appearing in the factorization of 9, 99, 999, ... have tests of the second sort, since 10^k = 1 (mod n), and so digits can be added in groups of k. So 11 has a divisibility test based on adding digits in pairs, for example.

Any prime not in the factorization of 10 has a test of the third form.

My question: Are there other kinds of tests than those listed here (or equivalent to these)?
jambaugh
jambaugh is offline
#13
Dec23-08, 03:16 PM
Sci Advisor
PF Gold
jambaugh's Avatar
P: 1,767
If you're looking at a last digit rule you need only consider:

If (p,10)=1 then
[tex] n = 10m + r = ap \equiv m \mp kr =bp[/tex]
where k comes from a two digit multiple of p which is one away from a multiple of 10.
[tex]sp = 10k \pm 1[/tex]

[tex] 10bp = 10m \mp 10k r = 10m+ r \mp (10k\pm 1)r = n \mp (10k\pm 1)r = n \mp sbp[/tex]
Thus
[tex] n = 10bp \pm sbp[/tex]

You could also generate rules from multiples of p more than one away from a multiple of 10 but these would require you multiply the remaining digits of the number n by that number which is harder.

You can work similarly with the last two digits working with 3 digit multiples of p and so on.

Examples for multiples of 7:

Example: 3x7 = 21 = 2x10 + 1. Double the last digit and subtract from remaining.
Example: 7x7 = 49 = 5x10 - 1. Multiply last digit by 5 and add.

1792 --> 179 + 10 = 189 --> 18+45 = 63 --> 6+21=28 --> 2+40 = 42 --> 4+10 = 14--> 1+20 = 21 --> 2+5=7.

Higher order examples:
For multiples of 11: 9x11 = 99=1x100 - 1. So multiply last two digits by 1 and add.
For multiples of 211: 9x211 = 1899 = 19x100-1. So multiply last 2 digits by 19 and add.
CRGreathouse
CRGreathouse is offline
#14
Dec23-08, 05:04 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by jambaugh View Post
If you're looking at a last digit rule you need only consider:

If (p,10)=1 then
[tex] n = 10m + r = ap \equiv m \mp kr =bp[/tex]
where k comes from a two digit multiple of p which is one away from a multiple of 10.
[tex]sp = 10k \pm 1[/tex]

[tex] 10bp = 10m \mp 10k r = 10m+ r \mp (10k\pm 1)r = n \mp (10k\pm 1)r = n \mp sbp[/tex]
Thus
[tex] n = 10bp \pm sbp[/tex]
OK, that's the third kind I mentioned: a rule to shorten the number by one.

Quote Quote by jambaugh View Post
You could also generate rules from multiples of p more than one away from a multiple of 10 but these would require you multiply the remaining digits of the number n by that number which is harder.
Good point. I'm not sure that those sorts of rules would be practical compared to long division,though.
tiny-tim
tiny-tim is offline
#15
Dec23-08, 05:26 PM
Sci Advisor
HW Helper
Thanks
tiny-tim's Avatar
P: 26,167
Quote Quote by CRGreathouse View Post
It's clear that numbers n appearing in the factorization of 9, 99, 999, ... have tests of the second sort, since 10^k = 1 (mod n), and so digits can be added in groups of k. So 11 has a divisibility test based on adding digits in pairs, for example.

My question: Are there other kinds of tests than those listed here (or equivalent to these)?
Hi CRGreathouse!

Also numbers n appearing in the factorization of 11, 101, 1001,

for example 1001 = 7.11.13, and to check whether a large number is divisible by each of those numbers, partition it into groups of three digits, and add them.
jambaugh
jambaugh is offline
#16
Dec23-08, 05:48 PM
Sci Advisor
PF Gold
jambaugh's Avatar
P: 1,767
Quote Quote by CRGreathouse View Post
[...]
Good point. I'm not sure that those sorts of rules would be practical compared to long division,though.
Oh! You want practical!

Well if it's simply a matter of doubling and you're good at doubling in your head then it isn't so bad. Except that since 2 divides 10 such a rule will have an equivalent half rule since you're choosing an even multiple of the prime. Let's say you're a wiz at tripling...

Example:

Divisible by 7? 1x7 = 7 = 1x10-3, so add the last digit to triple the remaining...

777 --> 3x77 + 7 = 231+7=238--> 3x23+8=69+8=77-->3x7+7=28 --> 6+8=14-->3+4=7.

Not too bad but as you say both less practical and there's an easier one. But that's the mechanics of how it works.

Note also the add all digits for 3 and 9 come from the same type rule applied recursively.

Divisible by 3 or 9? 3x3= 1x9 = 1x10 - 1 so add 1 times last digit to remainder... apply recursively and its the same as adding all digits.

Note 9 is composite but these rules should work for composites provided they're mutually prime to 10.

E.g. divisable by 33? 3x33 = 99 = 100-1. Add last two digits to remaining...

50886-> 508+86=594->5 + 94 = 99 check!

Easier by stages to check for 3 and 11 separately but quicker to do both at once (maybe).
CRGreathouse
CRGreathouse is offline
#17
Dec23-08, 06:36 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by jambaugh View Post
Oh! You want practical!
Actually, not really. I just thought the lack of practicality was worth mentioning.

For example, one borderline-practical test for divisibility by 7 would be to add up a number by groups of 6:

111,222,333,444,555,666,777,888,999 is divisible by 7 iff 111+222333+444555+666777+888999 = 2222775 is, and 2,222,775 is divisible by 7 iff 2+222775 = 222,777 is. Of course to go further you need trial division (or the standard 'shorten by 1 digit' rule).

But the analogue for 17 (summing digits in groups of 16) is seldom, if ever, worthwhile, and I can't imagine anyone working their way through that rule for 59.

I'm more interested in seeing where the rules come from. So far they come from the factorization of
* n^a, by looking at the last a digits
* n^a - 1, by summing in groups of a digits
* n^a +/- n^b, by (alternate) summing
MathematicalPhysicist
MathematicalPhysicist is offline
#18
Jan23-09, 12:14 AM
P: 3,176
Ok, Iv'e come to a bit difficulty here with 7.
I mean if I write down:
[tex]a_0+10a_1+...+10^n a_n=7m[/tex]
then the rule states that:
[tex]7m-2a_0+a_1=-a_0+11a_1+...+10^n a_n[/tex]
is divisble by 7, but I don't see how this is true, it means that a_1-2a_0 should be divisible by 7.
for example 35=5*7 so the rule states that 35-5*2+3=28, and indeed 3-10=-7, but here is where I am stuck, I don't see how do you prove it, anyone?


Register to reply

Related Discussions
Synthetic division or Long division of polynomials? General Math 6
GPA of Upper Division & Lower Division courses and M.S degree Academic Guidance 1
Chain rule in division rule Calculus & Beyond Homework 6
Division with variables (I think I'd call this double division) Precalculus Mathematics Homework 5
Quotient rule for derivatives (algebraic division help?) General Math 3