Problem of the Week #35 - November 26th, 2012

[Chris L T521]

Thanks to those who participated in last week's POTW!! Here's this week's problem!

-----

Problem: Show that $n^{13}-n$ is divisible by $2730$ for all $n$.

-----

Note: This is equivalent to showing that $n^{13}-n\equiv 0\pmod{2730}$ for all $n$.

Hint:

Spoiler

Use Fermat's theorem coupled with the Chinese Remainder Theorem to show this result.

Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Chris L T521]

This week's problem was correctly answered by Bacterius MarkFL, and Sudharaka.

Here's Bacterius' solution:

Spoiler

$n^{13} - n = 0 \pmod{2730} \iff n^{13} = n \pmod{2730}$ for all $~ n$

We note that $~ 2730 = 2 \times 3 \times 5 \times 7 \times 13$, thus we shall define $~ \mathbb{P} = \left \{ 2, 3, 5, 7, 13\right \}$ and study the simpler statement:

$n^{13} = n \pmod{p} ~~ \forall p \in \mathbb{P}$

Because every element in $\mathbb{P}$ is prime, we have $~ \gcd{\left ( n, p \right )} = 1$ for every $~ n$, thus it is valid to divide through by $~ n$ as an inverse is guaranteed to exist. Therefore:


$n^{12} = 1 \pmod{p} ~~ \forall p \in \mathbb{P}$


From Fermat's Little Theorem (FLT), the above holds if $~ p - 1 \, | \, 12$ for every $p \in \mathbb{P}$. We have $~ p - 1 ~ (\forall p \in \mathbb{P}) \implies \left \{ 1, 2, 4, 6, 12 \right \}$, and we note that all of these happen to be factors of (and hence divide) $~ 12$, therefore the statement does hold true for every $~ n$. It then follows from the Chinese Remainder Theorem (CRT) that:

$\displaystyle n^{12} = 1 \pmod{p} ~~ \forall p \in \mathbb{P} \iff n^{12} = 1 \pmod{ 2 \times 3 \times 5 \times 7 \times 13} \iff n^{12} = 1 \pmod{2730}$

$\therefore n^{13} = n \pmod{2730}$ for all $~ n$ and we conclude that $~ n^{13} - n$ is divisible by $~ 2730$ for all $~ n$.

$\mathbb{QED}$

Here's Sudharaka's solution:

Spoiler

From Fermat's theorem we have,

\[n^2-n\equiv 0\pmod{2}\mbox{ for all }n\]

\[\Rightarrow n^3-n^2\equiv 0\pmod{2}\]

Since, \(n^2\equiv n\pmod{2}\) we obtain,

\[n^3-n\equiv 0\pmod{2}\]

Repeating this process we finally get,

\[n^{13}-n\equiv 0\pmod{2}\mbox{ for all }n~~~~~~~~~~~~(1)\]

Similarly the following congruences can be obtained by using Fermat's theorem for primes \(3,5,7\mbox{ and }13\) respectively.

\[n^{13}-n\equiv 0\pmod{3}\mbox{ for all }n~~~~~~~~~~~~~(2)\]

\[n^{13}-n\equiv 0\pmod{5}\mbox{ for all }n~~~~~~~~~~~~~(3)\]

\[n^{13}-n\equiv 0\pmod{7}\mbox{ for all }n~~~~~~~~~~~~~(4)\]

\[n^{13}-n\equiv 0\pmod{13}\mbox{ for all }n~~~~~~~~~~~~~(5)\]

By the Chinese Remainder Theorem the solutions of the system of congruences, (1) to (5) are congruent modulo \(2\times 3\times 5\times 7\times 13=2730\). Therefore we can write,

\[n^{13}-n\equiv 0\pmod{2730}\mbox{ for all }n\]