pgdivbyn1.html

Divisibility 1

Hints | Answers | Solutions

1 A conjecture from arithmetic

You might know almost at a glance that 10¹¹ - 1 is evenly divisible by 9, but how could you tell quickly what, if anything, 7¹¹ - 1 is evenly divisible by? First, look for a pattern.

Show that 10¹¹ - 1 and 10⁷ - 1 are both divisible by 9. Give a solid explanation why 1 less than any power of 10 must be divisible by 9.
Compute 6³ - 1 and 6⁷ - 1 and find a small (one-digit) factor that both have in common. Are 6² - 1 and 6⁵ - 1 also divisible by that factor?
Can you show why that factor divides all numbers of the form 6ⁿ - 1 (where n is a whole number)?
Calculate 3ⁿ -1 for several values of n. Explain why these are all divisible by 2.
Calculate 11² - 1, 11³ - 1, 11⁴ - 1, and 11⁵ - 1 and find the largest obvious common factor. Unless you use fancy software, you probably can’t conveniently calculate 11³⁷, but you might be able to explain why 11³⁷ - 1 ends with a zero. That will go a long way toward helping you show that 11ⁿ - 1 is always divisible by.... Explain.
Numbers of the form 10ⁿ - 1 had 9 as a common factor; numbers like 3ⁿ - 1 had 2 as a common factor; you found a common factor in 6ⁿ - 1; and you also found a common factor in 11ⁿ - 1. What’s the pattern here? State a conjecture of the form “If you subtract 1 from any power of some number a, the result is divisible by....”

2 A proof from algebra

The rest of this problem set is devoted to proving that the pattern you’ve seen for 3ⁿ - 1, 6ⁿ - 1, 10ⁿ - 1, and 11ⁿ - 1 holds true for all numbers of the form aⁿ - 1.

1. Multiply (x - 1)(x + 1).
2. Multiply (x - 1)(x² + x + 1).
3. Multiply (x - 1)(x³ + x² + x + 1).
1. Multiply x(x⁵ + x⁴ + x³ + x² + x + 1).
2. Multiply -1 × (x⁵ + x⁴ + x³ + x² + x + 1).
3. Multiply (x - 1)(x⁵ + x⁴ + x³ + x² + x + 1).
1. Multiply x(x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1).
2. Multiply (-1)(x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1).
3. Multiply (x - 1)(x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1).
If you have worked carefully, you will see a pattern.
Explain why products like $8 7 6 5 4 3 2 (x- 1)(x + x + x + x + x + x + x + x + 1)$ always have only two terms, and say what those two terms must be.
On the basis of your pattern, what are and ? Show the computation that proves you are correct.
Why must x1 in this problem?
And now, the pièce de résistance.
1. Explain why aⁿ - 1 can always be factored (if n is an integer and n > 1), and give an illustrative example.
2. Relate this back to problem 5 in section 1.

3 Epilogue: An application to arithmetic

This result also explains why a whole number whose digits add up to a multiple of 9 must, itself, be a multiple of 9.

For example, the sum of the digits in the number 142857 is 1 + 4 + 2 + 8 + 5 + 7 = 27.
27 is divisible by 9, so 142857 must be divisible by 9. (142857 = 9 ^. 3 ^. 13 ^. 407)

If 10ⁿ - 1 is divisible by 9, then 10ⁿ must not be divisible by 9. What is the remainder when you divide 10ⁿ by 9? Explain how you know that’s true.
If b is a whole number less than 9, then b × 10ⁿ is not divisible by 9. What is the remainder when you divide b × 10ⁿ by 9? Explain how you know.
If b and c are both whole numbers and each of them is less than 5, show what the remainder is when you divide b×10⁵+c×10³ by 9. Show that you get the same remainder if you divide c × 10⁷ + b × 10⁶ by 9.
If b + c = 9, what remainder do you get when you divide b × 10⁵ + c × 10³ by 9? Explain why.
Extend your explanation to work for five-digit numbers. Without actually dividing, predict the remainder when 26453 is divided by 9. Tell whether 1350243 is divisible by 9 or not.

Hints

Problem | Answers | Solutions

1 A conjecture from arithmetic

Hint to problem 1. Look at numbers of the form 10ⁿ.
Hint to problem 2. Show why the units digits of 6³, 6⁷, 6² and 6⁵ are the same.
Hint to problem 3. Are powers of 3 odd or even?
Hint to problem 4. What is the units digit of any power of 11?

2 A proof from algebra

Hint to problem 5. If = c then cb = a.

What correspond to a, b, and c in this problem?

3 Epilogue: An application to arithmetic

Hint to problem 1. 10ⁿ is 1 more than 10ⁿ - 1, a multiple of 9, so...
Hint to problem 4.

5 3 b× 10 + c × 10 = b(9m + 1) + c(9n + 1) = 9(mb + nc) + (b + c) = ...

Hint to problem 5. Dividing 26453 is like dividing each of 20000, 6000, 400, 50, and 3 by 9. The remainders of the divisions, taken separately, are 2, 6, 4, 5, and 3.

Answers

Problem | Hints | Solutions

1 A conjecture from arithmetic

Numbers of the form 10ⁿ are written as a 1 followed by n zeros (for example, 10⁷ = 10,000,000). So numbers of the form 10ⁿ - 1 consist of n 9s (for example, 10⁷ - 1 = 9,999,999). These are all obviously divisible by 9.
6³-1 = 215, 6⁷-1 = 279935, 6²-1 = 35 and 6⁵-1 = 7775, all divisible by 5.
All powers of 3 must be odd. Subtracting 1 makes them even. So 3ⁿ - 1 is always divisible by 2.
11² - 1 = 120, 11³ - 1 = 1330, 11⁴ - 1 = 14640, and 11⁵ - 1 = 161050. These are all multiples of 10. In fact, the units digit of all powers of 11 must be 1, so 11ⁿ - 1 is always divisible by 10.
So far, it seems that numbers of the form aⁿ - 1 are divisible by a - 1. “If you subtract 1 from any power of some number a, the result is divisible by a - 1.”

2 A proof from algebra

$(x - 1)(x + 1) = (x2 + x) + (- x - 1) = x2 - 1 (x- 1)(x2 + x + 1) = (x3 + x2 + x) + (- x2 - x - 1) = x3 - 1 (x- 1)(x3 + x2 + x + 1) = (x4 + x3 + x2 + x) + (- x3 - x2 - x - 1) = x4 - 1$

Here’s another way of looking at it:
$(x + 1)(x - 1) = (x2- x) + (x - 1) = x2 - 1 (x2 + x + 1)(x - 1) = (x3- x2) + (x2 - x) + (x - 1) = x3 - 1 3 2 4 3 3 2 2 4 (x+ x + x + 1)(x - 1) = (x - x ) + (x - x ) + (x - x) + (x- 1) = x - 1$
x⁶ + x⁵ + x⁴ + x³ + x² + x
- x⁵ - x⁴ - x³ - x² - x - 1
___________________________________________
x⁶ - 1
x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x
- x⁷ - x⁶ - x⁵ - x⁴ - x³ - x² - x - 1
_______________________________________________________
x⁸ - 1
Multiplying (x⁶ + x⁵ + x⁴ + x³ + x² + x + 1) by x raises the exponent of each term, leaving a new highest power of x (in this case, x⁷), and no 1. Multiplying the same series by -1 leaves the exponents unchanged, but all negative coefficients. Adding the results, all but the highest and lowest exponent terms cancel each other out. Products like (xⁿ + ... + x³ + x² + x + 1)(x - 1), therefore, have only two terms, xⁿ⁺¹ and -1.
As long as x1, = x² + x + 1 because (x² + x + 1)(x - 1) = x³ - 1.
Also, = x⁴ + x³ + x² + x + 1. Of course, if x = 1, these expressions involve division by 0, which makes no sense.
Problem 4 in section 2 showed that = a^n-1 + a^n-2 + ... + a² + a + 1. An example is (10⁴ - 1) ÷ (10 - 1) = 9999 ÷ 9 = 1111.

3 Epilogue: An application to arithmetic

This result also explains why a whole number whose digits add up to a multiple of 9 must, itself, be a multiple of 9.

When you divide 10ⁿ by 9, the remainder is 1, because 10ⁿ is 1 more than 10ⁿ - 1, a multiple of 9.
If b < 9, then dividing b + 9ab by 9 leaves a remainder of b. This is because 10ⁿ is 1 plus a multiple of 9, so b × 10ⁿ = b(1 + 9a) = b + 9ab.
If b < 5 and c < 5 and both are whole numbers, then $b× 105 + c× 103 = b(9m + 1) + c(9n + 1) = 9(mb + nc)+ (b + c)$ Because b + c < 9, dividing [9(mb + nc) + (b + c)] by 9 leaves a remainder of b + c. The exponents are irrelevant in this calculation, and so whether you divide 403000 or 34000000 by 9, in either case the remainder is 7.
If b + c = 9, what remainder do you get when you divide b × 10⁵ + c × 10³ by 9? ANSWER:
There is no remainder. $5 3 b× 10 + c × 10 = b(9m + 1) + c(9n + 1) = 9(mb + nc) + (b + c) = 9(mb + nc) + 9 = 9(mb + nc + 1)$

So, there is no remainder because 9(mb + nc + 1) is a multiple of 9.
Dividing 26453 leaves a remainder of 2. (20 2 + 0 = 2). The number 1350243 is divisible by 9.

Solutions

Problem | Hints | Answers

1 A conjecture from arithmetic

Numbers of the form 10ⁿ are written as a 1 followed by n zeros (for example, 10⁷ = 10,000,000). So numbers of the form 10ⁿ - 1 consist of n 9s (for example, 10⁷ - 1 = 9,999,999). Just looking at these tells us that they are all divisible by 9 and that the quotient after dividing by 9 is a number consisting of n 1s.
6³ - 1 = 215, 6⁷ - 1 = 279935, 6² - 1 = 35 and 6⁵ - 1 = 7775, all clearly divisible by 5. In fact, all numbers of the form 6ⁿ - 1 are divisible by 5. We use the multiplication algorithm to show why. The product of 6 and any number that ends with 6 is another number that ends with 6.

Now, because 6 ends in 6, 6² also ends in 6, and so 6³ ends in 6, and so on for all higher powers of 6.

Because the units digit of 6ⁿ is 6 for all n, the units digit of 6ⁿ - 1 is 5, which makes 6ⁿ - 1 a multiple of 5 for all n.
All powers of 3 must be odd. Subtracting 1 makes them even. So 3ⁿ - 1 is always divisible by 2.
The units digit of all powers of 11 must be 1. Subtracting 1 from any of them produces numbers that end in 0--multiples of 10. So 11ⁿ-1 is always divisible by 10. Why must all powers of 11 end with 1? We already know that the first few powers do. So, pick one of these--say, 11ⁿ--and show that if it ends in 1 (which it does), then 11ⁿ⁺¹ must also end in 1. 11ⁿ ^. 11 = 11ⁿ ^. (10 + 1) = 11ⁿ ^. 10 + 11ⁿ^. = a number ending in 0 (a multiple of 10) plus a number ending in 1. Alternatively, base your argument on the multiplication algorithm again.
So far, it seems that numbers of the form aⁿ - 1 are divisible by a - 1. “If you subtract 1 from any power of some number a, the result is divisible by a - 1.”

2 A proof from algebra

$(x - 1)(x + 1) = (x2 + x) + (- x - 1) = x2 - 1 (x- 1)(x2 + x + 1) = (x3 + x2 + x) + (- x2 - x - 1) = x3 - 1 (x- 1)(x3 + x2 + x + 1) = (x4 + x3 + x2 + x) + (- x3 - x2 - x - 1) = x4 - 1$

Here’s another way of looking at it:
$(x + 1)(x - 1) = (x2- x) + (x - 1) = x2 - 1 (x2 + x + 1)(x - 1) = (x3- x2) + (x2 - x) + (x - 1) = x3 - 1 (x3+ x2 + x + 1)(x - 1) = (x4- x3) + (x3 - x2) + (x2 - x) + (x- 1) = x4- 1$
x⁶ + x⁵ + x⁴ + x³ + x² + x
- x⁵ - x⁴ - x³ - x² - x - 1
___________________________________________
x⁶ - 1
x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x
- x⁷ - x⁶ - x⁵ - x⁴ - x³ - x² - x - 1
_______________________________________________________
x⁸ - 1
Multiplying (x⁶ + x⁵ + x⁴ + x³ + x² + x + 1) by x raises the exponent of each term, leaving a new highest power of x (in this case, x⁷), and no 1. Multiplying the same series by -1 leaves the exponents unchanged, but all negative coefficients. Adding the results, all but the highest and lowest exponent terms cancel each other out. Products like (xⁿ + ... + x³ + x² + x + 1)(x - 1), therefore, have only two terms, xⁿ⁺¹ and -1.
As long as x1, = x² + x + 1 and = x⁴ + x³ + x² + x + 1. Of course, if x = 1, these expressions involve division by 0, which makes no sense.
Problem 4 in section 2 showed that = a^n-1 + a^n-2 + ... + a² + a + 1. An example is (10⁴ - 1) ÷ (10 - 1) = 9999 ÷ 9 = 1111.

3 Epilogue: An application to arithmetic

This result also explains why a whole number whose digits add up to a multiple of 9 must, itself, be a multiple of 9.

If 10ⁿ - 1 is divisible by 9, then 10ⁿ must not be divisible by 9. What is the remainder when you divide 10ⁿ by 9? SOLUTION: 10ⁿ is 1 more than 10ⁿ - 1, a multiple of 9. So, dividing 10ⁿ by 9 leaves a remainder of 1.
If b is a whole number less than 9, then b × 10ⁿ is not divisible by 9. What is the remainder when you divide b×10ⁿ by 9? SOLUTION: Because 10ⁿ is 1 plus a multiple of 9, b × 10ⁿ = b(1 + 9a) = b + 9ab. Dividing b + 9ab by 9 leaves a remainder of b if b < 9.
If b < 5 and c < 5 and both are whole numbers, then $b× 105 + c× 103 = b(9m + 1) + c(9n + 1) = 9(mb + nc)+ (b + c)$ Because b + c < 9, dividing [9(mb + nc) + (b + c)] by 9 leaves a remainder of b + c. The exponents are irrelevant in this calculation, and so whether you divide 403000 or 34000000 by 9, in either case the remainder is 7.
If b + c = 9, what remainder do you get when you divide b × 10⁵ + c × 10³ by 9? SOLUTION:
$b× 105 + c × 103 = b(9m + 1) + c(9n + 1) = 9(mb + nc) + (b + c) = 9(mb + nc) + 9 = 9(mb + nc + 1)$

So, there is no remainder because 9(mb + nc + 1) is a multiple of 9.
Dividing 26453 is like dividing each of 20000, 6000, 400, 50, and 3 by 9. The remainders of the divisions, taken separately, are 2, 6, 4, 5, and 3. Because their total, 20, is greater than 9, still more 9s can be divided out. But after taking out those two more nines, there is still a remainder of 2. (20 2 + 0 = 2). Reasoning the same way about the number 1350243, we add 1 + 3 + 5 + 0 + 2 + 4 + 3 = 18. Exactly two more nines can be divided out, so 1350243 is divisible by 9.