Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can I prove that prove $n^5 - n$ is divisible by 30?

I took $n^5 - n$ and got $n(n-1)(n+1)(n^2+1)$

Now, $n(n-1)(n+1)$ is divisible by 6.

Next I need to show that $n(n-1)(n+1)(n^2+1)$ is divisible by 5.

My guess is using Fermat little theory but I don't know how..

share|improve this question
    
There are 8 more answers at Divisibility of composite numbers –  MJD Jul 30 '12 at 19:13

9 Answers 9

up vote 11 down vote accepted

I'm going to take a leap, and suppose that you are doing exercises from the first section of Ireland and Rosen. In that case, I think that FLT is not the 'anticipated' method of solution.

So let's start from your factorization, $(n-1)n(n+1)(n^2 + 1)$

If $n$ is of the form $5k$, $5k-1$, or $5k+1$, we're done from the first three factors. What if $n$ is of the form $5k \pm 2$?

I claim to you that $n^2 + 1$ is always divisible by $5$ if $n = 5k \pm 2$. Perhaps the easiest way to see this is through strict computation. Or you could note that the constant term is either $5$ or $10$. In any case, I leave that part to you: can you show that $n^2 + 1$ is divisible by $5$ if $n = 5k \pm 2$?

share|improve this answer

Write as $n(n^2+1)(n^2-1)$ and note that the squares modulo $5$ are $\pm 1, 0$. Little Fermat does the trick immediately, but sometimes squares are useful.

share|improve this answer

a) $\small n^5-n = n \cdot(n^4-1) $ and $\small (n^4-1) $ is divisible by 5 by little fermat.
b) $\small n^5-n = n \cdot(n^2-1)(n^2+1) $
$ \small \qquad \qquad =n \cdot (n-1)(n+1)(n^2+1) $
$\small \qquad \qquad = (n-1)n(n+1) \cdot (n^2+1) $
$\qquad$ and $\small (n-1)n(n+1) $ is divisble by 6 (because by 2 and by 3)

Combine a) AND b) to see that $\small n^5-n $ is divisble by 5 AND 6 so also by 30.

share|improve this answer

By Fermat little theorem $n^5\equiv n\ \pmod{5}$.

share|improve this answer

Using combinatorial polynomials: $$ \begin{align} n^5-n &=120\binom{n}{5}+240\binom{n}{4}+150\binom{n}{3}+30\binom{n}{2}\\ &=30\left(4\binom{n}{5}+8\binom{n}{4}+5\binom{n}{3}+\binom{n}{2}\right) \end{align} $$ Note: The combinatorial polynomial expansion for a known polynomial, $P(n)$, is not as hard as it might seem. The coefficient, $a_0$, of $\binom{n}{0}$ is simply $P(0)$. If the coefficients, $a_j$, for $\binom{n}{j}$ are known for $j<k$, then the coefficient for $\binom{n}{k}$ is $$ P(k)-\sum_{j=0}^{k-1}a_j\binom{k}{j} $$

share|improve this answer
    
a nice alternative. Is there some reason to believe this method will generally drop out the highest integer factor? –  Ronald Apr 15 '12 at 22:32
    
@Ronald: Yes. A polynomial maps $\mathbb{Z}$ to $\mathbb{Z}$ if and only if it is an integral linear combination of combinatorial polynomials. This is proven on the page cited in the answer. –  robjohn Apr 15 '12 at 22:36
    
not sure if I understand why integral linear combination is relevant to the factor 30 becoming apparent? surely the original polynomial is an integral linear combination of elementary polynomials, but the 30 is not apparent. –  Ronald Apr 15 '12 at 22:49
    
@Ronald: if $30$ is a factor of $P(n)$ for every $n\in\mathbb{Z}$, then consider $Q(n)=\frac{1}{30}P(n)$. $Q(n)$ is a polynomial that maps $\mathbb{Z}$ to $\mathbb{Z}$, so it is an integral linear combination of combinatorial polynomials. Thus, $P(n)=30Q(n)$ will be an integral linear combination of combinatorial polynomials in which all of the coefficients are multiples of $30$. In other words, taking the GCD of the coefficients of $P(n)$ written as a linear combination of combinatorial polynomials yields the GCD of of $P(\mathbb{Z})$. –  robjohn Apr 15 '12 at 23:43

Hint $\rm\ mod\ 5\!:\ n \not\equiv 0\ \Rightarrow\ n\equiv \pm1,\pm2\ \Rightarrow\ n^2\equiv \pm1\ \Rightarrow\ n^4\equiv 1\ \Rightarrow\ n^5\equiv n$

This is a special case of the following global-form of Fermat's little theorem.$\: $ For naturals $\rm\: a,k,n$

$\ $ if $\rm\ a,k > 1\ $ then $\rm\ a\ |\ n^k\! -\! n\ $ for all $\rm\:n \iff a\:$ is squarefree, and $\rm\ p\!-\!1\: |\: k\!-\!1\ \ \:\forall$ primes $\rm\:p\:|\:a$

Hence for $\rm\: a = 30\: = 2\cdot 3\cdot 5\ $ we deduce: $\rm\ \ 30\ |\ n^k-n\ $ for all $\rm\:n\ \iff\ 4\ |\ k-1$

For the simple proof and further discussion see my 2009/04/10 sci.math post - which also presents the analogous generalization of Euler's $\phi$ function, and Korselt's criterion for Carmichael numbers.

Note: to fix rotted Google Groups links in the cited sci.math post it may be necessary to change $\ $ http://google.com/... $\ $ to$\ $ http://groups.google.com/... i.e. insert "groups." before "google.com".

share|improve this answer

$n^5-n=(n-1)n(n+1)(n^2+1)$. Rewrite $n^2+1$ as $5(n-1)+(n^2-5n+6)$ to obtain $n^5-n=5(n-1)^2n(n+1)+(n-3)(n-2)(n-1)n(n+1)$ and use the fact that $n!$ divides the product of n consecutive numbers.

share|improve this answer

$$\phi(2), \phi(3), \phi(5) \ | \ 4 \quad \stackrel{\textrm{Euler}}{\Longrightarrow} \quad n^5 \equiv n^{5-4} \mod{2,3,5} \quad \stackrel{\textrm{C.R.T.}}{\Longrightarrow} \quad n^5 - n \equiv 0 \mod{30}$$

share|improve this answer

By the Fermat little theorem, $n^{5} \equiv n \mod 5$ i.e. $n^{5} - n \equiv 0 \mod 5$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.