CDS Mathematics · Number System

Divisibility by Factorisation

Proving what divides a huge expression by factorising it instead of evaluating it — pulling the smallest power out of a sum of like powers, and using the standard a-to-the-n plus-or-minus-b-to-the-n identities.

All Number System notes CDS Mathematics strategy

Why this matters

Sixteen PYQs and 38% of them HARD — the densest HARD unit in the chapter. But the difficulty is entirely in recognising the shape: every question here is a one-line factorisation followed by reading off a prime factor. The power-sum extraction alone appears six times across the chapter and is the signature CDS pattern in this topic.

Concept 1 of 6: Pulling the smallest power out of a sum of like powers

When several terms share a base, factor out the lowest power. What remains is a small integer you can factorise by hand, and that integer carries every odd prime divisor of the whole expression. A thirty-digit number becomes a two-digit one.

Definition

For terms with a common base $a$ ,

a^{m}+a^{m+1}+\cdots+a^{m+k} = a^{m}\left(1+a+a^{2}+\cdots+a^{k}\right).

The bracket is a short geometric sum — compute it as an ordinary number and factorise it.
The power $a^{m}$ contributes only the primes already in $a$ , so any new prime divisor must come from the bracket.
Subtraction works the same way: signs just change the bracket, as in $3^{81}-3^{80}-3^{79} = 3^{79}(9-3-1) = 5\cdot 3^{79}$ .

Power-sum extraction

a^{m}+a^{m+1}+\cdots+a^{m+k}=a^{m}\!\left(1+a+\cdots+a^{k}\right)

Worked example

7^{20}+7^{21}+7^{22}

is divisible by which numbers?

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2018 · CDS (I) 2018 — Elementary Mathematics · Q1Easy

Example 1 · Number System · Divisibility by Factorisation

5^{17} + 5^{18} + 5^{19} + 5^{20}

is divisible by

A new prime can only come from the bracket

2^{122}+2^{124}+2^{126}+2^{128}+2^{130} = 2^{122}\times 341

, and

341 = 11\times 31

. The answer is 11 — the power of 2 cannot supply an odd factor, so checking the bracket alone is both necessary and sufficient. Students who try to test the whole number for divisibility by 11 get nowhere.

Drill 3 more on pulling the smallest power out of a sum of like powers

Concept 2 of 6: The a-to-the-n minus b-to-the-n identity

a^{n}-b^{n}

always has

a-b

as a factor, whatever

n

is. And when

n

is even it also has

a+b

, because you can view it as a difference of squares. So two divisors come for free.

Definition

For all positive integers $n$ ,

(a-b) \mid \left(a^{n}-b^{n}\right).

If $n$ is even, then $a^{n}-b^{n} = (a^{2})^{n/2}-(b^{2})^{n/2}$ is also divisible by $a^{2}-b^{2}$ , hence by $a+b$ .
More generally $a^{m}-b^{m}$ divides $a^{n}-b^{n}$ whenever $m \mid n$ .
Rewrite to expose the shape: $5^{2n}-2^{3n} = 25^{n}-8^{n}$ , so the free factor is $25-8=17$ .

Difference of like powers

a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)

Worked example

Show that

6^{10}-4^{10}

is divisible by both 2 and 10.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2019 · CDS (II) 2019 — Elementary Mathematics · Q50Moderate

Example 2 · Number System · Divisibility by Factorisation

The expression

5^{2n} - 2^{3n}

has a factor

a plus b needs an EVEN exponent for a difference

97^{30}-14^{30}

is divisible by

97^2-14^2 = 9213 = 3\times37\times83

precisely because 30 is even — which is how 37 and 83 both appear. For an odd exponent only

a-b

is available. Check the parity before claiming

a+b

Drill 3 more on the a-to-the-n minus b-to-the-n identity

Concept 3 of 6: The a-to-the-n plus b-to-the-n identity

A sum of like powers factorises only when the exponent is odd, and then

a+b

is a factor. This is the mirror image of the difference rule and the parity condition is reversed, which is the whole trap.

Definition

For odd $n$ ,

(a+b) \mid \left(a^{n}+b^{n}\right).

For even $n$ this fails: $a^{2}+b^{2}$ has no such factorisation over the integers.
The quick way to spot it: add the two bases and see whether the result is one of the options. $41+43 = 84$ ; $67+33 = 100$ ; $327+173 = 500$ .
Both terms being odd also makes the sum even, which is a separate free divisor of 2.

Sum of like powers, odd exponent

a^{n}+b^{n}=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right) \quad (n \text{ odd})

Worked example

Show that

13^{11}+12^{11}

is divisible by 25.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2022 · CDS (I) 2022 — Elementary Mathematics · Q2Moderate

Example 3 · Number System · Divisibility by Factorisation

41^{43} + 43^{43}

is divisible by

The parity conditions for a sum and a difference are opposite

a-b

divides a difference for every exponent;

a+b

divides a sum only for an odd exponent. Swapping these is the single commonest error in this unit. Write down which you have — sum or difference — then check the exponent's parity against the right rule.

Drill 1 more on the a-to-the-n plus b-to-the-n identity

Concept 4 of 6: Rewriting mixed bases as powers of one number

An expression mixing 2, 4 and 8, or 3, 9 and 27, is really a single-base expression in disguise. Convert everything to the smallest base first; the power-sum extraction then applies and the whole thing collapses.

Definition

Replace every composite base by a power of the common base: $4 = 2^2$ , $8 = 2^3$ , $9 = 3^2$ , $27 = 3^3$ , $25 = 5^2$ .

Multiply the exponents: $4^{62} = \left(2^{2}\right)^{62} = 2^{124}$ .
Then sort the terms by exponent and factor out the lowest.
For bases that share a factor without being powers of each other (555 and 777, both multiples of 3 and 37), factor the bases instead and look for a common divisor.

Rebasing

\left(a^{j}\right)^{k}=a^{jk}

Worked example

Simplify

4^{15}+8^{10}

to a single power of 2.

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2016 · CDS (II) 2016 — Elementary Mathematics · Q30Hard

Example 4 · Number System · Divisibility by Factorisation

2^{122} + 4^{62} + 8^{42} + 4^{64} + 2^{130}

is divisible by which one of the following integers ?

Rebase before you sort, and sort before you factor

2^{122}+4^{62}+8^{42}+4^{64}+2^{130}

looks like five unrelated terms. Rebasing gives

2^{122},2^{124},2^{126},2^{128},2^{130}

— an evenly spaced run — and factoring out

2^{122}

leaves

1+4+16+64+256 = 341 = 11\times31

. Attempting to factor before rebasing gets nowhere.

Drill 1 more on rewriting mixed bases as powers of one number

Concept 5 of 6: The largest number that ALWAYS divides an expression

"Always divides" is a claim about every value of the variable — so the answer can be no larger than the value at the smallest admissible input. Compute that one case first; it caps the answer, and usually equals it.

Definition

To find the largest $d$ dividing $f(n)$ for all admissible $n$ :

factor $f(n)$ to get a guaranteed divisor;
evaluate $f$ at the smallest admissible $n$ — the answer must divide that number, which caps it;
confirm the cap is attained.

Watch the domain: "natural number" usually starts at 1, but "whole number" includes 0, and that single difference changes the answer.

The cap from the smallest case

d \mid f(n)\ \forall n \;\Longrightarrow\; d \mid f(n_{\min})

Worked example

What is the largest number that always divides

5^{x}+5^{x+1}

for every natural number

x

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2020 · CDS (I) 2020 — Elementary Mathematics · Q10Moderate

Example 5 · Number System · Divisibility by Factorisation

Which one of the following is the largest divisor of

3^{x} + 3^{x+1} + 3^{x+2}

, if

x

is any natural number ?

Whole numbers include zero, and that can break the statement

5\cdot 8^{m}+2^{3m} = 6\cdot 8^{m}

, which is divisible by 48 for every

m \ge 1

— but at

m=0

it equals 6, and 6 is not divisible by 48. Since "whole numbers" include 0, the statement is false. Always test the smallest value the stated domain actually permits.

Drill 1 more on the largest number that always divides an expression

Concept 6 of 6: When a variable divides a polynomial in itself

If every term of a polynomial except the constant already has a factor of

x

, then

x

divides the whole thing exactly when

x

divides the constant. So the question collapses to listing the divisors of one small number.

Definition

For a polynomial with integer coefficients,

x \mid \left(a_kx^{k}+\cdots+a_1x+c\right) \iff x \mid c.

Every term containing $x$ is automatically divisible by $x$ ; only the constant can obstruct.
So the count of valid positive $x$ is the number of positive divisors of $c$ .
The same reasoning read backwards handles $\frac{f(m)+n}{m}$ : it is an integer exactly when $m \mid n$ .

Constant-term criterion

x \mid \left(a_kx^{k}+\cdots+a_1x+c\right) \iff x \mid c

Worked example

For how many positive integers

x

x^{2}+3x+12

exactly divisible by

x

Practice this conceptself-check · 4 quick reps

The same idea in a real exam question:

CDS · 2020 · CDS (II) 2020 — Elementary Mathematics · Q1Moderate

Example 6 · Number System · Divisibility by Factorisation

x^3 + x^2 + 16

is exactly divisible by

x

, where

x

is a positive integer. The number of all such possible values of

x

Count the divisors of the constant, not the values you happen to test

For

x^{3}+x^{2}+16

the condition is

x\mid 16

, giving

1,2,4,8,16

— five values. Testing

x=1,2,3,\ldots

by substitution finds the same answers much more slowly and risks stopping early. Reduce to the constant first, then count its divisors.

Drill 1 more on when a variable divides a polynomial in itself

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Formulas (6)

Pulling the smallest power out of a sum of like powers
Power-sum extraction
$a^{m}+a^{m+1}+\cdots+a^{m+k}=a^{m}\!\left(1+a+\cdots+a^{k}\right)$
The a-to-the-n minus b-to-the-n identity
Difference of like powers
$a^{n}-b^{n}=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots+b^{n-1}\right)$
The a-to-the-n plus b-to-the-n identity
Sum of like powers, odd exponent
$a^{n}+b^{n}=(a+b)\left(a^{n-1}-a^{n-2}b+\cdots+b^{n-1}\right) \quad (n \text{ odd})$
Rewriting mixed bases as powers of one number
Rebasing
$\left(a^{j}\right)^{k}=a^{jk}$
The largest number that ALWAYS divides an expression
The cap from the smallest case
$d \mid f(n)\ \forall n \;\Longrightarrow\; d \mid f(n_{\min})$
When a variable divides a polynomial in itself
Constant-term criterion
$x \mid \left(a_kx^{k}+\cdots+a_1x+c\right) \iff x \mid c$

Watch out for (6)

A new prime can only come from the bracket
→ Pulling the smallest power out of a sum of like powers
a plus b needs an EVEN exponent for a difference
→ The a-to-the-n minus b-to-the-n identity
The parity conditions for a sum and a difference are opposite
→ The a-to-the-n plus b-to-the-n identity
Rebase before you sort, and sort before you factor
→ Rewriting mixed bases as powers of one number
Whole numbers include zero, and that can break the statement
→ The largest number that ALWAYS divides an expression
Count the divisors of the constant, not the values you happen to test
→ When a variable divides a polynomial in itself

Test yourself on Number System

20 past CDS questions from this chapter, timed at 24 minutes and marked the way the exam marks it. You see your score and every answer the moment you finish. Free to start.

Take the Number System chapter test Drill all 16 questions

Related notes

Divisibility rules and missing digits →