Posts Tagged ‘Divisibility’

Monday Math 137

September 27, 2010

Let n be the product of three consecutive positive integers. Show that there is an integer s, greater than the smallest of the consecutive integers, such that n is divisible by s2-1.
Solution:

Advertisements

Monday Math 83

August 3, 2009

Previously, I talked about expressing fractions as decimals. I showed how to determine if a fraction gives a terminating decimal, a pure repeating decimal, or a mixed repeating decimal. I also showed how to determine the number of digits in a terminating decimal from the denominator of the fraction.
Now, let us consider the number of digits that repeat in a pure repeating decimal.

Let us first consider a pure repeating decimal with a one-digit repeat, for example 0.55555…
Let our repeating decimal be x. If we multiply it by ten, we still have the same repeating sequence after the decimal point, but we also now have one occurence of it to the left of the decimal point:
If x=0.5555…, then 10x=5.55555…
Now, then we can subtract x from our 10x, thus removing everything to the right of the decimal point:
10xx=(5.555…)-(0.555…)=5
But this gives us 9x, and thus x is the repeated digit over 9:
0.55555…=5/9. Similarly, 0.6666…=6/9=2/3, and so on.

Now, for a repeat of two digits, one can multiply by 100, to obtain one repeat to the left of the decimal point, and subtract the original number to get an integer. In general, let us consider a pure repeating decimal which repeats n digits. Let a be the integer formed by the repeated digits; e.g. for 0.148148148…, n=3 and a=148. Then our number is
.
And, the series at the end is a geometric series, so we see
,
so that
.
For example, 0.148148148…=148/(103-1)=148/999=4/27.
Now, we have a way of quickly converting a pure repeating decimal into a fraction. However, it also tells us something about the reverse; namely that a fraction that converts to a pure repeating decimal with an n digit repeat must have a denominator which divides 10n-1. More specifically, the length of the repeat for a pure repeating decimal is the smallest n such that the denominator divides 10n-1. For example, 1/37: 37 does not divide 9 or 99, but does divide 999=27*37, so 1/37 has a three-digit repeat as a decimal (1/37=27/999=0.027027027…).

Monday Math 82

July 27, 2009

Consider writing a proper fraction (a positive rational number less than 1), in lowest terms, as a decimal. As many people learn in their mathematics education, there are three possible outcomes:
I). Terminating Decimal
One has a finite sequence of digits after the decimal point (followed by a non-written infinite sequence of zeroes).
Examples: 1/2=0.5, 1/8=0.125, 1/200=0.005
II). Pure Repeating Decimal
One has a finite sequence of digits which repeats infinitely many times after the decimal point.
Examples: 1/3=0.333333…, 1/7=0.142857142857…, 1/33=0.03030303…
III). Mixed Repeating Decimal
One has a finite sequence of non-repeating digits followed by infinite repeats of a different digit sequence.
Examples: 1/6=0.166666…, 1/22=0.0454545…, 43/180=0.23888888…

How do we determine which of these a given fraction will have without performing the division to actually compute the result? Let’s first examine the terminating decimals.
The digits of a decimal represent multiples of negative powers of 10. For our examples:
0.5=(5/10)=1/2, 0.125=(1/10)+(2/100)+(5/1000)=125/1000=1/8, and 0.005=(0/10)+(0/100)+(5/1000)=5/1000=1/200.
So we see the common denominator of the fractions represented by the digits of the decimal is that of the rightmost digit; if we have n digits, the common denominator is 10n. Thus, the denominator of our fraction must divide this power of 10: 2|10, 8|1000, 200|1000. In fact, we see that 10n is the smallest power of 10 which is divisible by our fraction denominator.
From this, we then obtain the condition for a fraction to give a terminating decimal: there must be a power of 10 divisible by the denominator of the fraction (in lowest terms). This occurs only if the denominator’s prime factors are 2 and/or 5: 2=2, 8=23, 200=23*52. Note that the highest power of 2 and/or 5 in the prime factorization of the denominator is the number of digits n

Examination of the prime factorizations of the denominators of pure repeating decimals versus mixed repeating decimals will give us the distinguishing element:
the denominators of fractions that give pure repeating decimals are coprime with 10; they are divisible by neither 2 nor 5. For the mixed repeating decimals, the denominator is divisible by 2 and/or 5, but the prime factorization also contains other primes. From our examples:
6=2*3, 22=2*11, 180=22*32*5.

Note that for the mixed repeating decimals, the fraction denominators can be factored into the product of a number which divides a power of 10 and a number coprime with 10. For example 6=2*3, 22=2*11, 180=20*9. If we call the number which divides the power of 10 a and the number coprime with 10 b then our mixed repeating decimal has as many non-repeating digits as the terminating decimal 1/a and a repeated sequence of the same length as the repeated sequence of 1/b:
1/6: 1/2=0.5 has one digit, 1/3=0.333… has a one-digit repeat, so 1/6=0.16666 has one non-repeating digit and one repeating.
1/22: 1/2=0.5 has one digit, 1/11=0.090909… has a two-digit repeat, so 1/22=0.0454545 has one non-repeating digit and two repeating.
43/180: 1/20=0.05 has two digits, 1/9=0.1111… has a one-digit repeat, so 43/180=0.23888… has two non-repeating digits and one repeating.

Monday Math 65

March 30, 2009

Divisibility Tests Part 5: Tests for 13

Divisibility tests for 13 are also quite rare, however we can create a test analogous to our first for 7.

We note that 9*10+1=91=7*13, so with n=10a+b and q=a-9b, we see
,
so 9n+q is a multiple of 13, which means that n is divisible by 13 if and only if q is divisible by 13. This gives us the test: mulitply the ones digit of our number by 9, and subtract from the number formed by the rest of the digits. We see that this doesn’t work well for two-digit numbers, but a little better for three- or four-digit numbers.
For example:
n=78
7-8*9=-65=-5*13
n=182
18-2*9=0=0*13
n=507
50-7*9=-13
n=3679
367-9*9=286
28-9*6=-26=-2*13
so all of these numbers are divisible by 13.

As with 7, this procedure may be laborious for very large numbers. However, we can see that
1001=7*143=7*11*13=77*13
This means 1000=13*77-1, and so we see our large-number divisibility test for 7 also works for 13.
Thus, we split our large number into sets of three digits, and then take the alternating sum of these numbers. For example:
n=348,970,129,352
352-129+970-348=845
84-5*9=39=3*13
so 348,970,129,352 is divisible by 13
n=4,626,145,317,014,712
712-14+317-145+626-4=1492
149-2*9=131=13*10+1, which is not divisible by 13,
so 4,626,145,317,014,712 is not divisible by 13.

Monday Math 64

March 23, 2009

Divisibility Tests Part 4: Tests for 7

One generally does not see tests for divisibility by 7, as these aren’t as simple or quick as the more common tests. However, tests do exist.

First, let us consider two numbers a and b, and examine n=10a+b, q=a-2b. In particular,
, so 2n+q is a multiple of 7, which means that n is divisible by 7 if and only if q is divisible by 7. This gives us the following test: mulitply the ones digit of our number by 2, and subtract from the number formed by the rest of the digits.
For example:
n=42
4-2*2=0=0*7
n=49
4-2*9=4-18=-14=-2*7
n=301
30-2*1=28=4*7
so all of these numbers are divisible by 7.
For large numbers, we can repeat the test:
n=41,237
4123-2*7=4109
410-2*9=392
39-2*2=35=5*7,
so 41,237 is divisible by 7 (41,237=7*5891)

Note that for very large numbers, the procedure may be laborious. However, we can develop a second test by noting that
1001=7*143
This means 1000=7*143-1, and so:

,
and so on, so that
is divisible by 7 for all non-negative integers k. This creates a test by analogy to our divisibility test for 11.
Thus, we split our large number into sets of three digits, and then take the alternating sum of these numbers. For example:
n=348,967,129,356,874
874-356+129-967+348=28=4*7
so 348,967,129,356,874 is divisible by 7.
We can also combine the tests:
n=1,626,145,217,013,712
712-13+217-145+626-1=1596
159-2*6=147=21*7
so 1,626,145,217,013,712 is divisible by 7

Monday Math 63

March 16, 2009

Divisibility tests Part 3: 11

Last time, we proved the tests for divisibility by 3 and 9. Now, for 11, we again use the factoring rule . We also use the rule that if n is odd.
The first tells us , and so is divisible by 11 (as 99=11*9) for even k.
The second tells us that
.
So is divisible by 11 for all non-negative integers k.
So we consider the alternating sum . The difference between n and a is then
, and as each term of the series is divisible by 11, the difference is a multiple of 11. Thus, n is divisible by 11 if and only if a is a multiple of 11.

An few examples of this test:
n=297: 7-9+2=0=0*11, so 297 is divisible by 11 (297=27*11)
n=12,529:
9-2+5-2+1=11 (12,529=1139*11)
n=4,596,836:
6-3+8-6+9-5+4=13, so 4,596,836 is not divisible by 11.
n=94,949,690:
0-9+6-9+4-9+4-9=-22=-2*11, so 94,949,690 is divisible by 11 (94,949,690=8,631,790*11).

Monday Math 62

March 9, 2009

Divisibility Tests
Part 2: 3 and 9

One may know that the tests for divisibility by 3 and 9 involve adding the digits of a number: a number is divisible by 3 if and only if the sum of its digits is divisible by 3, and divisible by 9 if and only if the sum of its digits is divisible by 9.
The key is to recall the factoring rule , used to prove the geometric series formulas. This means that . (This just means 9, 99, 999, 9999, etc. are all multiples of 9, which should be quite obvious).
Let us consider an integer n. Let a0 be the ones digit, a1 the tens digit, a2 the hundreds digit, and so on, with am the highest digit, so that n is an (m+1)-digit number. This means
. The sum of the digits, in turn, is . The difference between these two is
.
As this is a multiple of 9, we see that n is divisible by 9 if and only if s is divisible by 9, and as a multiple of 9 is also a multiple of 3, n is divisible by 3 if and only if s is divisible by 3.

Monday Math 61

March 2, 2009

Divisibility Tests
Part 1: Factors of powers of 10

A common topic in mid-level aritmetic are tests to determine whether a number is divisible by a given small integer without needing to perform a full division; for example, that a number is divisible by nine if and only if the sum of its digits is also a multiple of nine. Proving these rules, however, can involve a bit of higher level math, such as modular arithmetic or other number-theoretic reasoning. Today, I will consider the simplest of divisibility tests; those for factors of powers of ten, which are simple due to our use of the base-ten number system.

First, divisiblity by ten is simply detemined by whether or not the ones digit is zero; divisiblity by 100; by whether the ones and tens digits are both zero; and so on. The reason is obvious.
Next, we see that divisibilty by the factors of 10, 2 and 5, also depend only on the ones digit: a number is divisible by 2 (even) if and only if the ones digit is even, and a number is divisible by five if and only if the ones digit is 0 or 5.

Those numbers which divide 100 but not 10 divide a number only if they divide the last two digits. This gives us the rules for 4, 20, 25, and 50.

For numbers dividing 1000 but not 100, we test the last three digits. This gives the tests for 8, 40, 125, 200, 250, and 500.

And so on. These, as we can see, are simple, and are obvious consequences of our base-ten system.