1
$\begingroup$

What is the largest integer which must evenly divide all integers of the form $n^5-n$ ?

I am stuck on this problem,I don't know how to approach this.

Some scribble I've tried is:

Given that $n^5-n \equiv 0 \mod x $,I have $\left(n- \cfrac{1}{2} \right)^2 \equiv \cfrac{1}{4} \mod x \implies n \equiv 1 \mod x \implies x\cdot q =n-1 $ for some integer $q$.

I know that $n^5-n$ is always a multiple of $5$ by Fermat's little theorem so $x$ is some multiple of $5$ but after that I don't know what to do.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It's a good start. How about $n^5 -n $ modulo some other (small) integers? $\endgroup$ – hardmath Jan 22 '16 at 18:12
  • 5
    $\begingroup$ $2^5-2$ dramatically limits what other numbers you need to check. $\endgroup$ – Arthur Jan 22 '16 at 18:15
  • 1
    $\begingroup$ "I know that $n^5−n$ is always a multiple of $n^5 -n$ by Fermat's little theorem so x is some multiple of 5 but after that I don't know what to do." Well, that's the most important part. next thing to not is that $n^5 - n= n(n^4 - 1)= n(n^2 - 1)(n^2 + 1) = n(n+1)(n-1)(n^2 + 1)$ so n, n+1, n-1 are three consecutive integers so is a mulitple of 3 and or 2 so 2*3*5 = 30 will divide all. As $2^5 - 2 = 30$ 30 is the largest number that divides all. ... interesting. This means for any 3 consect integers, none div by 5, then the middle one squared + 1 is always div by 5... neat... $\endgroup$ – fleablood Jan 22 '16 at 18:29
  • $\begingroup$ See also math.stackexchange.com/questions/164524/…. $\endgroup$ – lhf Jan 22 '16 at 19:22
5
$\begingroup$

A good start is to look at $2^5-2$ because $x$ must divide it also :

$2^5-2=30=2 \cdot 3 \cdot 5$

You checked that $5 \mid n^5-n$ for every $n$ .

It's also clear that $2 \mid n^5-n$ because they have the same parity .

Finally :

$$n^5-n=(n^3-n)(n^2+1)$$ and from Fermat's theorem $3 \mid n^3-n$ so it also follows that $3 \mid n^5-n$ .

Putting everything together it follows that $x=30$ is the required number .

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer. One last doubt :how do I know that I won't get an extra factor from $n^2+1 $ ? $\endgroup$ – Mr. Y Jan 22 '16 at 18:47
  • 1
    $\begingroup$ @Mr.Y So you know that $2,3$ and $5$ divides all the numbers and this means that $30$ divides all the numbers .But the number you're searching needs to divide also $$2^5-2=30$$ so these are the only possible factors . $\endgroup$ – user252450 Jan 22 '16 at 18:49
  • $\begingroup$ @ComplexPhy Thanks again,that cleared the confusion ! $\endgroup$ – Mr. Y Jan 22 '16 at 18:51
  • $\begingroup$ Well you won't get another factor of 3 from $n^2 + 1$ but that's coincidental. and if 5 doesn't divide $n^3 - n$ then you will get a factor of 5 out of $n^2 + 1$. And you could of course get all sorts of factors out of $n^2+1$ (if n is odd; you'll get extra factors of 2, etc.). But because $2^5 - 2$ = 30 you know thirty is a max possible required value. Those potential extra factors don't matter. the min possible. required value.... $\endgroup$ – fleablood Jan 22 '16 at 19:12
3
$\begingroup$

Hint: $$n^5-n=n(n-1)(n+1)(n^2+1)$$ The first thing to notice would be that there are three consecutive integers - $(n-1)n(n+1)$. Also checking modulo 5 might help.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

$2^5-2=30=2\cdot3\cdot5=6\cdot5$

$N=n^5-n=(n-1)(n)(n+1)(n^2+1)\Rightarrow N\equiv0 \pmod6$.

$n\equiv 1\pmod5\Rightarrow n-1\equiv 0\pmod5$

$n\equiv 2\pmod5\Rightarrow n^2+1\equiv 0\pmod5$

$n\equiv3\pmod5\Rightarrow n^2+1\equiv 0\pmod5$

$n\equiv4\pmod5\Rightarrow n+1\equiv 0\pmod5$

Consequently the asked number is $\color{red}{30}$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks sir for the answer,it provided me other insights about the problem :) $\endgroup$ – Mr. Y Jan 22 '16 at 19:01
  • $\begingroup$ It is a pleasure to help you, Mr Y $\endgroup$ – Piquito Jan 22 '16 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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