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

Status
Not open for further replies.

Chris L T521

Well-known member
Staff member
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:
Use Fermat's theorem coupled with the Chinese Remainder Theorem to show this result.

Chris L T521

Well-known member
Staff member
This week's problem was correctly answered by Bacterius MarkFL, and Sudharaka.

Here's Bacterius' solution:

$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:

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$

Status
Not open for further replies.