Problem of the Week

Problem 24 Solution

Congratulations to Markus Kuan from Northstowe Secondary College for successfully solving the problem!

(a) Factorise:

$x^{3}-x = x(x^{2}-1) = x(x+1)(x-1)$

$(x-1), x, (x+1)$ are all consecutive integers. Any two consecutive integers will have at least one number that is divisible by 2, any three consecutive integers will have at least one number that is divisible by 3. The entire expression has factors of 2 and 3, so it will also have a factor of 6.

(b) Factorise:

$x^{5}-x = x(x^{4}-1) = x(x^{2}+1)(x^{2}-1) = x(x^{2}+1)(x-1)(x+1)$

Using the same logic from (a), the expression will be divisible by 2 and 3.

Consider $x(x^{2}+1)(x^{2}-1)$ . You may realise that all square numbers end in the digits 1, 4, 5, 6, 9, 0. These digits are all either 1 more, 1 below, or is a multiple of 5. Hence, you can always find a multiple of 5 on one of the three terms depending on the units digit of $x^{2}$ . If $x^{2}$ ended in 1 or 6, plugging into $(x^{2}-1)$ will return a number divisible by 5. If $x^{2}$ ended in 4 or 9, plug into $(x^{2}+1)$ . If $x^{2}$ ended in 5 or 0, $x$ itself is divisible by 5. The expression has a factor of 2, 3, 5, and therefore will contain a factor of 30.

‎

Alternative Method 1:

Consider $x(x^{2}+1)(x-1)(x+1)$ .

$x^{2}+1 = x^{2}-4+5 = (x-2)(x+2)+5$

$(x-2)(x+2)+5 \equiv (x-2)(x+2) \pmod{5}$

If $(x-2)$ or $(x+2)$ was divisible by 5, then $x^{2}+1$ will be divisible by 5 too.

$(x-2),(x-1),x,(x+1),(x+2)$ are five consecutive integers, this means at least one of them must be divisible by 5. Therefore, the entire expression has a factor of 5.

(c)* Consider $(x+1)^{p}$ .

Those that do Further Maths GCSE may recognise binomial expansion using Pascal’s Triangle. Consider the $p$ th row. Notice how all the middle terms are always divisible by $p$ .

Here’s a proof:

Each term in the $p$ th row of Pascal’s Triangle, represented by the $k$ th term has the coefficient:

$\binom{p}{k} = \frac{p!}{k!(p - k)!}$

where 1 $\leq$ $k$ $\leq$ $p-1$ (0th term and $k$ th term are the 1s on the side)

Since $p$ is prime, when $k$ or $p-k$ is less than $p$ , the denominator will not have the factor $p$ , meaning the overall value will have the factor $p$ . The only exception is when $k=0$ or $k=p$ , where the denominator contains $p!$ . This will divide the numerator and makes the 1s on the side of the triangle.

This means the expansion of $(x+1)^{p}$ will reduce to the following:

$(x+1)^{p} \equiv x^p + ... + 1 \pmod{p}$

$(x+1)^{p} \equiv x^p + 1 \pmod{p} \text{(all middle terms divisible by p)}$

Plug $x=0$ into the equation:

$(0+1)^{p} \equiv 0^p + 1 \pmod{p}$

$1^{p} \equiv 0 + 1 \pmod{p}$

$1^{p} \equiv 1 \pmod{p}$

Plug $x=1$ into the equation:

$(1+1)^{p} \equiv 1^p + 1 \pmod{p}$

$2^{p} \equiv 1 + 1 \pmod{p}$

$2^{p} \equiv 2 \pmod{p}$

Plug $x=2$ into the equation:

$(2+1)^{p} \equiv 2^p + 1 \pmod{p}$

$3^{p} \equiv 2 + 1 \pmod{p}$

$3^{p} \equiv 3 \pmod{p}$

Notice in the above examples, by induction,

$x^{p} \equiv x \pmod{p}$

$x^{p}-x \equiv 0 \pmod{p}$

This shows that $x^p-x$ is always divisible by $p$ , when $p$ is a prime and $x$ is an integer.

For further learning, consider checking out modular arithmetic or proof by induction. Also, part (c) proves a version of Fermat’s Little Theorem, those who are interested in that proof could consider giving it a search.

Problem of the Week

Problem 24 Solution

Site Search