How can you prove that $n^5-n$ is divisible by $30$ for any integer $n\ge 2$?

  • MHB
  • Thread starter Ackbach
  • Start date
  • Tags
    2015
In summary, the proof for the divisibility of $n^5-n$ by $30$ involves using mathematical induction and the fundamental theorem of arithmetic. There are also alternative methods such as modular arithmetic and the binomial theorem. This statement can also be generalized to any expression of the form $n^k-n$, where $k$ is a positive integer, using Fermat's little theorem and the same reasoning for the proof by mathematical induction.
  • #1
Ackbach
Gold Member
MHB
4,155
93
Here is this week's POTW:

-----

For any integer $n\ge 2$, prove that $n^5-n$ is divisible by $30$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
  • #2
Congratulations to lfdahl, Sudharaka, Petek, Kiwi, Fallen Angel, kaliprasad, and MarkFL for their correct solutions! I'm very glad to see such enthusiastic participation in the University POTW!

There were essentially three different methods represented by the above submissions, so I will post three representative solutions, one for each method:

Solution by MarkFL:

Suppose we write as our induction hypothesis $P_n$:

\(\displaystyle n^5-n=30k\) where \(\displaystyle k\in\mathbb{N}\)

Checking the base case $P_2$, we find:

\(\displaystyle 2^5-2=30k\)

\(\displaystyle 30=30\cdot1\)

The base case is true, so as our induction step, let's add the following to $P_n$:

\(\displaystyle \left((n+1)^5-(n+1)\right)-\left(n^5-n\right)=5n(n+1)\left((n+2)^2-3n\right)\)

Now, since one of $n,\,n+1,\,n+2$ must be divisible by 2 and one must also be divisible by 3 (and in the case of $n+2$ being divisible by 3, then $3n$ is as well), we may write:

\(\displaystyle 5n(n+1)\left((n+2)^2-3n\right)=30p\) where \(\displaystyle p\in\mathbb{N}\)

And so we obtain:

\(\displaystyle (n+1)^5-(n+1)=30k+30p=30(k+p)\)

Thus, we have derived $P_{n+1}$ from $P_n$, thereby completing the proof by induction.

Solution by Kiwi:
For any integer a we can express n as:

n=ab+r for some integers b and r where \(0 \leq r \lt a\)

\(\therefore n^5-n=(ab+r)^5-ab-r \equiv r^5-r\) mod a

Now if a = 5 then \(r \in \{0,1,2,3,4\} \text{ and } r^5-r \in \{0^5-0,1^5-1,2^5-2,3^5-3,4^5-4\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 5

Simiarly if a = 3 then \(r \in \{0,1,2\} \text{ and } r^5-r \in \{0^5-0,1^5-1,2^5-2\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 3

And if a = 2 then \(r \in \{0,1\} \text{ and } r^5-r \in \{0^5-0,1^5-1\}\) but all of these are congruent to zero so \(r^5-r \equiv 0\) mod 2

\(n^5-n\) is divisible by the primes 2,3 and 5 so by the unique factorisation of n into primes \(n^5-n\) is divisible by their product which is 30.

Solution by Sudharaka:
By Fermat's Little Theorem $n^5-n$ is divisible by 5.

\[n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=(n^3-n)(n^2+1)\]

Again by Fermat's Little Theorem $n^3-n$ is divisible by 3 and hence $n^5-n$ is divisible by 3.

\[n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)=(n^2-n)(n+1)(n^2+1)\]

Once again, by Fermat's Little Theorem $n^2-n$ is divisible by 2 and hence $n^5-n$ is divisible by 2. Therefore $n^5-n$ is divisible by 5, 3, and 2 and hence it is divisible by $5\times 3\times 2=30$.
 

FAQ: How can you prove that $n^5-n$ is divisible by $30$ for any integer $n\ge 2$?

How can you prove that $n^5-n$ is divisible by $30$ for any integer $n\ge 2$?

The proof involves using mathematical induction. First, we can show that the statement is true for the base case $n=2$, since $2^5-2=30$ which is divisible by $30$. Then, we assume the statement is true for some integer $k\ge 2$, that is, $k^5-k$ is divisible by $30$. We need to prove that the statement is also true for $k+1$, that is, $(k+1)^5-(k+1)$ is divisible by $30$. By expanding the expression, we get $(k+1)^5-(k+1)=k^5+5k^4+10k^3+10k^2+5k+1-k-1$. By substituting $k^5-k$ with $30$, this simplifies to $30+30k^2+30k$. Since $30$ is divisible by $30$ and $k^2+k$ is always an integer, the expression is also divisible by $30$. Therefore, the statement holds for $k+1$ and by mathematical induction, it is true for all integers $n\ge 2$.

Why is $n^5-n$ divisible by $30$ for any integer $n\ge 2$?

This can be explained using the fundamental theorem of arithmetic. Every integer can be expressed as a unique product of prime numbers. In this case, the numbers $n$, $n+1$, $n+2$, $n+3$, and $n+4$ (which make up the expression $n^5-n$) are consecutive integers, meaning they have no common factors other than $1$. Therefore, at least one of these numbers must be divisible by $2$ and another by $3$. By the fundamental theorem of arithmetic, since $2$ and $3$ are both prime numbers, their product $6$ must also be a factor of $n^5-n$. Additionally, since $n\ge 2$, $n^5-n$ will always be positive, meaning it cannot have a factor of $-1$. Therefore, $n^5-n$ is divisible by $6$ and $5$, making it also divisible by $30$.

Can the divisibility of $n^5-n$ by $30$ be proven using a different method?

Yes, there are multiple ways to prove this statement. One alternative method is using modular arithmetic. We can show that for any integer $n$, $n^5-n$ is congruent to $0$ modulo $30$. This means that $n^5-n$ is a multiple of $30$ and therefore divisible by $30$. Another method is using the binomial theorem to expand the expression as $(n-1)n(n+1)(n+2)(n+3)$ and showing that this is divisible by $30$ by considering cases where $n$ is even or odd.

Is there a general formula for proving the divisibility of expressions similar to $n^5-n$?

Yes, there is a general formula known as Fermat's little theorem. It states that if $p$ is a prime number and $n$ is an integer not divisible by $p$, then $n^{p-1}-1$ is divisible by $p$. This can also be extended to expressions of the form $n^m-n$ where $m$ is any positive integer. Therefore, for the expression $n^5-n$, we can use Fermat's little theorem with $p=5$ to prove its divisibility by $5$ and then use the methods mentioned above to show its divisibility by $2$ and $3$.

Can the statement be generalized to any expression of the form $n^k-n$ where $k$ is a positive integer?

Yes, the statement can be generalized to any expression of the form $n^k-n$ where $k$ is a positive integer. This is because, as mentioned in the previous question, Fermat's little theorem can be extended to expressions of this form. Also, the reasoning behind the proof using mathematical induction remains the same for any positive integer $k$. Therefore, the statement holds for any expression $n^k-n$ where $k$ is a positive integer.

Similar threads

MHB When Is \( (k+1)^n+(k+2)^n+(k+3)^n+(k+4)^n+(k+5)^n \) Divisible by 5?
Replies
1
Views
2K
MHB Is the expression $\frac{\gcd(m,n)}{n}\binom{n}{m}$ always an integer?
Replies
1
Views
1K
MHB Odd Prime Factor of \( a_{2015} \)?
Replies
1
Views
2K
MHB Is There a Simple Group of Order $2n$ for Odd $n \geq 3$?
Replies
1
Views
2K
MHB Problem of the Week # 275 - Aug 07, 2017
Replies
1
Views
1K
MHB Problem Of The Week # 288 - Nov 09, 2017
Replies
1
Views
2K
MHB Is $\theta(N)$ a normal subgroup of $G$?
Replies
1
Views
2K
MHB Problem Of The Week # 290 - Nov 24, 2017
Replies
1
Views
2K
MHB Problem Of The Week # 286 - Oct 24, 2017
Replies
1
Views
2K
MHB How Does Grouping Terms Simplify the Infinite Series in This Week's POTW?
Replies
1
Views
2K

Recent Insights

Back
Top