Code: PU
P=100 (k=65=30 (mod 35) )
Formulae:
Number N is divisible by 35 iff 30*b+a = -5*b+a is divisible by 35
Example:
Number N = 98 76 54 32 15 = 28 6 19 32 15 =
-5( 28 6 19 32)+15 =
-5(-5( 28 6 19+32)+15 =
-5(-5(-5( 28 6+19)+32)+15 =
-5(-5(-5(-5*28+6)+19)+32)+15 =
-5(-5(-5* 6+19)+32)+15 =
-5(-5* 24+32)+15 =
-5* 17+15 = 0 (mod 35)
is divisible by 35.
Code: CR
P=70=7*10
Formulae:
Number N is divisible by 35 iff least significant digit is either 0 or 35
Example:
Number N = 8512160
[8 5 1 2 1 6 | 0] = [7 14 7 42 0 14 | 20] = 7*[1 2 1 6 0 2] 20
isn't divisible by 35
11/16/17
number 34
Code: PU
P=100 (k=66=32 (mod 34) )
Formulae:
Number N is divisible by 34 iff 32*b+a = -2*b+a is divisible by 34
Example:
Number N = 98 76 54 32 10 = 30 8 20 32 10 =
-2( 30 8 20 32)+10 =
-2(-2( 30 8 20+32)+10 =
-2(-2(-2( 30 8+20)+32)+10 =
-2(-2(-2(-2*30+8)+20)+32)+10 =
-2(-2(-2* 16+20)+32)+10 =
-2(-2* 22+32)+10 =
-2* 22+10 = 0 (mod 34)
is divisible by 34.
P=100 (k=66=32 (mod 34) )
Formulae:
Number N is divisible by 34 iff 32*b+a = -2*b+a is divisible by 34
Example:
Number N = 98 76 54 32 10 = 30 8 20 32 10 =
-2( 30 8 20 32)+10 =
-2(-2( 30 8 20+32)+10 =
-2(-2(-2( 30 8+20)+32)+10 =
-2(-2(-2(-2*30+8)+20)+32)+10 =
-2(-2(-2* 16+20)+32)+10 =
-2(-2* 22+32)+10 =
-2* 22+10 = 0 (mod 34)
is divisible by 34.
11/9/17
number 33
Code: PU
P=100 (k=67=1 (mod 33) )
Formulae:
Number N is divisible by 33 iff sum of digits is divisible by 33
Example:
Number N = 98 76 54 32 04 = 32 10 21 32 4 =
32+10+21+32+4 = 99 = 0 (mod 33)
is divisible by 33.
Code: SF 10*10-3*33=1
10(10b+a) = b+10a (mod 33)
Formulae:
Number N is divisible by 33 iff b+10a is divisible by 33
Example:
Number N = 68905
6890+10*5 = 6940
694+10*0 =694
69+10*4 = 109
10+10*9 = 100 = 3*33+1
isn't divisible by 33
Code: SF- 23*10-7*33=-1
23(10b+a) = -b+23a = -(b+10a) (mod 33)
It is the same as above.
P=100 (k=67=1 (mod 33) )
Formulae:
Number N is divisible by 33 iff sum of digits is divisible by 33
Example:
Number N = 98 76 54 32 04 = 32 10 21 32 4 =
32+10+21+32+4 = 99 = 0 (mod 33)
is divisible by 33.
Code: SF 10*10-3*33=1
10(10b+a) = b+10a (mod 33)
Formulae:
Number N is divisible by 33 iff b+10a is divisible by 33
Example:
Number N = 68905
6890+10*5 = 6940
694+10*0 =694
69+10*4 = 109
10+10*9 = 100 = 3*33+1
isn't divisible by 33
Code: SF- 23*10-7*33=-1
23(10b+a) = -b+23a = -(b+10a) (mod 33)
It is the same as above.
number 32
Code: PS P=100.000
b100000+a = 32*3125b+a = a
Formulae:
Number N is divisible by 32 iff least significant digit a is divisible by 32
Example:
Number N = 98476 51430 98756
98756 = 4*24689
Number N isn't divisible by 32
Code: PU
P=100 (k=68=4 (mod 32) )
Formulae:
Number N is divisible by 32 iff 4*b+a is divisible by 32
Example:
Number N = 98 76 54 32 00 = 2 12 22 0 0 =
4(2 12 22 0)+0 =
4(4(2 12 22+0)+0 =
4(4(4( 2 12+22)+0)+0 =
4(4(4(4* 2+12)+22)+0)+0 =
4(4(4* 20+22)+0)+0 =
4(4* 6+0)+0 =
4* 24+0 = 0 (mod 32)
is divisible by 32.
Code: CR
P=800 (k=100*8)
Formulae:
Number N is divisible by 32 iff remainder from division by 800 is divisible by 32
Example:
Number N = 84 56 21 34
Conversion to P=100*8
[84, 56, 21 | 34] = [80, 456, 16] | 534 = 8*[10, 57, 2] | 534
The number N has least significant digit 534 = 2*267, so N isn't divisible by 32
b100000+a = 32*3125b+a = a
Formulae:
Number N is divisible by 32 iff least significant digit a is divisible by 32
Example:
Number N = 98476 51430 98756
98756 = 4*24689
Number N isn't divisible by 32
Code: PU
P=100 (k=68=4 (mod 32) )
Formulae:
Number N is divisible by 32 iff 4*b+a is divisible by 32
Example:
Number N = 98 76 54 32 00 = 2 12 22 0 0 =
4(2 12 22 0)+0 =
4(4(2 12 22+0)+0 =
4(4(4( 2 12+22)+0)+0 =
4(4(4(4* 2+12)+22)+0)+0 =
4(4(4* 20+22)+0)+0 =
4(4* 6+0)+0 =
4* 24+0 = 0 (mod 32)
is divisible by 32.
Code: CR
P=800 (k=100*8)
Formulae:
Number N is divisible by 32 iff remainder from division by 800 is divisible by 32
Example:
Number N = 84 56 21 34
Conversion to P=100*8
[84, 56, 21 | 34] = [80, 456, 16] | 534 = 8*[10, 57, 2] | 534
The number N has least significant digit 534 = 2*267, so N isn't divisible by 32
10/31/17
number 31
Code: PU
P=100 (k=69=7 (mod 31) )
Formulae:
Number N is divisible by 31 iff 7*b+a is divisible by 31
Example:
Number N = 98 76 54 32 08 = 5 14 23 1 8 =
7( 5 14 23 1)+8 =
7(7(5 14 23+1)+8 =
7(7(7( 5 14+23)+1)+8 =
7(7(7(7* 5+14)+23)+1)+8 =
7(7(7* 18+23)+1)+8 =
7(7* 25+1)+8 =
7* 21+8 = 0 (mod 31)
is divisible by 31.
Code: SF 28*10-9*31=1
28(10b+a) = b+28a = b-3a (mod 31)
Formulae:
Number N is divisible by 31 iff b-3a is divisible by 31
Example:
Number N = 68931
6893-3*1 = 6890
689-3*0 =689
68-3*9 = 41
4-3*1 = 1
isn't divisible by 31
Code: SF- 3*10-1*31=-1
3(10b+a) = -b+3a = -(b-3a) (mod 31)
It is the same as above.
P=100 (k=69=7 (mod 31) )
Formulae:
Number N is divisible by 31 iff 7*b+a is divisible by 31
Example:
Number N = 98 76 54 32 08 = 5 14 23 1 8 =
7( 5 14 23 1)+8 =
7(7(5 14 23+1)+8 =
7(7(7( 5 14+23)+1)+8 =
7(7(7(7* 5+14)+23)+1)+8 =
7(7(7* 18+23)+1)+8 =
7(7* 25+1)+8 =
7* 21+8 = 0 (mod 31)
is divisible by 31.
Code: SF 28*10-9*31=1
28(10b+a) = b+28a = b-3a (mod 31)
Formulae:
Number N is divisible by 31 iff b-3a is divisible by 31
Example:
Number N = 68931
6893-3*1 = 6890
689-3*0 =689
68-3*9 = 41
4-3*1 = 1
isn't divisible by 31
Code: SF- 3*10-1*31=-1
3(10b+a) = -b+3a = -(b-3a) (mod 31)
It is the same as above.
number 30
Code: CR
P = 3*10
Formulae:
Number N is divisible by 30 iff least significant digit is 0
Example:
Convert decimal number N = 8512160 into base P = 3*10=30, first step is enough
[8 5 1 2 1 6 | 0] = [6 24 9 21 9 24 | 20] = 3*[2 8 3 7 3 8] 20
Number N isn't divisible by 30
Code: PU
P=100 (k=70=10 (mod 30) )
This case method doesn't work - the formulae wishes to check a number N:
Number N is divisible by 30 iff N = 10*b+a is divisible by 30
P = 3*10
Formulae:
Number N is divisible by 30 iff least significant digit is 0
Example:
Convert decimal number N = 8512160 into base P = 3*10=30, first step is enough
[8 5 1 2 1 6 | 0] = [6 24 9 21 9 24 | 20] = 3*[2 8 3 7 3 8] 20
Number N isn't divisible by 30
Code: PU
P=100 (k=70=10 (mod 30) )
This case method doesn't work - the formulae wishes to check a number N:
Number N is divisible by 30 iff N = 10*b+a is divisible by 30
10/23/17
number 29
Code: PU
P=100 (k=71=13 (mod 29) )
Formulae:
Number N is divisible by 29 iff 13*b+a is divisible by 29
Example:
Number N = 98 76 54 32 13 = 11 18 25 3 13 =
13( 11 18 25 3)+13 =
13(13(11 18 25+3)+13 =
13(13(13(11 18+25)+3)+13 =
13(13(13(11*17+18)+25)+3)+13 =
13(13(13* 2+25)+3)+13 =
13(13* 22+3)+13 =
13* 28+13 = 0 (mod 29)
is divisible by 29.
Code: SF 3*10-1*29=1
3(10b+a) = b+3a (mod 29)
Formulae:
Number N is divisible by 29 iff b+3a is divisible by 29
Example:
Number N = 68931
6893+3*1 = 6896
689+3*6 = 707
70+3*7 = 91
9+3*1 = 12
isn't divisible by 29
Code: SF- 26*10-9*29=-1
26(10b+a) = -b+26a = -(b+3a) (mod 29)
It is the same as above.
P=100 (k=71=13 (mod 29) )
Formulae:
Number N is divisible by 29 iff 13*b+a is divisible by 29
Example:
Number N = 98 76 54 32 13 = 11 18 25 3 13 =
13( 11 18 25 3)+13 =
13(13(11 18 25+3)+13 =
13(13(13(11 18+25)+3)+13 =
13(13(13(11*17+18)+25)+3)+13 =
13(13(13* 2+25)+3)+13 =
13(13* 22+3)+13 =
13* 28+13 = 0 (mod 29)
is divisible by 29.
Code: SF 3*10-1*29=1
3(10b+a) = b+3a (mod 29)
Formulae:
Number N is divisible by 29 iff b+3a is divisible by 29
Example:
Number N = 68931
6893+3*1 = 6896
689+3*6 = 707
70+3*7 = 91
9+3*1 = 12
isn't divisible by 29
Code: SF- 26*10-9*29=-1
26(10b+a) = -b+26a = -(b+3a) (mod 29)
It is the same as above.
10/13/17
number 28
Code: PU P=100 (k=72=16 (mod 28) )
Formulae:
Number N is divisible by 28 iff 16b+a = -12b+a is divisible by 28
Example:
Number N = 98 76 54 32 08 = 14 20 26 4 8 =
-12( 14 20 26 4)+8 =
-12(-12( 14 20 26+4)+8 =
-12(-12(-12( 14 20+26)+4)+8 =
-12(-12(-12(-12*14+20)+26)+4)+8 =
-12(-12(-12* 20+26)+4)+8 =
-12(-12* 10+4)+8
-12* 24+8 = 0 (mod 28)
is divisible by 28.
Code: PS, PD
P=1000, (k=8). 1008 = 36*28
Formulae:
Number N is divisible by 28 iff -8b+a is divisible by 28
Example:
Number N = 68 940 with base P=1000
-8*68 + 940 = 396 = 14*28+4
Number N isn't divisible by 28
Formulae:
Number N is divisible by 28 iff 16b+a = -12b+a is divisible by 28
Example:
Number N = 98 76 54 32 08 = 14 20 26 4 8 =
-12( 14 20 26 4)+8 =
-12(-12( 14 20 26+4)+8 =
-12(-12(-12( 14 20+26)+4)+8 =
-12(-12(-12(-12*14+20)+26)+4)+8 =
-12(-12(-12* 20+26)+4)+8 =
-12(-12* 10+4)+8
-12* 24+8 = 0 (mod 28)
is divisible by 28.
Code: PS, PD
P=1000, (k=8). 1008 = 36*28
Formulae:
Number N is divisible by 28 iff -8b+a is divisible by 28
Example:
Number N = 68 940 with base P=1000
-8*68 + 940 = 396 = 14*28+4
Number N isn't divisible by 28
number 27
Code: PU
P=100 (k=73=19 (mod 27) )
Formulae:
Number N is divisible by 27 iff 19*b+a = -8*b+a is divisible by 27
Example:
Number N = 98 76 54 32 19 = 17 22 0 5 19 =
-8( 17 22 0 5)+19 =
-8(-8( 17 22 0+5)+19 =
-8(-8(-8(17 22+0)+5)+19 =
-8(-8(-8(-8*17+22)+0)+5)+19 =
-8(-8(-8* 21+0)+5)+19 =
-8(-8* 21+5)+19 =
-8* 26+19 = 0 (mod 27)
is divisible by 27.
Code: SF 19*10-7*27=1
19(10b+a) = b+19a = b-8a (mod 27)
Formulae:
Number N is divisible by 27 iff b+19a = b-8a is divisible by 27
Example:
Number N = 68931
6893-8*1 = 6885
688-8*5 = 648
64-8*8 = 0
is divisible by 27
Code: SF- 8*10-3*27=-1
8(10b+a) = -b+8a = -(b-8a) (mod 27)
It is the same as above
P=100 (k=73=19 (mod 27) )
Formulae:
Number N is divisible by 27 iff 19*b+a = -8*b+a is divisible by 27
Example:
Number N = 98 76 54 32 19 = 17 22 0 5 19 =
-8( 17 22 0 5)+19 =
-8(-8( 17 22 0+5)+19 =
-8(-8(-8(17 22+0)+5)+19 =
-8(-8(-8(-8*17+22)+0)+5)+19 =
-8(-8(-8* 21+0)+5)+19 =
-8(-8* 21+5)+19 =
-8* 26+19 = 0 (mod 27)
is divisible by 27.
Code: SF 19*10-7*27=1
19(10b+a) = b+19a = b-8a (mod 27)
Formulae:
Number N is divisible by 27 iff b+19a = b-8a is divisible by 27
Example:
Number N = 68931
6893-8*1 = 6885
688-8*5 = 648
64-8*8 = 0
is divisible by 27
Code: SF- 8*10-3*27=-1
8(10b+a) = -b+8a = -(b-8a) (mod 27)
It is the same as above
10/12/17
number 26
Code: PU
P=100 (k=74=22 (mod 26) )
Formulae:
Number N is divisible by 26 iff 22*b+a = -4b+a is divisible by 26
Example:
Number N = 98 76 54 32 22 = 20 24 2 6 22 =
-4( 20 24 2 6)+22 =
-4(-4( 20 24 2+6)+22 =
-4(-4(-4(20 24+2)+6)+22 =
-4(-4(-4(-4*20+24)+2)+6)+22 =
-4(-4(-4* (-4)+2)+6)+22 =
-4(-4* 18+6)+22 =
-4* 12+22 = 0 (mod 26)
is divisible by 26.
Code: CR PD
P=25 (k=1)
Formulae:
Number N is divisible by 26 iff alternate sum of digits is divisible by 26
Example:
Number N = 68928 in decimal
Conversion to base P=25 is in previous post number 25
number is 4 10 7 3 with base 5^2 = 25
Formulae is: -4+10-7+3 = 2
so number N isn't divisible by 26
P=100 (k=74=22 (mod 26) )
Formulae:
Number N is divisible by 26 iff 22*b+a = -4b+a is divisible by 26
Example:
Number N = 98 76 54 32 22 = 20 24 2 6 22 =
-4( 20 24 2 6)+22 =
-4(-4( 20 24 2+6)+22 =
-4(-4(-4(20 24+2)+6)+22 =
-4(-4(-4(-4*20+24)+2)+6)+22 =
-4(-4(-4* (-4)+2)+6)+22 =
-4(-4* 18+6)+22 =
-4* 12+22 = 0 (mod 26)
is divisible by 26.
Code: CR PD
P=25 (k=1)
Formulae:
Number N is divisible by 26 iff alternate sum of digits is divisible by 26
Example:
Number N = 68928 in decimal
Conversion to base P=25 is in previous post number 25
number is 4 10 7 3 with base 5^2 = 25
Formulae is: -4+10-7+3 = 2
so number N isn't divisible by 26
10/11/17
number 25
Code: SN
100 = 4*25
Formulae:
Number N is divisible by 25 iff least significant two digits are 00, 25, 50 or 75.
Example:
Number N = 59 60 05 44 76 75
is divisible by 25
Code: PU
P=100 (k=75=0 (mod 25) )
Formulae:
Number N is divisible by 25 iff least significant digit is divisible by 24
Example:
Number N = 98 76 54 32 00
is divisible by 25.
Code: CR
P=25 (k=1)
Formulae:
Number N is divisible by 25 iff least significant digit is 0
Example:
Conversion to base P=25 uses method, eg:
1) from decimal system P=10: P=10*1/2, next P^2 into 25
2) P=100*1/4
Number N = 68928 with base P=10
Conversion from P=100*1/4: digits in bracket [] multiply by 4
[6 89 | 28] = [24 | 356] 28 = [24 | 14*25+6] 25+3
[24] = 96 = 3*25+21
repair of digits, they are not bigger than 25:
96 356 28 = 3 (21+14) (6+1) 3 = 4 10 7 3
or
from P=10*1/2:
[6 8 9 2 | 8] = [12 16 18 4] 8
[1 3 7 8 | 4] = [2 6 14 16 ] 4
[2 7 5 | 6] = [4 14 10] 6
[5 5 | 0] = [10 10] 0
[1 1 | 0] = [2 2] 0
[2 | 2] = 4 2
number is 4 2 0 0 6 4 8 = 4201203 with base P=5
number is 4 20 12 03 = 4 10 7 3 with base 5^2 = 25
Number N isn't divisible by 25 because remainder is 3
100 = 4*25
Formulae:
Number N is divisible by 25 iff least significant two digits are 00, 25, 50 or 75.
Example:
Number N = 59 60 05 44 76 75
is divisible by 25
Code: PU
P=100 (k=75=0 (mod 25) )
Formulae:
Number N is divisible by 25 iff least significant digit is divisible by 24
Example:
Number N = 98 76 54 32 00
is divisible by 25.
Code: CR
P=25 (k=1)
Formulae:
Number N is divisible by 25 iff least significant digit is 0
Example:
Conversion to base P=25 uses method, eg:
1) from decimal system P=10: P=10*1/2, next P^2 into 25
2) P=100*1/4
Number N = 68928 with base P=10
Conversion from P=100*1/4: digits in bracket [] multiply by 4
[6 89 | 28] = [24 | 356] 28 = [24 | 14*25+6] 25+3
[24] = 96 = 3*25+21
repair of digits, they are not bigger than 25:
96 356 28 = 3 (21+14) (6+1) 3 = 4 10 7 3
or
from P=10*1/2:
[6 8 9 2 | 8] = [12 16 18 4] 8
[1 3 7 8 | 4] = [2 6 14 16 ] 4
[2 7 5 | 6] = [4 14 10] 6
[5 5 | 0] = [10 10] 0
[1 1 | 0] = [2 2] 0
[2 | 2] = 4 2
number is 4 2 0 0 6 4 8 = 4201203 with base P=5
number is 4 20 12 03 = 4 10 7 3 with base 5^2 = 25
Number N isn't divisible by 25 because remainder is 3
9/30/17
number 24
P=100 (k=76=4 (mod 24) )
Formulae:
Number N is divisible by 24 iff 4*b+a is divisible by 24
Example:
Number N = 98 76 54 32 16 = 2 4 6 8 16 =
4(2 4 6 8)+16 =
4(4(2 4 6+8)+16 =
4(4(4(2 4+6)+8)+16 =
4(4(4(4*2+4)+6)+8)+16 =
4(4(4* 12+6)+8)+16 =
4(4* 6+8)+16 =
4* 8+16 = 0 (mod 24)
is divisible by 24.
Code: CR PU
P=25 (k=1)
Formulae:
Number N is divisible by 24 iff sum of digits is divisible by 24
Example:
Number N = 68928 with base P=10
Conversion to base P=25 is in next post number 25
number is 4 10 7 3 with base 5^2 = 25 Formulae is: 4+10+7+3 = 24
so number N is divisible by 24
9/28/17
number 23
Code: PU
P=100 (k=77=8 (mod 23) )
Formulae:
Number N is divisible by 23 iff 8*b+a is divisible by 23
Example:
Number N = 98 76 54 32 06 = 6 7 8 9 6 =
8(6 7 8 9)+6 =
8(8(6 7 8+9)+6 =
8(8(8(6 7+8)+9)+6 =
8(8(8(8*6+7)+8)+9)+6 =
8(8(8* 9+8)+9)+6 =
8(8* 11+9)+6 =
8* 5+6 = 0 (mod 23)
is divisible by 23.
Code: SF 7*10-3*23=1
7(10b+a) = b+7a (mod 23)
Formulae:
Number N is divisible by 23 iff b+7a is divisible by 23
Example:
Number N = 68932
6893+7*2 = 6907
690+7*7 = 739
73+7*9 = 136
13+7*6 = 55
isn't divisible by 23
Code: SF- 16*10-7*23=-1
16(10b+a) = -b+16a = -(b-16a) = -(b+7a) (mod 23)
It is the same as above
P=100 (k=77=8 (mod 23) )
Formulae:
Number N is divisible by 23 iff 8*b+a is divisible by 23
Example:
Number N = 98 76 54 32 06 = 6 7 8 9 6 =
8(6 7 8 9)+6 =
8(8(6 7 8+9)+6 =
8(8(8(6 7+8)+9)+6 =
8(8(8(8*6+7)+8)+9)+6 =
8(8(8* 9+8)+9)+6 =
8(8* 11+9)+6 =
8* 5+6 = 0 (mod 23)
is divisible by 23.
Code: SF 7*10-3*23=1
7(10b+a) = b+7a (mod 23)
Formulae:
Number N is divisible by 23 iff b+7a is divisible by 23
Example:
Number N = 68932
6893+7*2 = 6907
690+7*7 = 739
73+7*9 = 136
13+7*6 = 55
isn't divisible by 23
Code: SF- 16*10-7*23=-1
16(10b+a) = -b+16a = -(b-16a) = -(b+7a) (mod 23)
It is the same as above
9/27/17
number 22
Code: PU P=100 (k=78=12 (mod 22) )
Formulae:
Number N is divisible by 22 iff 12b+a = -10b+a = -(10b-a) is divisible by 22
Example:
Number N = 98 76 54 32 04 = 10 10 10 10 4 =
-10( 10 10 10 10)+4 =
-10(-10( 10 10 10+10)+4 =
-10(-10(-10( 10 10+10)+10)+4 =
-10(-10(-10(-10*10+10)+10)+10)+4 =
-10(-10(-10* 20+10)+10)+4 =
-10(-10* 8+10)+4
-10* 18+4 = 0 (mod 22)
is divisible by 22.
This method one can't omit a minus before -(10b-a), contrary do FS. The fast calculation from middle are as follow (four last lines):
10*10-10 = 90 = 2 (mod 22)
10*(-2)-10 = -30 = -8 (mod 22)
10*(--8)-10 = 70 = 4 (mod 22)
10*(-4)-4 = -44 = 0 (mod 22)
Code: PS, CR
P=11*10, (k=11). 110 = 5*22
Formulae:
Number N is divisible by 22 iff remainder from division by 110 is divisible by 22
Example:
Number N = 68940 with base P=10
Conversion to base 110, first step
[6, 8, 9, 4 | 0] = [0, 66, 22, 66 | 80] = 11*[0, 6, 2, 6] 80
Number N isn't divisible by 22 because 80=6*22+14.
Formulae:
Number N is divisible by 22 iff 12b+a = -10b+a = -(10b-a) is divisible by 22
Example:
Number N = 98 76 54 32 04 = 10 10 10 10 4 =
-10( 10 10 10 10)+4 =
-10(-10( 10 10 10+10)+4 =
-10(-10(-10( 10 10+10)+10)+4 =
-10(-10(-10(-10*10+10)+10)+10)+4 =
-10(-10(-10* 20+10)+10)+4 =
-10(-10* 8+10)+4
-10* 18+4 = 0 (mod 22)
is divisible by 22.
This method one can't omit a minus before -(10b-a), contrary do FS. The fast calculation from middle are as follow (four last lines):
10*10-10 = 90 = 2 (mod 22)
10*(-2)-10 = -30 = -8 (mod 22)
10*(--8)-10 = 70 = 4 (mod 22)
10*(-4)-4 = -44 = 0 (mod 22)
Code: PS, CR
P=11*10, (k=11). 110 = 5*22
Formulae:
Number N is divisible by 22 iff remainder from division by 110 is divisible by 22
Example:
Number N = 68940 with base P=10
Conversion to base 110, first step
[6, 8, 9, 4 | 0] = [0, 66, 22, 66 | 80] = 11*[0, 6, 2, 6] 80
Number N isn't divisible by 22 because 80=6*22+14.
number 21
Code: PU, PD
P=100 (k=79=16 (mod 21) )
PD: 105 = 5*21 = 100+5
Formulae:
Number N is divisible by 21 iff 16*b+a = -5*b+a is divisible by 21
Example:
Number N = 98 76 54 32 01 = 14 13 12 11 1 =
-5(14 13 12 11)+1 =
-5(-5(14 13 12+11)+1 =
-5(-5(-5(14 13+12)+11)+1 =
-5(-5(-5(-5*14+13)+12)+11)+1 =
-5(-5(-5* 6+12)+11)+1 =
-5(-5* 3+11)+1 =
-5* 17+1 = 0 (mod 21)
is divisible by 21.
Code: SF 19*10-9*21=1
19(10b+a) = b+19a = b-2a (mod 21)
Formulae:
Number N is divisible by 21 iff b-2a is divisible by 21
Example:
Number N = 68932
6893-2*2 = 6889
688-2*9 = 670
67-2*0 = 67
6-2*7 = 19
isn't divisible by 21
Code: SF- 2*10-1*19=-1
2(10b+a) = -b+2a = -(b-2a) (mod 21)
It is the same as above
P=100 (k=79=16 (mod 21) )
PD: 105 = 5*21 = 100+5
Formulae:
Number N is divisible by 21 iff 16*b+a = -5*b+a is divisible by 21
Example:
Number N = 98 76 54 32 01 = 14 13 12 11 1 =
-5(14 13 12 11)+1 =
-5(-5(14 13 12+11)+1 =
-5(-5(-5(14 13+12)+11)+1 =
-5(-5(-5(-5*14+13)+12)+11)+1 =
-5(-5(-5* 6+12)+11)+1 =
-5(-5* 3+11)+1 =
-5* 17+1 = 0 (mod 21)
is divisible by 21.
Code: SF 19*10-9*21=1
19(10b+a) = b+19a = b-2a (mod 21)
Formulae:
Number N is divisible by 21 iff b-2a is divisible by 21
Example:
Number N = 68932
6893-2*2 = 6889
688-2*9 = 670
67-2*0 = 67
6-2*7 = 19
isn't divisible by 21
Code: SF- 2*10-1*19=-1
2(10b+a) = -b+2a = -(b-2a) (mod 21)
It is the same as above
9/26/17
number 20
Code: PU P=100 (k=80=0 (mod 20) )
Formulae:
Number N is divisible by 20 iff least significant digit is divisible by 20
Example:
Number N = 98 76 54 32 20
is divisible by 20.
Code: PS, CR
P=2*10, (k=2)
Formulae:
Number N is divisible by 20 iff least significant digit with base 20 is 0
Example:
Number N = 68940 with base P=10
[6, 8, 9, 4 | 0] = [6, 8, 8, 14 | 0] = 2*[3, 4, 8, 7] 0
Number N is divisible by 20. Other digits:
[3, 4, 4 | 7] = [2, 14, 4 | 7] = 2*[1, 7, 2] 7
[1, 7 | 2] = [0, 16 | 12] = 2*[0, 8] 12
[0 | 8] = 2*[0] 8
So N = 8 12 7 0 with base 20
Formulae:
Number N is divisible by 20 iff least significant digit is divisible by 20
Example:
Number N = 98 76 54 32 20
is divisible by 20.
Code: PS, CR
P=2*10, (k=2)
Formulae:
Number N is divisible by 20 iff least significant digit with base 20 is 0
Example:
Number N = 68940 with base P=10
[6, 8, 9, 4 | 0] = [6, 8, 8, 14 | 0] = 2*[3, 4, 8, 7] 0
Number N is divisible by 20. Other digits:
[3, 4, 4 | 7] = [2, 14, 4 | 7] = 2*[1, 7, 2] 7
[1, 7 | 2] = [0, 16 | 12] = 2*[0, 8] 12
[0 | 8] = 2*[0] 8
So N = 8 12 7 0 with base 20
9/25/17
number 19
Code: PU
P=100 (k=81=5 (mod 19) )
Formulae:
Number N is divisible by 19 iff 5*b+a is divisible by 19
Example:
Number N = 98 76 54 32 16 = 3 0 16 13 16 =
5(3 0 16 13)+16 =
5(5( 3 0 16+13)+16 =
5(5(5( 3 0+16)+13)+16 =
5(5(5(5* 3+0)+16)+13)+16 =
5(5(5* 15+16)+13)+16 =
5(5* 15+13)+16
5* 12+16 = 0 (mod 19)
is divisible by 19.
Code: PD
P=10, (k=9)
Formulae:
Number N is divisible by 19 iff -9b+a = 10b+a is divisible by 19
Example:
Number N = 54391
-9( 5439)+1 =
-9(-9( 543+9)+1 =
-9(-9(-9( 54+3)+9)+1 =
-9(-9(-9(-9*5+4)+3)+9)+1 =
-9(-9(-9*(-3)+3)+9)+1 =
-9(-9* 11+9)+1
-9* 5+1 = 13 (mod 19)
isn't divisible by 19.
Code: SF 2*10-1*19=1
2(10b+a) = b+2a (mod 19)
Formulae:
Number N is divisible by 19 iff b+2a is divisible by 19
Example:
Number N = 68932
6893+2*2 = 6897
689+2*7 =703
70+2*3 =76
7+2*6 = 19
is divisible by 19
Code: SF- 17*10-9*19=-1
17(10b+a) = -b+17a = -(b+2a) (mod 19)
It is the same as above
P=100 (k=81=5 (mod 19) )
Formulae:
Number N is divisible by 19 iff 5*b+a is divisible by 19
Example:
Number N = 98 76 54 32 16 = 3 0 16 13 16 =
5(3 0 16 13)+16 =
5(5( 3 0 16+13)+16 =
5(5(5( 3 0+16)+13)+16 =
5(5(5(5* 3+0)+16)+13)+16 =
5(5(5* 15+16)+13)+16 =
5(5* 15+13)+16
5* 12+16 = 0 (mod 19)
is divisible by 19.
Code: PD
P=10, (k=9)
Formulae:
Number N is divisible by 19 iff -9b+a = 10b+a is divisible by 19
Example:
Number N = 54391
-9( 5439)+1 =
-9(-9( 543+9)+1 =
-9(-9(-9( 54+3)+9)+1 =
-9(-9(-9(-9*5+4)+3)+9)+1 =
-9(-9(-9*(-3)+3)+9)+1 =
-9(-9* 11+9)+1
-9* 5+1 = 13 (mod 19)
isn't divisible by 19.
Code: SF 2*10-1*19=1
2(10b+a) = b+2a (mod 19)
Formulae:
Number N is divisible by 19 iff b+2a is divisible by 19
Example:
Number N = 68932
6893+2*2 = 6897
689+2*7 =703
70+2*3 =76
7+2*6 = 19
is divisible by 19
Code: SF- 17*10-9*19=-1
17(10b+a) = -b+17a = -(b+2a) (mod 19)
It is the same as above
number 18
Code: PU P=100 (k=82=10 (mod 18) )
Formulae:
Number N is divisible by 18 iff 10*b+a is divisible by 18
Example:
Number N = 98 76 54 32 10 = 8 4 0 14 10 =
10( 8 4 0 14)+10 =
10(10( 8 4 0+14)+10 =
10(10(10( 8 4+0)+14)+10 =
10(10(10(10*8+4)+0)+14)+10 =
10(10(10* 12+0)+14)+10 =
10(10* 12+14)+10 =
10* 8+10 = 0 (mod 18)
is divisible by 18.
Code: PD
P=10, (k=8)
Formulae:
Number N is divisible by 18 iff -8b+a is divisible by 18
Example:
Number N = 54392
-8( 5439)+2 =
-8(-8( 543+9)+2 =
-8(-8(-8( 54+3)+9)+2 =
-8(-8(-8(-8*5+4)+3)+9)+2 =
-8(-8(-8* 0+3)+9)+2 =
-8(-8* 3+9)+2
-8* 3+2 = 14 (mod 18)
isn't divisible by 18.
Code: PS, CR
P=9*10, (k=9)
Formulae:
Number N is divisible by 18 iff remainder from division by 90 is divisible by 18
Example:
Number N = 68940 with base P=10
B=[6], C=?, A=[8,9,4,0]
B=[0]/9#[6*10+8]=[0,68], C=6, A=[9,4,0]
B=[0,63]/9#[5*10+9]=[0,7,59], C=5, A=[4,0]
B=[0,0,684]/9#[5*10+4]=[0,0,76,54], C=5, A=[0]
B=[0,0,72,414]/9#[0]=[0,0,8,46,0], C=0, A=[]
least significant digit of 8 46 0 is 0, so N is divisible by 18
or (other here eg. 68=63+5, 63 stands by and 5 movies to less significant value).
[6, 8, 9, 4 | 0] = [0, 63, 54, 54 | 0] = 9*[0, 7, 6, 6] 0
[0, 7, 6 | 6] = [0, 0, 72 | 46] = 9*[0, 0, 8] 46
[0, 0 | 8] = 9*[0] 8
Formulae:
Number N is divisible by 18 iff 10*b+a is divisible by 18
Example:
Number N = 98 76 54 32 10 = 8 4 0 14 10 =
10( 8 4 0 14)+10 =
10(10( 8 4 0+14)+10 =
10(10(10( 8 4+0)+14)+10 =
10(10(10(10*8+4)+0)+14)+10 =
10(10(10* 12+0)+14)+10 =
10(10* 12+14)+10 =
10* 8+10 = 0 (mod 18)
is divisible by 18.
Code: PD
P=10, (k=8)
Formulae:
Number N is divisible by 18 iff -8b+a is divisible by 18
Example:
Number N = 54392
-8( 5439)+2 =
-8(-8( 543+9)+2 =
-8(-8(-8( 54+3)+9)+2 =
-8(-8(-8(-8*5+4)+3)+9)+2 =
-8(-8(-8* 0+3)+9)+2 =
-8(-8* 3+9)+2
-8* 3+2 = 14 (mod 18)
isn't divisible by 18.
Code: PS, CR
P=9*10, (k=9)
Formulae:
Number N is divisible by 18 iff remainder from division by 90 is divisible by 18
Example:
Number N = 68940 with base P=10
B=[6], C=?, A=[8,9,4,0]
B=[0]/9#[6*10+8]=[0,68], C=6, A=[9,4,0]
B=[0,63]/9#[5*10+9]=[0,7,59], C=5, A=[4,0]
B=[0,0,684]/9#[5*10+4]=[0,0,76,54], C=5, A=[0]
B=[0,0,72,414]/9#[0]=[0,0,8,46,0], C=0, A=[]
least significant digit of 8 46 0 is 0, so N is divisible by 18
or (other here eg. 68=63+5, 63 stands by and 5 movies to less significant value).
[6, 8, 9, 4 | 0] = [0, 63, 54, 54 | 0] = 9*[0, 7, 6, 6] 0
[0, 7, 6 | 6] = [0, 0, 72 | 46] = 9*[0, 0, 8] 46
[0, 0 | 8] = 9*[0] 8
9/23/17
number 17
Code: PU
P=100 (k=83=15=-2 (mod 17) )
Formulae:
Number N is divisible by 17 iff 15*b+a = -2b+a is divisible by 17
Example:
Number N = 98 76 54 32 10 = 13 8 3 15 10 =
-2( 13 8 3 15)+10 =
-2(-2( 13 8 3+15)+10 =
-2(-2(-2( 13 8+3)+15)+10 =
-2(-2(-2(-2*13+8)+3)+15)+10 =
-2(-2(-2* 16+3)+15)+10 =
-2(-2* 5+15)+10
-2* 5+10 = 0 (mod 17)
is divisible by 17.
Code: PD
P=10, (k=7)
Formulae:
Number N is divisible by 17 iff -7b+a is divisible by 17
Example:
Number N = 54391
-7( 5439)+1 =
-7(-7( 543+9)+1 =
-7(-7(-7( 54+3)+9)+1 =
-7(-7(-7(-7*5+4)+3)+9)+1 =
-7(-7(-7* 3+3)+9)+1 =
-7(-7* (-1)+9)+1
-7* (-1)+1 = 8 (mod 17)
isn't divisible by 17.
Code: SF 12*10-7*17=1
12(10b+a) = b+12a (mod 17)
Formulae:
Number N is divisible by 17 iff b+12a is divisible by 17
Example:
Number N = 68941
6894+12*1 = 6906
689+12*8 = 762
76+12*2 = 100
10+12*0 = 10
isn't divisible by 17
This rule is equivalent the next one.
Code: SF- 5*10-3*17=-1
5(10b+a) = -b+5a = -(b-5a) (mod 17)
Formulae:
Number N is divisible by 17 iff b-5a is divisible by 17
Example:
Number N = 67915
6791-5*5 = 6766
676-5*6 =646
64-5*6 = 34 = 2*17
is divisible by 17
P=100 (k=83=15=-2 (mod 17) )
Formulae:
Number N is divisible by 17 iff 15*b+a = -2b+a is divisible by 17
Example:
Number N = 98 76 54 32 10 = 13 8 3 15 10 =
-2( 13 8 3 15)+10 =
-2(-2( 13 8 3+15)+10 =
-2(-2(-2( 13 8+3)+15)+10 =
-2(-2(-2(-2*13+8)+3)+15)+10 =
-2(-2(-2* 16+3)+15)+10 =
-2(-2* 5+15)+10
-2* 5+10 = 0 (mod 17)
is divisible by 17.
Code: PD
P=10, (k=7)
Formulae:
Number N is divisible by 17 iff -7b+a is divisible by 17
Example:
Number N = 54391
-7( 5439)+1 =
-7(-7( 543+9)+1 =
-7(-7(-7( 54+3)+9)+1 =
-7(-7(-7(-7*5+4)+3)+9)+1 =
-7(-7(-7* 3+3)+9)+1 =
-7(-7* (-1)+9)+1
-7* (-1)+1 = 8 (mod 17)
isn't divisible by 17.
Code: SF 12*10-7*17=1
12(10b+a) = b+12a (mod 17)
Formulae:
Number N is divisible by 17 iff b+12a is divisible by 17
Example:
Number N = 68941
6894+12*1 = 6906
689+12*8 = 762
76+12*2 = 100
10+12*0 = 10
isn't divisible by 17
This rule is equivalent the next one.
Code: SF- 5*10-3*17=-1
5(10b+a) = -b+5a = -(b-5a) (mod 17)
Formulae:
Number N is divisible by 17 iff b-5a is divisible by 17
Example:
Number N = 67915
6791-5*5 = 6766
676-5*6 =646
64-5*6 = 34 = 2*17
is divisible by 17
9/21/17
number 16
Code: PS P=10.000
b10000+a = 16*625b+a = a
Formulae:
Number N is divisible by 16 iff least significant digit a is divisible by 16
Example:
Number N = 9876 5430 9856
9856 = 16*616
Number N is divisible by 16
Code: PU
P=100 (k=84=4 (mod 16) )
Formulae:
Number N is divisible by 16 iff 4*b+a is divisible by 16
Example:
Number N = 98 76 54 32 00 = 2 12 6 0 0 =
4(2 12 6 0)+0 =
4(4(2 12 6+0)+0 =
4(4(4(2 12+6)+0)+0 =
4(4(4(4* 2+12)+6)+0)+0 =
4(4(4* 4+12)+0)+0 =
4(4* 12+0)+0 =
4* 24+0 = 0 (mod 16)
is divisible by 16.
Code: PD
P=10, (k=6)
Formulae:
Number N is divisible by 16 iff -6b+a is divisible by 16
Example:
Number N = 54392
-6( 5439)+2 =
-6(-6( 543+9)+2 =
-6(-6(-6( 54+3)+9)+2 =
-6(-6(-6(-6*5+4)+3)+9)+2 =
-6(-6(-6* 6+3)+9)+2 =
-6(-6* 15+9)+2
-6* 15+2 = 8 (mod 16)
isn't divisible by 16.
Code: CR
P=400 (k=100*4)
Formulae:
Number N is divisible by 16 iff remainder from division by 400 is divisible by 16
Example:
Number N = 84 56 21 34
Conversion to P=100*4
[84, 56, 21 | 34] = [84, 56, 20] | 134 = 4*[21, 14, 5] | 134
[21, 14 | 5] = [20, 112] | 205 = 4*[5, 28] | 205
[5 | 28] = [4] | 128 = 4*[1] | 128
[1] = 1
Take least significant digit from number N = 1 128 205 134, and 134 = 8*16+6, so N isn't divisible by 16.
The first step of conversion is enough to check using this method of conversion.
b10000+a = 16*625b+a = a
Formulae:
Number N is divisible by 16 iff least significant digit a is divisible by 16
Example:
Number N = 9876 5430 9856
9856 = 16*616
Number N is divisible by 16
Code: PU
P=100 (k=84=4 (mod 16) )
Formulae:
Number N is divisible by 16 iff 4*b+a is divisible by 16
Example:
Number N = 98 76 54 32 00 = 2 12 6 0 0 =
4(2 12 6 0)+0 =
4(4(2 12 6+0)+0 =
4(4(4(2 12+6)+0)+0 =
4(4(4(4* 2+12)+6)+0)+0 =
4(4(4* 4+12)+0)+0 =
4(4* 12+0)+0 =
4* 24+0 = 0 (mod 16)
is divisible by 16.
Code: PD
P=10, (k=6)
Formulae:
Number N is divisible by 16 iff -6b+a is divisible by 16
Example:
Number N = 54392
-6( 5439)+2 =
-6(-6( 543+9)+2 =
-6(-6(-6( 54+3)+9)+2 =
-6(-6(-6(-6*5+4)+3)+9)+2 =
-6(-6(-6* 6+3)+9)+2 =
-6(-6* 15+9)+2
-6* 15+2 = 8 (mod 16)
isn't divisible by 16.
Code: CR
P=400 (k=100*4)
Formulae:
Number N is divisible by 16 iff remainder from division by 400 is divisible by 16
Example:
Number N = 84 56 21 34
Conversion to P=100*4
[84, 56, 21 | 34] = [84, 56, 20] | 134 = 4*[21, 14, 5] | 134
[21, 14 | 5] = [20, 112] | 205 = 4*[5, 28] | 205
[5 | 28] = [4] | 128 = 4*[1] | 128
[1] = 1
Take least significant digit from number N = 1 128 205 134, and 134 = 8*16+6, so N isn't divisible by 16.
The first step of conversion is enough to check using this method of conversion.
number 15
Code: PU
P=100 (k=85=10 (mod 15) )
Formulae:
Number N is divisible by 15 iff 10*b+a = -5b+a is divisible by 15
Example:
Number N = 98 76 54 32 05 = 8 1 9 2 0 =
10( 8 1 9 2)+0 =
10(10( 8 1 9+2)+0 =
10(10(10( 8 1+9)+2)+0 =
10(10(10(10*9+1)+9)+2)+0 =
10(10(10* 1+9)+2)+0 =
10(10* 4+2)+0
10* 12 = 0 (mod 15)
is divisible by 15.
Code: PD
P=10, (k=5)
Formulae:
Number N is divisible by 15 iff -5b+a is divisible by 15
Example:
Number N = 54395
-5( 5439)+5 =
-5(-5( 543+9)+5 =
-5(-5(-5( 54+3)+9)+5 =
-5(-5(-5(-5*5+4)+3)+9)+5 =
-5(-5(-5* 9+3)+9)+5 =
-5(-5* 3+9)+5
-5* 9+5 = 5 (mod 15)
isn't divisible by 15.
The rule is common in both cases, but there are different base P, so they are different rules.
Code: CR P=10*3= 30
Formulae:
Number N is divisible by 15 iff least significant digit is 0 or 15 in base P=30
Example:
Number N = 68940 with base P=10
B=[6], C=?, A=[8,9,4,0]
B=[6]/3#[0*10+8]=[2,8], C=0, A=[9,4,0]
B=[0,66]/3#[2*10+9]=[0,22,29], C=2, A=[4,0]
B=[0,21,57]/3#[2*10+4]=[0,7,19,24], C=2, A=[0]
B=[0,6,48,54]/3#[0]=[0,2,16,18,0], c=0, A=[]
least significant digit of 2 16 18 0 is 0, so N is divisible by 15
P=100 (k=85=10 (mod 15) )
Formulae:
Number N is divisible by 15 iff 10*b+a = -5b+a is divisible by 15
Example:
Number N = 98 76 54 32 05 = 8 1 9 2 0 =
10( 8 1 9 2)+0 =
10(10( 8 1 9+2)+0 =
10(10(10( 8 1+9)+2)+0 =
10(10(10(10*9+1)+9)+2)+0 =
10(10(10* 1+9)+2)+0 =
10(10* 4+2)+0
10* 12 = 0 (mod 15)
is divisible by 15.
Code: PD
P=10, (k=5)
Formulae:
Number N is divisible by 15 iff -5b+a is divisible by 15
Example:
Number N = 54395
-5( 5439)+5 =
-5(-5( 543+9)+5 =
-5(-5(-5( 54+3)+9)+5 =
-5(-5(-5(-5*5+4)+3)+9)+5 =
-5(-5(-5* 9+3)+9)+5 =
-5(-5* 3+9)+5
-5* 9+5 = 5 (mod 15)
isn't divisible by 15.
The rule is common in both cases, but there are different base P, so they are different rules.
Code: CR P=10*3= 30
Formulae:
Number N is divisible by 15 iff least significant digit is 0 or 15 in base P=30
Example:
Number N = 68940 with base P=10
B=[6], C=?, A=[8,9,4,0]
B=[6]/3#[0*10+8]=[2,8], C=0, A=[9,4,0]
B=[0,66]/3#[2*10+9]=[0,22,29], C=2, A=[4,0]
B=[0,21,57]/3#[2*10+4]=[0,7,19,24], C=2, A=[0]
B=[0,6,48,54]/3#[0]=[0,2,16,18,0], c=0, A=[]
least significant digit of 2 16 18 0 is 0, so N is divisible by 15
9/20/17
number 14
Code: PU
P=100 (k=86=2 (mod 14) )
Formulae:
Number N is divisible by 14 iff 2*b+a is divisible by 14
Example:
Number N = 98 76 54 32 08 = 0 6 12 4 8 =
2(0 6 12 4)+8 =
2(2(0 6 12+4)+8 =
2(2(2(0 6+12)+4)+8 =
2(2(2(2* 0+6)+12)+4)+8 =
2(2(2* 6+12)+4)+8 =
2(2* 10+4)+8 =
2* 10+8 = 0 (mod 14)
is divisible by 14.
Code: PD
P=10, (k=4)
Formulae:
Number N is divisible by 14 iff -4b+a is divisible by 14
Example:
Number N = 54391
-4( 5439)+1 =
-4(-4( 543+9)+1 =
-4(-4(-4( 54+3)+9)+1 =
-4(-4(-4(-4*5+4)+3)+9)+1 =
-4(-4(-4* 12+3)+9)+1 =
-4(-4* 11+9)+1
-4* 7+1 = 8 (mod 14)
isn't divisible by 14.
P=100 (k=86=2 (mod 14) )
Formulae:
Number N is divisible by 14 iff 2*b+a is divisible by 14
Example:
Number N = 98 76 54 32 08 = 0 6 12 4 8 =
2(0 6 12 4)+8 =
2(2(0 6 12+4)+8 =
2(2(2(0 6+12)+4)+8 =
2(2(2(2* 0+6)+12)+4)+8 =
2(2(2* 6+12)+4)+8 =
2(2* 10+4)+8 =
2* 10+8 = 0 (mod 14)
is divisible by 14.
Code: PD
P=10, (k=4)
Formulae:
Number N is divisible by 14 iff -4b+a is divisible by 14
Example:
Number N = 54391
-4( 5439)+1 =
-4(-4( 543+9)+1 =
-4(-4(-4( 54+3)+9)+1 =
-4(-4(-4(-4*5+4)+3)+9)+1 =
-4(-4(-4* 12+3)+9)+1 =
-4(-4* 11+9)+1
-4* 7+1 = 8 (mod 14)
isn't divisible by 14.
9/19/17
number 13
Code: PU
P=100 (k=87=9 (mod 13) )
Formulae:
Number N is divisible by 13 iff 9*b+a = -4b+a is divisible by 13
Example:
Number N = 98 76 54 32 09 = 7 11 2 6 9 =
9(7 11 2 6)+9 =
9(9(7 11 2+6)+9 =
9(9(9(7 11+2)+6)+9 =
9(9(9(9* 7+11)+2)+6)+9 =
9(9(9* 9+2)+6)+9 =
9(9* 5+6)+9
9* 12+9 = 0 (mod 13)
is divisible by 13.
Code: PD
P=10, (k=3)
Formulae:
Number N is divisible by 13 iff -3b+a is divisible by 13
Example:
Number N = 54391
-3( 5439)+1 =
-3(-3( 543+9)+1 =
-3(-3(-3( 54+3)+9)+1 =
-3(-3(-3(-3*5+4)+3)+9)+1 =
-3(-3(-3* 2+3)+9)+1 =
-3(-3* 10+9)+1
-3* 5+1 = 12 (mod 13)
isn't divisible by 13.
Code: SN, PD in P=1000 (k=1 special) 1001 = 7*11*13
Compare with divisibility rule by 7
Formulae:
Number N is divisible by 13 iff remainder from division by 1001 is divisible by 13
Code: SF 4*10-3*13=1
4(10b+a) = b+4a (mod 13)
Formulae:
Number N is divisible by 13 iff b+4a is divisible by 13
Example:
Number N = 68941
6894+4*1 = 6898
689+4*8 = 721
72+4*1 = 76
7+4*6 = 31 = 2*13+5
isn't divisible by 13, but the remainder is other than 5
Code: SF- 9*10-7*13=-1
9(10b+a) = -b+9a (mod 13)
Formulae:
Number N is divisible by 13 iff b-9a is divisible by 13
Example:
Number N = 67912
6791-9*2 = 6773
677-9*3 =650
65-9*0 = 65 = 5*13
is divisible by 13
P=100 (k=87=9 (mod 13) )
Formulae:
Number N is divisible by 13 iff 9*b+a = -4b+a is divisible by 13
Example:
Number N = 98 76 54 32 09 = 7 11 2 6 9 =
9(7 11 2 6)+9 =
9(9(7 11 2+6)+9 =
9(9(9(7 11+2)+6)+9 =
9(9(9(9* 7+11)+2)+6)+9 =
9(9(9* 9+2)+6)+9 =
9(9* 5+6)+9
9* 12+9 = 0 (mod 13)
is divisible by 13.
Code: PD
P=10, (k=3)
Formulae:
Number N is divisible by 13 iff -3b+a is divisible by 13
Example:
Number N = 54391
-3( 5439)+1 =
-3(-3( 543+9)+1 =
-3(-3(-3( 54+3)+9)+1 =
-3(-3(-3(-3*5+4)+3)+9)+1 =
-3(-3(-3* 2+3)+9)+1 =
-3(-3* 10+9)+1
-3* 5+1 = 12 (mod 13)
isn't divisible by 13.
Code: SN, PD in P=1000 (k=1 special) 1001 = 7*11*13
Compare with divisibility rule by 7
Formulae:
Number N is divisible by 13 iff remainder from division by 1001 is divisible by 13
Code: SF 4*10-3*13=1
4(10b+a) = b+4a (mod 13)
Formulae:
Number N is divisible by 13 iff b+4a is divisible by 13
Example:
Number N = 68941
6894+4*1 = 6898
689+4*8 = 721
72+4*1 = 76
7+4*6 = 31 = 2*13+5
isn't divisible by 13, but the remainder is other than 5
Code: SF- 9*10-7*13=-1
9(10b+a) = -b+9a (mod 13)
Formulae:
Number N is divisible by 13 iff b-9a is divisible by 13
Example:
Number N = 67912
6791-9*2 = 6773
677-9*3 =650
65-9*0 = 65 = 5*13
is divisible by 13
number 12
Code: PU
P=100 (k=88=4 (mod 12) )
Formulae:
Number N is divisible by 12 iff 4*b+a is divisible by 12
Example:
Number N = 98 76 54 32 04 = 2 4 6 8 4 =
4(2 4 6 8)+4 =
4(4(2 4 6+8)+4 =
4(4(4(2 4+6)+8)+4 =
4(4(4(4*2+4)+6)+8)+4 =
4(4(4* 0+6)+8)+4 =
4(4* 6+8)+4
4* 8+4 = 0 (mod 12)
is divisible by 12.
Code: PD
P=10, (k=2)
Formulae:
Number N is divisible by 12 iff -2b+a is divisible by 12
Example:
Number N = 54391
-2( 5439)+1 =
-2(-2( 543+9)+1 =
-2(-2(-2( 54+3)+9)+1 =
-2(-2(-2(-2*5+4)+3)+9)+1 =
-2(-2(-2* 6+3)+9)+1 =
-2(-2* 3+9)+1
-2* 3+1 = 7 (mod 12)
isn't divisible by 12.
P=100 (k=88=4 (mod 12) )
Formulae:
Number N is divisible by 12 iff 4*b+a is divisible by 12
Example:
Number N = 98 76 54 32 04 = 2 4 6 8 4 =
4(2 4 6 8)+4 =
4(4(2 4 6+8)+4 =
4(4(4(2 4+6)+8)+4 =
4(4(4(4*2+4)+6)+8)+4 =
4(4(4* 0+6)+8)+4 =
4(4* 6+8)+4
4* 8+4 = 0 (mod 12)
is divisible by 12.
Code: PD
P=10, (k=2)
Formulae:
Number N is divisible by 12 iff -2b+a is divisible by 12
Example:
Number N = 54391
-2( 5439)+1 =
-2(-2( 543+9)+1 =
-2(-2(-2( 54+3)+9)+1 =
-2(-2(-2(-2*5+4)+3)+9)+1 =
-2(-2(-2* 6+3)+9)+1 =
-2(-2* 3+9)+1
-2* 3+1 = 7 (mod 12)
isn't divisible by 12.
9/18/17
number 11
Code: PU
P=100 (k=89=1 (mod 11) )
Formulae:
Number N is divisible by 11 iff sum of digits is divisible by 11
Example:
Number N =
98 76 54 32 04
10+10+10+10+4 = 44 = 0 (mod 11)
is divisible by 11.
Number N =
10 23 07 29
10+1+7+7 = 25 = 3 (mod 11)
isn't divisible by 11.
Code: PD
P=10, (k=1)
Formulae:
Number N is divisible by 11 iff alternating sum of digits is divisible by 11
Example:
Number N =
9 8 7 6 5 4 3 2 1 5
-9+8-7+6-5+4-3+2-1+5 = 0 (mod 11)
is divisible by 11.
Number N =
5 3 1 9 7 6 2
5-3+1-9+7-6+2 = -3 = 8 (mod 11)
isn't divisible by11.
Code: SN, PD in P=1000 (k=1 special) 1001 = 7*11*13
Compare with divisibility rule by 7
Formulae:
Number N is divisible by 11 iff remainder from division by 1001 is divisible by 11
P=100 (k=89=1 (mod 11) )
Formulae:
Number N is divisible by 11 iff sum of digits is divisible by 11
Example:
Number N =
98 76 54 32 04
10+10+10+10+4 = 44 = 0 (mod 11)
is divisible by 11.
Number N =
10 23 07 29
10+1+7+7 = 25 = 3 (mod 11)
isn't divisible by 11.
Code: PD
P=10, (k=1)
Formulae:
Number N is divisible by 11 iff alternating sum of digits is divisible by 11
Example:
Number N =
9 8 7 6 5 4 3 2 1 5
-9+8-7+6-5+4-3+2-1+5 = 0 (mod 11)
is divisible by 11.
Number N =
5 3 1 9 7 6 2
5-3+1-9+7-6+2 = -3 = 8 (mod 11)
isn't divisible by11.
Code: SN, PD in P=1000 (k=1 special) 1001 = 7*11*13
Compare with divisibility rule by 7
Formulae:
Number N is divisible by 11 iff remainder from division by 1001 is divisible by 11
number 10
There are two ordinary rules, common to all numbers.
Code: PD
P=8, (k=2)
Formulae:
Number N is divisible by 10 iff -2b+a is divisible by 10
Example:
P=8
Number N = 025750
-2( 2575)+0 =
-2(-2( 257+5)+0 =
-2(-2(-2( 25+7)+5)+0 =
-2(-2(-2(-2*2+5)+7)+5)+0 =
-2(-2(-2* 1+7)+5)+0 =
-2(-2* 5+5)+0
-2* 5+0 = 0 (mod 10)
is divisible by 10.
Code: PD
P=8, (k=2)
Formulae:
Number N is divisible by 10 iff -2b+a is divisible by 10
Example:
P=8
Number N = 025750
-2( 2575)+0 =
-2(-2( 257+5)+0 =
-2(-2(-2( 25+7)+5)+0 =
-2(-2(-2(-2*2+5)+7)+5)+0 =
-2(-2(-2* 1+7)+5)+0 =
-2(-2* 5+5)+0
-2* 5+0 = 0 (mod 10)
is divisible by 10.
number 9
Code: PU, SF
P=10 (k=1)
10b+a = b+a (mod 9)
Formulae:
Number N is divisible by 9 iff sum of digits is divisible by 9
Example:
Number N =
9 8 7 6 5 4 3 2 1 0
0+8+7+6+5+4+3+2+1+0 = 0 (mod 9)
is divisible by 9.
Number N =
7 0 4 1 2
7+0+4+1+2 = 5
isn't divisible by 9.
Code: PD
P=8 (k=1)
Formulae:
Number N is divisible by 9 iff alternating sum of digits is divisible by 9
Example:Number N =
7 6 5 4 3 2 1 4
-7+6-5+4-3+2-1+4 = 0
is divisible by 9.
Number N =
6 4 2 7 5 3 2
6-4+2-7+5-3+2 = 1
isn't divisible by 9.
P=10 (k=1)
10b+a = b+a (mod 9)
Formulae:
Number N is divisible by 9 iff sum of digits is divisible by 9
Example:
Number N =
9 8 7 6 5 4 3 2 1 0
0+8+7+6+5+4+3+2+1+0 = 0 (mod 9)
is divisible by 9.
Number N =
7 0 4 1 2
7+0+4+1+2 = 5
isn't divisible by 9.
Code: PD
P=8 (k=1)
Formulae:
Number N is divisible by 9 iff alternating sum of digits is divisible by 9
Example:Number N =
7 6 5 4 3 2 1 4
-7+6-5+4-3+2-1+4 = 0
is divisible by 9.
Number N =
6 4 2 7 5 3 2
6-4+2-7+5-3+2 = 1
isn't divisible by 9.
9/15/17
number 8
Code: SN
P=1000
1000b+a = 8*125b+a = a (mod 8)
Formulae:
Number N is divisible by 8 iff least significant digit is divisible by 8
Example:
N = 3 459 637 480 is divisible by 8 due 480=8*60.
N = 123 459 071 isn't divisible by 8.
Code: PU
P=10, (k=2)
10b+a = 2b+a
Formulae:
Number N is divisible by 8 iff 2b+a is divisible by 8.
Example:
Number N = 25712
2( 2571)+2 =
2(2( 257+1)+2 =
2(2(2( 25+7)+1)+2 =
2(2(2(2*2+5)+7)+1)+2 =
2(2(2* 1+7)+1)+2 =
2(2* 1+1)+2
2* 3+2 = 0 (mod 8)
is divisible by 8.
P=1000
1000b+a = 8*125b+a = a (mod 8)
Formulae:
Number N is divisible by 8 iff least significant digit is divisible by 8
Example:
N = 3 459 637 480 is divisible by 8 due 480=8*60.
N = 123 459 071 isn't divisible by 8.
Code: PU
P=10, (k=2)
10b+a = 2b+a
Formulae:
Number N is divisible by 8 iff 2b+a is divisible by 8.
Example:
Number N = 25712
2( 2571)+2 =
2(2( 257+1)+2 =
2(2(2( 25+7)+1)+2 =
2(2(2(2*2+5)+7)+1)+2 =
2(2(2* 1+7)+1)+2 =
2(2* 1+1)+2
2* 3+2 = 0 (mod 8)
is divisible by 8.
9/14/17
number 7
Source of some of these methods: Michał Szurek: Opowieści matematyczne, PWN Warszawa 1987
Code: SN in decimal P=10
Number N less than 1001=7*11*13 or remainder from division by this
c*100+b*10+a = (2*7^2+2)c+(7+3)*b+a = 2*c+3*b+a (mod 7)
Formulae:
Number N=cba is divisible by 7 iff 2c+3b+a is divisible by 7 (rule IV)
Example:
Number N = 455
2*4+3*5+5 = 28 = 4*7
is divisible by 7.
Number N= 942
2*9+3*4+2 = 32 = 4*7+4
isn't divisible by 7.
Division by 1001 as division by 7
Code: SN in decimal P=10
Number N=cba less than 1000.
100c+10b+a = (7*13+7+3-1)c+10b+a = 10(c+b)+(a-c) (mod 7)
Formulae:
Number N=cba is divisible by 7 iff (c+b)#(a-c) is divisible by 7. (rule III)
Sign '#' split digits into one two-digit number. Operations are modulo 7.
Example:
Number N =679
(6+7)#(9-6) = 63
is divisible by 7.
Number N= 391
(3+9)#(1-3) = 55
isn't divisible by 7.
Code: PD in P=1000 (k=1 special)
Division by 1001 each decimal digit separately greatly damp number N. Then use other method.
1000d+a = -d+a, the same with 1000e+b and 1000f+c
Formulae:
Number N is divisible by 7 iff number created by alternate sum every third digit is divisible by 7. (rule II)
Example:
Number N = 32 673 981 207
6-9+2 = -1 = 6 (mod 7)
-3+7-8+0 = -4 = 3 (mod 7)
-2+3-1+7 = 7 = 0 (mod 7)
If number 630 is divisible by 7, number N is divisible, too.
This allow get another rule:
Number 10^n+a is divisible by 7 iff number 10^(n+3)-a is divisible by 7. (rule VII)
Hint. Sum 10^n+a+10^(n+3)-a = 1001*10^n is divisible by 7.
Code: PD (k=1) CR P=100 (k=1/2)
f*10^(10)+e*10^8+d*10^6+c*10^4+b*100+a = 32f+16e+(7+1)d+4c+(2*49+2)b+a = 4(f+c)+2(e+b)+(d+a)
Formulae:
Number N is divisible by 7 iff 4(c)+2(b)+(a) reduced to number divisible by 7. (it is like rule IX, but it has other end)
Example:
Number N =
2 35 94 06 17 88 36 =
2 0 3 6 3 4 1 (mod 7)
(c) = 0+3 = 3 (mod 7)
(b) = 3+4 = 7 = 0 (mod 7)
(a) = 2+6+1 = 9 = 2 (mod 7)
4*(c)+2*(b)+(a) = 4*3+2*0+2 = 14 = 2*7, number N is divisible by 7.
The difference from original example is, that from 302 number 30 was reduced by 7 to 2 and this number was substract from 2 at end.
Code: PS, PU
P=10 (k=3)
10b+a = 3b+a (mod 7)
Formulae:
Number N is divisible by 7 iff 3b+a is divisible by 7. (rules VIII, X, V)
Example:
Number N = 25711
3( 2571)+1 =
3(3( 257+1)+1 =
3(3(3( 25+7)+1)+1 =
3(3(3(3*2+5)+7)+1)+1 =
3(3(3* 4+7)+1)+1 =
3(3* 5+1)+1
3* 2+1 = 0 (mod 7)
is divisible by 7.
There is so many rules in the source, because one of method is like presented don't using modulo operations (better for quotient), second changes powers of 10 into powers of 3 in positional system, and last is an determinant
| 3 1 |
|10-a b+1 |
equal 3b+a-7.
Code: PS
P=100
4*(100b+a) = 4*2b+4a = b+4a (mod 7)
Formulae:
Number N is divisible by 7 iff b+4a is divisible by 7. (rule I)
Example:
Number N = 138264
1382 + 4*64 = 1638
16 + 4*38 = 168
and use other method for 168.
We can use modulo operation to upgrade this method.
Code: PS, SF-
P=10, for SF- 2*10-3*7=-1 gets -b+2a
10b+a = 3b+a = 3b-6a = 3(b-2a) (mod 7)
Formulae Żbikowski theorem:
Number N is divisible by 7 iff b-2a is divisible by 7. (rule VI)
Example:
Number N = 646786
64678 -2*6 = 64666
6466 -2*6 = 6454
645 -2*4 = 637
63 -2*7 = 49
is divisible by 7.
Code: SF
P=10, 5*10-7*7=1
5(10b+a) = b+5a (mod 7)
Formulae:
Number N is divisible by 7 iff b+5a is divisible by 7.
Example:
Number N = 646786
64678 +5*6 = 64708
6470 +5*8 = 6510
651 +5*0 = 651
65 +5*1 = 70
is divisible by 7.
Code: PD
P=8, (k=1)
Formulae:
Number N is divisible by 7 iff sum of digits is divisible by 7
Example:
Number N =
7 6 5 4 3 2 4 0
7+6+5+4+3+2+4+0 = 3 (mod 7)
isn't divisible by 7.
Code: SN in decimal P=10
Number N less than 1001=7*11*13 or remainder from division by this
c*100+b*10+a = (2*7^2+2)c+(7+3)*b+a = 2*c+3*b+a (mod 7)
Formulae:
Number N=cba is divisible by 7 iff 2c+3b+a is divisible by 7 (rule IV)
Example:
Number N = 455
2*4+3*5+5 = 28 = 4*7
is divisible by 7.
Number N= 942
2*9+3*4+2 = 32 = 4*7+4
isn't divisible by 7.
Division by 1001 as division by 7
Code: SN in decimal P=10
Number N=cba less than 1000.
100c+10b+a = (7*13+7+3-1)c+10b+a = 10(c+b)+(a-c) (mod 7)
Formulae:
Number N=cba is divisible by 7 iff (c+b)#(a-c) is divisible by 7. (rule III)
Sign '#' split digits into one two-digit number. Operations are modulo 7.
Example:
Number N =679
(6+7)#(9-6) = 63
is divisible by 7.
Number N= 391
(3+9)#(1-3) = 55
isn't divisible by 7.
Code: PD in P=1000 (k=1 special)
Division by 1001 each decimal digit separately greatly damp number N. Then use other method.
1000d+a = -d+a, the same with 1000e+b and 1000f+c
Formulae:
Number N is divisible by 7 iff number created by alternate sum every third digit is divisible by 7. (rule II)
Example:
Number N = 32 673 981 207
6-9+2 = -1 = 6 (mod 7)
-3+7-8+0 = -4 = 3 (mod 7)
-2+3-1+7 = 7 = 0 (mod 7)
If number 630 is divisible by 7, number N is divisible, too.
This allow get another rule:
Number 10^n+a is divisible by 7 iff number 10^(n+3)-a is divisible by 7. (rule VII)
Hint. Sum 10^n+a+10^(n+3)-a = 1001*10^n is divisible by 7.
Code: PD (k=1) CR P=100 (k=1/2)
f*10^(10)+e*10^8+d*10^6+c*10^4+b*100+a = 32f+16e+(7+1)d+4c+(2*49+2)b+a = 4(f+c)+2(e+b)+(d+a)
Formulae:
Number N is divisible by 7 iff 4(c)+2(b)+(a) reduced to number divisible by 7. (it is like rule IX, but it has other end)
Example:
Number N =
2 35 94 06 17 88 36 =
2 0 3 6 3 4 1 (mod 7)
(c) = 0+3 = 3 (mod 7)
(b) = 3+4 = 7 = 0 (mod 7)
(a) = 2+6+1 = 9 = 2 (mod 7)
4*(c)+2*(b)+(a) = 4*3+2*0+2 = 14 = 2*7, number N is divisible by 7.
The difference from original example is, that from 302 number 30 was reduced by 7 to 2 and this number was substract from 2 at end.
Code: PS, PU
P=10 (k=3)
10b+a = 3b+a (mod 7)
Formulae:
Number N is divisible by 7 iff 3b+a is divisible by 7. (rules VIII, X, V)
Example:
Number N = 25711
3( 2571)+1 =
3(3( 257+1)+1 =
3(3(3( 25+7)+1)+1 =
3(3(3(3*2+5)+7)+1)+1 =
3(3(3* 4+7)+1)+1 =
3(3* 5+1)+1
3* 2+1 = 0 (mod 7)
is divisible by 7.
There is so many rules in the source, because one of method is like presented don't using modulo operations (better for quotient), second changes powers of 10 into powers of 3 in positional system, and last is an determinant
| 3 1 |
|10-a b+1 |
equal 3b+a-7.
Code: PS
P=100
4*(100b+a) = 4*2b+4a = b+4a (mod 7)
Formulae:
Number N is divisible by 7 iff b+4a is divisible by 7. (rule I)
Example:
Number N = 138264
1382 + 4*64 = 1638
16 + 4*38 = 168
and use other method for 168.
We can use modulo operation to upgrade this method.
Code: PS, SF-
P=10, for SF- 2*10-3*7=-1 gets -b+2a
10b+a = 3b+a = 3b-6a = 3(b-2a) (mod 7)
Formulae Żbikowski theorem:
Number N is divisible by 7 iff b-2a is divisible by 7. (rule VI)
Example:
Number N = 646786
64678 -2*6 = 64666
6466 -2*6 = 6454
645 -2*4 = 637
63 -2*7 = 49
is divisible by 7.
Code: SF
P=10, 5*10-7*7=1
5(10b+a) = b+5a (mod 7)
Formulae:
Number N is divisible by 7 iff b+5a is divisible by 7.
Example:
Number N = 646786
64678 +5*6 = 64708
6470 +5*8 = 6510
651 +5*0 = 651
65 +5*1 = 70
is divisible by 7.
Code: PD
P=8, (k=1)
Formulae:
Number N is divisible by 7 iff sum of digits is divisible by 7
Example:
Number N =
7 6 5 4 3 2 4 0
7+6+5+4+3+2+4+0 = 3 (mod 7)
isn't divisible by 7.
number 6
Code: PU
P=10 (k=4)
10b+a = 4b+a (mod 6)
Formulae:
Number N is divisible by 6 iff 4b+a is divisible by 6
Example:
Number N =
Number N = 98760 =
4( 9876 )+0 =
4(4( 987+6)+0 =
4(4(4( 98+7)+6)+0 =
4(4(4(4*9+8)+7)+6)+0 =
4(4( 2+7)+6)+0 =
4( 3+6)+0 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 176 =
4( 17)+6 =
4(4*1+7)+6 =
4* 5+6 = 2 (mod 6) isn't divisible by 6.
Code: PU
P=8 (k=2)
8b+a = 2b+a (mod 6)
Formulae:
Number N is divisible by 6 iff 2b+a is divisible by 6
Example:
Number N = 754 =
2( 75)+4 =
2(2*7+5)+4 =
2* 1+4 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 172 =
2( 17)+2 =
2(2*1+7)+2 =
2* 1+2 = 4 (mod 6) isn't divisible by 6.
Code: PD
P=4, (k=2)
4b+a = 6b-2b+a = -2b+a (mod 6)
Formulae:
Number N is divisible by 6 iff -2b+a is divisible by 6
Example:
Number N = 322 =
-2( 32)+2 =
-2(-2*3+2)+2 =
-2* 2+4 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 130 =
-2( 13)+0 =
-2(-2*1+3)+0 =
-2* 1+0 = -2 = 4 (mod 6) isn't divisible by 6.
P=10 (k=4)
10b+a = 4b+a (mod 6)
Formulae:
Number N is divisible by 6 iff 4b+a is divisible by 6
Example:
Number N =
Number N = 98760 =
4( 9876 )+0 =
4(4( 987+6)+0 =
4(4(4( 98+7)+6)+0 =
4(4(4(4*9+8)+7)+6)+0 =
4(4( 2+7)+6)+0 =
4( 3+6)+0 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 176 =
4( 17)+6 =
4(4*1+7)+6 =
4* 5+6 = 2 (mod 6) isn't divisible by 6.
Code: PU
P=8 (k=2)
8b+a = 2b+a (mod 6)
Formulae:
Number N is divisible by 6 iff 2b+a is divisible by 6
Example:
Number N = 754 =
2( 75)+4 =
2(2*7+5)+4 =
2* 1+4 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 172 =
2( 17)+2 =
2(2*1+7)+2 =
2* 1+2 = 4 (mod 6) isn't divisible by 6.
Code: PD
P=4, (k=2)
4b+a = 6b-2b+a = -2b+a (mod 6)
Formulae:
Number N is divisible by 6 iff -2b+a is divisible by 6
Example:
Number N = 322 =
-2( 32)+2 =
-2(-2*3+2)+2 =
-2* 2+4 = 0 (mod 6)
is divisible by 6.
Number N =
Number N = 130 =
-2( 13)+0 =
-2(-2*1+3)+0 =
-2* 1+0 = -2 = 4 (mod 6) isn't divisible by 6.
9/13/17
number 5
Code: SN
P=10
10b+a = 5*2b+a = a (mod 5)
Formulae:
Number N is divisible by 5 iff least significant digit is divisible by 5
Example:
N = 9876543210 is divisible by 5.
N = 2345678901 isn't divisible by 5.
Code: PD
P=4, (k=1)
Formulae:
Number N is divisible by 5 iff alternating sum of digits is divisible by 5
Example:
P=4
Number N =
1 1 2 0 0 1 2 3
-1+1-2+0-0+1-2+3 = 0
is divisible by 5.
Number N =
1 0 1 3 2 0 0
1-0+1-3+2-0+0 = 1
isn't divisible by 5.
Code: CR
multiply P by k=1/2 from decimal system
Formulae:
Number N is divisible by 5 iff least significant digit is 0
Example:
After conversion this is ordinary case where base is a divisor P=D. See first rule above.
It is mentioned, because this method allows get quotient N/5 as multiplication N by 2:
(b*10)/5 = 2*b
P=10
10b+a = 5*2b+a = a (mod 5)
Formulae:
Number N is divisible by 5 iff least significant digit is divisible by 5
Example:
N = 9876543210 is divisible by 5.
N = 2345678901 isn't divisible by 5.
Code: PD
P=4, (k=1)
Formulae:
Number N is divisible by 5 iff alternating sum of digits is divisible by 5
Example:
P=4
Number N =
1 1 2 0 0 1 2 3
-1+1-2+0-0+1-2+3 = 0
is divisible by 5.
Number N =
1 0 1 3 2 0 0
1-0+1-3+2-0+0 = 1
isn't divisible by 5.
Code: CR
multiply P by k=1/2 from decimal system
Formulae:
Number N is divisible by 5 iff least significant digit is 0
Example:
After conversion this is ordinary case where base is a divisor P=D. See first rule above.
It is mentioned, because this method allows get quotient N/5 as multiplication N by 2:
(b*10)/5 = 2*b
number 4
Code: SN
P=100
100b+a = 4*25b+a = a (mod 4)
Formulae:
Number N is divisible by 4 iff least significant digit is divisible by 4
Example:
N = 3 45 67 80 is divisible by 4 due 80=4*20.
N = 23 49 01 isn't divisible by 4.
Code: PU
P=10 (k=6=2 (mod 4) )
10b+a = (2*4+2)b+a = 2b+a (mod 4)
Formulae:
Number N is divisible by 4 iff 2b+a is divisible by 4
This method is practically the same as first, because P^2=100=4*25
Example:
Number N = 98764 =
2( 9876)+4 =
2(2( 987+6)+4 =
2(2(2( 98+7)+6)+4 =
2(2(2(2*9+8)+7)+6)+4 =
2(2(2* 2+7)+6)+4 =
2(2* 3+6)+4 =
2* 0+4 = 0 (mod 4)
is divisible by 4.
Code: PD
P=3, (k=1)
3b+a = 4b-b+a = -b+a (mod 4)
Formulae:
Number N is divisible by 4 iff alternating sum of digits is divisible by 4
Example:
P=3
Number N =
1 0 2 0 0 1 2 0
-1+0-2+0-0+1-2+0 = -4 = 4*(-1)
is divisible by 4.
Number N =
1 0 0 2 1 0 1
1-0+0-2+1-0+1 = 1
isn't divisible by 4.
P=100
100b+a = 4*25b+a = a (mod 4)
Formulae:
Number N is divisible by 4 iff least significant digit is divisible by 4
Example:
N = 3 45 67 80 is divisible by 4 due 80=4*20.
N = 23 49 01 isn't divisible by 4.
Code: PU
P=10 (k=6=2 (mod 4) )
10b+a = (2*4+2)b+a = 2b+a (mod 4)
Formulae:
Number N is divisible by 4 iff 2b+a is divisible by 4
This method is practically the same as first, because P^2=100=4*25
Example:
Number N = 98764 =
2( 9876)+4 =
2(2( 987+6)+4 =
2(2(2( 98+7)+6)+4 =
2(2(2(2*9+8)+7)+6)+4 =
2(2(2* 2+7)+6)+4 =
2(2* 3+6)+4 =
2* 0+4 = 0 (mod 4)
is divisible by 4.
Code: PD
P=3, (k=1)
3b+a = 4b-b+a = -b+a (mod 4)
Formulae:
Number N is divisible by 4 iff alternating sum of digits is divisible by 4
Example:
P=3
Number N =
1 0 2 0 0 1 2 0
-1+0-2+0-0+1-2+0 = -4 = 4*(-1)
is divisible by 4.
Number N =
1 0 0 2 1 0 1
1-0+0-2+1-0+1 = 1
isn't divisible by 4.
number 3
Code: PU
P=10 (k=7=1 (mod 3) ), P=4 (k=1)
Formulae:
Number N is divisible by 3 iff sum of digits is divisible by 3
Example:
P=10
Number N =
9 8 7 6 5 4 3 2 1 0
0+2+1+0+2+1+0+2+1+0 = 3*3
is divisible by 3.
P=4
Number N =
1 0 2 0 2
1+0+2+0+2 = 3*1+2
isn't divisible by 3.
Code: PD
P=2, (k=1)
Formulae:
Number N is divisible by 3 iff alternating sum of digits is divisible by 3
Example:
P=2
Number N =
1 0 0 0 0 1 0 0
-1+0-0+0-0+1-0+0 = 0
is divisible by 3.
Number N =
1 0 0 1 1 0 1
1-0+0-1+1-0+1 = 2
isn't divisible by 3.
P=10 (k=7=1 (mod 3) ), P=4 (k=1)
Formulae:
Number N is divisible by 3 iff sum of digits is divisible by 3
Example:
P=10
Number N =
9 8 7 6 5 4 3 2 1 0
0+2+1+0+2+1+0+2+1+0 = 3*3
is divisible by 3.
P=4
Number N =
1 0 2 0 2
1+0+2+0+2 = 3*1+2
isn't divisible by 3.
Code: PD
P=2, (k=1)
Formulae:
Number N is divisible by 3 iff alternating sum of digits is divisible by 3
Example:
P=2
Number N =
1 0 0 0 0 1 0 0
-1+0-0+0-0+1-0+0 = 0
is divisible by 3.
Number N =
1 0 0 1 1 0 1
1-0+0-1+1-0+1 = 2
isn't divisible by 3.
9/12/17
Conversions CR
Conversions allow calculate much smaller values.
1) Power k of base P.
A divisor has k digits in base P. When we change base into P^k, a divisor becomes one-digit number. They old digits split into one bigger digit in new system. Let i is a natural number or 0. We group digits:
a_{ki+k-1}*P^{ki+k-1} + ... + a_{ki+1}*P^{ki+1} + a_{ki}*P^{ki} = (a_{ki+k-1}*P^{k-1}+...+a_{ki+1}*P+a_{ki})*P^{ki}
Example:
Decimal system. Let change into a system with base P=1000=10^3. Split neighboring three digits into one as follow:
N = 9876543210.
New base P=1000 put N = 9 876 543 210, it has only four digits, three of them have three digits in decimal system.
2) Multiply base P by k
Every digit divide by power k^i, which is position of digit a_i.
a_n*P^n + ... + a_1*P + a_0 = a_n*k^{-n}*Q^n +...+a_1*k^{-1}*Q + a_0
where Q = P*k.
There are some method to avoid fraction. In most of them they are shift remainder from division a_i from k to less significant digit.
We can add P into digit, that changes value of N. Below is a method, it saves values of N.
Let use two lists B=[a_n], A=[a_{n-1}, ..., a_1, a_0] and use current algorithm:
1.multiply k*P with remainders by division digit by k and move they to next number of list, last number put into C;
2. divide all digits from B by k - it's possible now (write as []/5#[step 3.]);
3. take first digit from A, put it at the end of B increased by P*C;
4. stop when A is empty, else goto 1.
In list B is number with base kP, in list A is number with base P.
Example:
Decimal system
Write number N = 6542 with base P=50. k=5 (=50/10)
start: B=[6], C=?, A=[5,4,2]
B=[5]/5#[1*10+5]=[1,15], C=1, A=[4,2]
B=[0,65]/5#[4]=[0,13,4], C=0, A=[2]
B=[0,10,150]/5#[4*10+2]=[0,2,30,42], C=4, A=[]
From list B comes number N = 2 30 42 with base P=50.
There is other way to get a number in such system. In digits are multiples like above, and remainders shifts and increase less significant digit.
A list contains the first digits the last of them is separate. This digits moves out list into list of digits of number N. Now all values in list are divided by k. Use recursion until list is empty or has zeros only. A number N contains digits they abandon list, it is in new base.
Example anew:
Decimal number N=6542 into base P=5*10.
[6, 5, 4 | 2] = [5, 15, 0 | 42] = 5*[1, 3, 0] 42
[1, 3 | 0] = [0, 10 | 30] = 5*[0, 2] 30
[0 | 2] = [0] 2
It is number N = 2 30 42 with base 50.
3) Add integer k to base P
Expression a_n*P^n+...+a_1*P+a_0 transforms into
b_m*(P+k)^m+...+b_1*(P+k)+b_0
Let use two list B=[a_n], A=[a_{n-1},...,a_1, a_0] like above.
1. move first digit from A to the end of B;
2. for all digits in B do:
this = this - k*previous,
if previous doesn't exists, take 0
3. repair digits by addiction, subtraction (P+k) and decrement / increment previous number (they are in colour in example);
4. stop when A is empty, else goto 1.
This method is a kernel of [PU] or [PD]. It works especially good with bigger values P. There is number in list B with base (P+k).
Example:
Decimal system.
Number N = 951 transform to base P=8. Calculate k=8-10=-2.
start: B=[9], A=[5,1]
B = [9, 5-(-2)*9] = [9, 23] = [0+1,9-8+2, 23-2*8] = [1,3,7], A=[1]
B=[1, 3-(-2)*1, 7-(-2)*3, 1-(-2)*7] = [1,5+1,8-8+5+1,8-8+7] = [1,6,6,7], A=[]
There is number N = 01667 in list B, in decimal system still N = 951.
1) Power k of base P.
A divisor has k digits in base P. When we change base into P^k, a divisor becomes one-digit number. They old digits split into one bigger digit in new system. Let i is a natural number or 0. We group digits:
a_{ki+k-1}*P^{ki+k-1} + ... + a_{ki+1}*P^{ki+1} + a_{ki}*P^{ki} = (a_{ki+k-1}*P^{k-1}+...+a_{ki+1}*P+a_{ki})*P^{ki}
Example:
Decimal system. Let change into a system with base P=1000=10^3. Split neighboring three digits into one as follow:
N = 9876543210.
New base P=1000 put N = 9 876 543 210, it has only four digits, three of them have three digits in decimal system.
2) Multiply base P by k
Every digit divide by power k^i, which is position of digit a_i.
a_n*P^n + ... + a_1*P + a_0 = a_n*k^{-n}*Q^n +...+a_1*k^{-1}*Q + a_0
where Q = P*k.
There are some method to avoid fraction. In most of them they are shift remainder from division a_i from k to less significant digit.
We can add P into digit, that changes value of N. Below is a method, it saves values of N.
Let use two lists B=[a_n], A=[a_{n-1}, ..., a_1, a_0] and use current algorithm:
1.multiply k*P with remainders by division digit by k and move they to next number of list, last number put into C;
2. divide all digits from B by k - it's possible now (write as []/5#[step 3.]);
3. take first digit from A, put it at the end of B increased by P*C;
4. stop when A is empty, else goto 1.
In list B is number with base kP, in list A is number with base P.
Example:
Decimal system
Write number N = 6542 with base P=50. k=5 (=50/10)
start: B=[6], C=?, A=[5,4,2]
B=[5]/5#[1*10+5]=[1,15], C=1, A=[4,2]
B=[0,65]/5#[4]=[0,13,4], C=0, A=[2]
B=[0,10,150]/5#[4*10+2]=[0,2,30,42], C=4, A=[]
From list B comes number N = 2 30 42 with base P=50.
There is other way to get a number in such system. In digits are multiples like above, and remainders shifts and increase less significant digit.
A list contains the first digits the last of them is separate. This digits moves out list into list of digits of number N. Now all values in list are divided by k. Use recursion until list is empty or has zeros only. A number N contains digits they abandon list, it is in new base.
Example anew:
Decimal number N=6542 into base P=5*10.
[6, 5, 4 | 2] = [5, 15, 0 | 42] = 5*[1, 3, 0] 42
[1, 3 | 0] = [0, 10 | 30] = 5*[0, 2] 30
[0 | 2] = [0] 2
It is number N = 2 30 42 with base 50.
3) Add integer k to base P
Expression a_n*P^n+...+a_1*P+a_0 transforms into
b_m*(P+k)^m+...+b_1*(P+k)+b_0
Let use two list B=[a_n], A=[a_{n-1},...,a_1, a_0] like above.
1. move first digit from A to the end of B;
2. for all digits in B do:
this = this - k*previous,
if previous doesn't exists, take 0
3. repair digits by addiction, subtraction (P+k) and decrement / increment previous number (they are in colour in example);
4. stop when A is empty, else goto 1.
This method is a kernel of [PU] or [PD]. It works especially good with bigger values P. There is number in list B with base (P+k).
Example:
Decimal system.
Number N = 951 transform to base P=8. Calculate k=8-10=-2.
start: B=[9], A=[5,1]
B = [9, 5-(-2)*9] = [9, 23] = [0+1,9-8+2, 23-2*8] = [1,3,7], A=[1]
B=[1, 3-(-2)*1, 7-(-2)*3, 1-(-2)*7] = [1,5+1,8-8+5+1,8-8+7] = [1,6,6,7], A=[]
There is number N = 01667 in list B, in decimal system still N = 951.
Algorithm PU
This algorithm works like algorithm PD, it is only one difference with destinations, this means sign in operation. The base P is bigger than divisor D.
Now the unpaired step use other operator:
do from most signicicant digit
add to next digit (+ this*R)
until we take the least significant one;
Example in decimal system:
358 / 7
we multiply by 7-10=-3 each numbers (in this algorithm we substract negative, so add), they we get from digit of number. We can upgrade this and take the number nearer zero. The last number /digit is the remainder from division.
3
3*3+5 = 14 = 0 (mod 7)
3*0+8 = 8 = 1 (mod 7)
This method allows get quotient, until we be very caution, verify all changes of digits and repair becoming list of numbers.
In this example we got list [3, 0, 1] in decimal, but we used some congruences inside. The list for quotient looks as follow
[3, 2*7+0, 1*7+1] = [3+2, 0+1, 1] = [5,1,1]
and returns a quotient 51 and remainder 1.
Now the unpaired step use other operator:
do from most signicicant digit
add to next digit (+ this*R)
until we take the least significant one;
Example in decimal system:
358 / 7
we multiply by 7-10=-3 each numbers (in this algorithm we substract negative, so add), they we get from digit of number. We can upgrade this and take the number nearer zero. The last number /digit is the remainder from division.
3
3*3+5 = 14 = 0 (mod 7)
3*0+8 = 8 = 1 (mod 7)
This method allows get quotient, until we be very caution, verify all changes of digits and repair becoming list of numbers.
In this example we got list [3, 0, 1] in decimal, but we used some congruences inside. The list for quotient looks as follow
[3, 2*7+0, 1*7+1] = [3+2, 0+1, 1] = [5,1,1]
and returns a quotient 51 and remainder 1.
9/11/17
Algorithm with congruence SF
Stephen Froggatt indicates in Math Forum an equation, it can help in finding remainders Divisibility Rules to 50 and Beyond.
His explanation is as follow (divisibility by 7 in decimal):
Assume, that 10b+a = 7k.
Then b+5a = b+5(7k-10b) = 35k-49b = 7(5k-7b).
But where are 5 get from?
There exists a numbers M, K and formula
M*P - K*D = 1
for base P and divisor D. Let M is as small positive as possible.
Then the number N is split into two parts, b is N with cutting least significant digit off, and this digit a.
This equation is equivalent to congruence
M*P = 1 (mod D)
Such case
N*M = (b*P+a)M = b(P*M)+a*M = b*1 + a*M = b+aM (mod D)
In mentioned example we check: 10=3 (7), 20=-1 (7), 30=2 (7), 40=5 (7), 50=1(7) it is this, M=5.
Number N is divisible by D iff b+M*a is divisible by D.
Congruence allows the second formulae, when M is bigger than half D. Simply decrease M by D:
Number N is divisible by D iff b+(M-D)*a is divisible by D.
Upgrade [SF-]
We can use congruence
M*P = -1 (mod D)
Such case there is
N*M = -b+aM = -(b-aM) (mod D)
This method doesn't detect quotient N / D.
His explanation is as follow (divisibility by 7 in decimal):
Assume, that 10b+a = 7k.
Then b+5a = b+5(7k-10b) = 35k-49b = 7(5k-7b).
But where are 5 get from?
There exists a numbers M, K and formula
M*P - K*D = 1
for base P and divisor D. Let M is as small positive as possible.
Then the number N is split into two parts, b is N with cutting least significant digit off, and this digit a.
This equation is equivalent to congruence
M*P = 1 (mod D)
Such case
N*M = (b*P+a)M = b(P*M)+a*M = b*1 + a*M = b+aM (mod D)
In mentioned example we check: 10=3 (7), 20=-1 (7), 30=2 (7), 40=5 (7), 50=1(7) it is this, M=5.
Number N is divisible by D iff b+M*a is divisible by D.
Congruence allows the second formulae, when M is bigger than half D. Simply decrease M by D:
Number N is divisible by D iff b+(M-D)*a is divisible by D.
Upgrade [SF-]
We can use congruence
M*P = -1 (mod D)
Such case there is
N*M = -b+aM = -(b-aM) (mod D)
This method doesn't detect quotient N / D.
Algorithm PD
Let base P is a smaller than divisor D.
The conversion add P+(D-P) from base P into base D gets the remainder from division into least significant digit. These conversion decreases current digit by multiplication a difference R=D-P with previous digit. Then we cut the least significant number off and reconvert to base P. These algorithms are inverse, but there is one unpaired step in the middle during division.
The first conversion algorithm is publicized in special case R=2 in MJM on June 2014 Conversion of number systems and factorization [pdf]. The second has negate R.
This step can be expressed as follow:
do from most significant digit
add (- R*this) to next digit / number
until we take the least significant one;
Example in decimal system:
358 / 12
multiply by 12-10=2 each numbers, they we get from digit of number. The last is the remainder from division.
3
-2* 3+5 = -1
-2*(-1)+8 = 10
This method allows get quotient, but ones must be very cautious, verify all changes of digits and repair becoming list of numbers.
In this example we got list [3, -1, 10] in decimal, which is translated into
3*10-1 with remainder 10, so quotient is 29.
The conversion add P+(D-P) from base P into base D gets the remainder from division into least significant digit. These conversion decreases current digit by multiplication a difference R=D-P with previous digit. Then we cut the least significant number off and reconvert to base P. These algorithms are inverse, but there is one unpaired step in the middle during division.
The first conversion algorithm is publicized in special case R=2 in MJM on June 2014 Conversion of number systems and factorization [pdf]. The second has negate R.
This step can be expressed as follow:
do from most significant digit
add (- R*this) to next digit / number
until we take the least significant one;
Example in decimal system:
358 / 12
multiply by 12-10=2 each numbers, they we get from digit of number. The last is the remainder from division.
3
-2* 3+5 = -1
-2*(-1)+8 = 10
This method allows get quotient, but ones must be very cautious, verify all changes of digits and repair becoming list of numbers.
In this example we got list [3, -1, 10] in decimal, which is translated into
3*10-1 with remainder 10, so quotient is 29.
Positional system
A natural number is a list of digits. Each digits is a coefficient in section [0,P), where P is called base of positional system.
Assume, that P is common to all positions of number. Then the number with digits can be expressed as:
N = a_n * P^n + a_{n-1} * P^(n-1) + ... + a_2 * P^2 + a_1 * P + a_0.
A digit a_n is called most significant digit, and a_0 least significant digit.
Sometimes there is other expression, which is a bit better to calculate, called Hörner schema. The powers are hidden due the brackets in this view:
N = (((...(a_n * P + a_{n-1})*P+...)+ a_2)*P+a_1)*P+a_0.
In this blog this schema is preferred.
To avoid indexes, in blog digits are written a=a_0, b=a_1 etc. We often use recursion, and expression
N = b*P+a
means also
N'*P+a
where N' is a number (N-a_0)/P .
Examples:
P=10. This is the most using positional system.
P=2. This is binary system, which is used inside processors.
Assume, that P is common to all positions of number. Then the number with digits can be expressed as:
N = a_n * P^n + a_{n-1} * P^(n-1) + ... + a_2 * P^2 + a_1 * P + a_0.
A digit a_n is called most significant digit, and a_0 least significant digit.
Sometimes there is other expression, which is a bit better to calculate, called Hörner schema. The powers are hidden due the brackets in this view:
N = (((...(a_n * P + a_{n-1})*P+...)+ a_2)*P+a_1)*P+a_0.
In this blog this schema is preferred.
To avoid indexes, in blog digits are written a=a_0, b=a_1 etc. We often use recursion, and expression
N = b*P+a
means also
N'*P+a
where N' is a number (N-a_0)/P .
Examples:
P=10. This is the most using positional system.
P=2. This is binary system, which is used inside processors.
Number 2
Code: PS, PU in decimal system with k=8=0 (mod 2)
P is even
Formulae:
Number N is divisible by 2 iff least significant digit is divisible by 2 (even)
Example:
P=10
They are digits divisible by 2: 0, 2, 4, 6, 8
Number N = 9876543210 is divisible by 2.
P=2
Number N=1010000110110001 isn't divisible by 2.
Code: PS, PD in P=3 with k=1
P is odd
Formulae:
Number N is divisible by 2 iff sum parity of digits is even
Example:
P=9
Number N =
8 7 6 5 4 3 2 1 0
0+1+0+1+0+1+0+1+0 = 4 = 2*2
Number is even. It's divisible by 2.
P = 11
Number N =
6 5 4 3 10 9 8 7 1 2 0
0+1+0+1+ 0+1+0+1+1+0+0 = 5 (parity of digits)
Number 5 is odd. Number N isn't divisible by 2.
P is even
Formulae:
Number N is divisible by 2 iff least significant digit is divisible by 2 (even)
Example:
P=10
They are digits divisible by 2: 0, 2, 4, 6, 8
Number N = 9876543210 is divisible by 2.
P=2
Number N=1010000110110001 isn't divisible by 2.
Code: PS, PD in P=3 with k=1
P is odd
Formulae:
Number N is divisible by 2 iff sum parity of digits is even
Example:
P=9
Number N =
8 7 6 5 4 3 2 1 0
0+1+0+1+0+1+0+1+0 = 4 = 2*2
Number is even. It's divisible by 2.
P = 11
Number N =
6 5 4 3 10 9 8 7 1 2 0
0+1+0+1+ 0+1+0+1+1+0+0 = 5 (parity of digits)
Number 5 is odd. Number N isn't divisible by 2.
Subscribe to:
Comments (Atom)