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.

I was trying to prove this, and I realized that this is essentially a statement that $n^5$ has the same last digit as $n$, and to prove this it is sufficient to calculate $n^5$ for $0-9$ and see that the respective last digits match. Another approach I tried is this: I factored $n^5-n$ to $n(n^2+1)(n+1)(n-1)$. If $n$ is even, a factor of $2$ is guaranteed by the factor $n$. If $n$ is odd, the factor of $2$ is guaranteed by $(n^2+1)$. The factor of $5$ is guaranteed if the last digit of $n$ is $1, 4, 5, 6,$ $or$ $9$ by the factors $n(n+1)(n-1)$, so I only have to check for $n$ ending in digits $0, 2, 3, 7,$ $and$ $8$. However, I'm sure that there has to be a much better proof (and without modular arithmetic). Do you guys know one? Thanks!

share|improve this question
4  
Whether or not modular arithmetic is allowed, it is still a question of elementary number theory. –  MJD May 27 '13 at 20:24
2  
One has to use other basic tools of number theory, and that's what the answers below demonstrate. –  MJD May 27 '13 at 20:27
2  
It's funny to ask for a proof about modular arithmetic which does not use modular arithmetic. –  Martin Brandenburg May 27 '13 at 21:01
3  
I've never understood people who ask for answerers to not use modular arithmetic. The answers invariably end up using modular arithmetic and just not using the word 'mod,' because that's essentially the only way to solve the problem. –  Potato May 27 '13 at 21:56
1  
@Potato I updated my answer with a "full disclosure", because basically even the little step of arguing that $k(k + 1)(k + 1)$ is even depends on congruences! Division into even/odd cases is tantamount to division into the two symbols of the mod 2 congruence. Divisibility is tied to congruences, period. This question boils down to "prove that such and such a formula is congruent to 0 mod 10, but don't use congruences or modulo math". –  Kaz May 28 '13 at 7:09

7 Answers 7

up vote 21 down vote accepted

Your proof is good enough. There's a slight improvement, if you want to avoid modular arithmetic / considering cases.

$n^5 - n$ is a multiple of 5 $\Leftrightarrow$ $ n^5 + 10 n^4 + 35n^3 + 50 n^2 + 24 n = n^5 -n + 5(2n^4 + 7n^3 + 10n^2 + 5n) $ is a multiple of 5. The latter is just $n(n+1)(n+2)(n+3)(n+4)$, which is the product of 5 consecutive integers, hence is a multiple of 5.


Note: You should generally be able to do the above transformation, and can take the product of any 5 (or k) consecutive integers, if you are looking at a polynomial of degree 5 (or k).

share|improve this answer
    
I don't understand the point of n(n+1)(n+2)(n+3)(n+4) being divisible by 5, because n(n+1)(n+2)(n+3)(n+4) does not equal $n^5−n$ –  Ovi May 27 '13 at 20:37
    
@Ovi I made the if and only if implication explicit. Does this help? –  Calvin Lin May 27 '13 at 20:38
    
Sorry, I still don't see why n^5−n is a multiple of 5 ⇔ $n^5+10n+35n+50n+24n$. And if you are using $n(n+1)(n+2)(n+3)(n+4)$, shouldn't it be $n^5+10n^4+35n^3+50n^2+24n?$ –  Ovi May 27 '13 at 20:43
1  
@Ovi Indeed, I forgot the degrees. I've added the explanation, though it's similar to the rest, which you seem to have trouble following. Do you agree with "$x$ is a multiple of 5 if and only if $x+5$ is a multiple of 5"? –  Calvin Lin May 27 '13 at 20:46
1  
@Ovi: Notice that adding $10n^4$ or $35n^3$ or $50n^2$ doesn't change divisibility by 5 because all of them are multiples of 5, and adding a multiple of 5 to a number already divisible by 5 will keep it divisible by 5, and adding a multiple of 5 to a number not divisible by 5 will keep it not divisible by 5. I think the problem is that everyone here knows and is implicitly stating the same result of modular arithmetic, which you aren't following, that 24n = -n (mod 5). –  Zen May 27 '13 at 20:49

$$n^5-n=n(n^2+1)(n+1)(n-1)= n(n^2-4)(n+1)(n-1)+5n(n-1)(n+1)=(n-2)(n-1)n(n+1)(n+2)+5n(n-1)(n+1)$$

$(n-2)(n-1)n(n+1)(n+2)$ is even and divisible by 5, since it is the product of 5 consecutive integers.

$5(n-1)n(n+1)$ is also even and divisible by $5$.

Note: Both expressions are also divisible by $3$, so $n^5-n$ is actually divisible by $30$!

share|improve this answer
6  
265252859812191058636308480000000 does not divide $n^5-n$ :) –  cyclochaotic May 28 '13 at 0:13
    
@cyclochaotic :)) –  N. S. May 28 '13 at 0:14

Clearly, $n$ and $n^5$ are of the same parity. Hence, $2 \vert (n^5-n)$.

To check for divisibility by $5$, note that \begin{align} n^5 - n & = (n^2+1)n(n+1)(n-1)\\ & = (n^2-4+5)n(n+1)(n-1)\\ & = (n^2-4)n(n+1)(n-1) + 5n(n+1)(n-1)\\ & = (n-2)(n-1)n (n+1)(n+2) + 5n(n+1)(n-1)\\ \end{align}

Clearly, $5 \vert 5n(n+1)(n-1)$. Also, $(n-2)(n-1)n (n+1)(n+2)$ is a product of $5$ consecutive numbers and hence $5$ divides it.

share|improve this answer
    
I don't understand the point of (n−2)(n−1)n(n+1)(n+2) being divisible by 5, because (n−2)(n−1)n(n+1)(n+2) does not equal $n^5-n$ –  Ovi May 27 '13 at 20:33
1  
$n^5-n=p+q$, thus $5|p$ and $5|q$ imply that $5|(n^5-n)$. –  Jack May 27 '13 at 20:54

Since $n$ and $n^5$ have the same parity, $f(n):=n^5-n$ is divisible by $2$. It is also divisible by $5$, since $f(0)=0$ and $f(n+1)-f(n)=\dotsc=5 n (n^3 + 2 n^2 + 2 n + 1)$. More generally, for every prime $p$, $f(n):=n^p-n$ is divisible by $p$, this is Fermat's little theorem. In fact, $f(n+1)-f(n)=\sum_{0<k<p} \binom{p}{k} n^k$ and $p \mid \binom{p}{k}$ for $0 < k < p$.

share|improve this answer
1  
Very nice solution –  Ovi May 27 '13 at 21:05

Key idea $\ \ p\!-\!1\mid n\!-\!1\,\Rightarrow\, p\mid a^n- a.\ $ Proof $\ $ Clear if $\,p\mid a.\,$ Else write $\, \color{#f0f}n = (p\!-\!1)k + 1.\,$

$\ \color{#0a0}{b\!-\!1\mid b^k\!-\!1}\,$ so $\,b = a^{p-1}\,\Rightarrow\, \color{#c00}{p\mid} \color{#0a0}{a^{p-1}\!-\!1\mid (a^{(p-1)k}\!-\!1)}a = a^\color{#f0f}{\large n}\!-\!a\ $ by $\rm\color{#c00}{little\ Fermat}\ \ {\bf QED}$

So $\ p\!-\!1,q\!-\!1\mid n\!-\!1\,\Rightarrow\ p,q\mid a^n\!-a\,\Rightarrow\,pq\mid a^n\!-a,\,$ by $\,{\rm lcm}(p,q) = pq\,$ for $\,p\neq q\,$ primes. Yours is the special case $\ p = 2,\ q = 5,\ n = 5.$

The converse is also true, which yields the following generalization of little Fermat-Euler.

Theorem $\ \ $ For naturals $\ m,n > 1$

$$ m \mid a^n - a\ \ \ \text{for all }\ a\in\Bbb Z\iff m\ \text{ is squarefree, and prime } p\mid m\,\Rightarrow\, p-1\mid n- 1$$

share|improve this answer
    
Note: this was an answer to this duplicate question, but could not be posted there due to it being closed while the answer was being composed. –  Key Ideas Jun 13 '13 at 2:12
    
Thanks, but again I was looking for an answer without modular arithmetic. –  Ovi Jun 13 '13 at 2:27
    
@Ovi Ah, then it was a mistake to close the current question as a duplicate of this one. –  Key Ideas Jun 13 '13 at 2:31
    
I guess so but this one still has some really great answers. –  Ovi Jun 13 '13 at 2:32
    
@Ovi I eliminated the modular arithmetic. If anything is not clear please let me know and I will elaborate. –  Key Ideas Jun 13 '13 at 2:56

To check if $n^5-n$ is congruent to $0$ modulo $5$, it suffices to check the five cases $n = 0, \pm 1, \pm 2$. Since the polynomial $n^5-n$ is odd, the sign is not important, and we need check only $0$, $1$, and $2$. The first two cases are trivial, and for the last case we calculate manually $32 - 2$ which is divisible by $5$.

Congruence modulo $3$ or modulo $2$ is similar (only involves the "trivial" cases).

share|improve this answer

Without modular arithmetic? How about induction?

Base case: it is true for $n = 0$ since $0^5 - 0 = 0$. It is also true for $-1$ and $1$ since $-1^5 + 1 = 0$, and $1^5 - 1 = 0$. And it is true for $-2$ and $2$: $-2^5 + 2 = -30$ and $2^5 - 2 = 30$.

Inductive hypothesis: if it is true for $k$, it can be shown to be true for $k + 1$ or vice versa. We can work it from $k + 1$ to $k$, avoiding any "trap door" steps, so that all derivation works both ways.

$$(k + 1)^5 - (k + 1) = 10q$$

$$k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - (k + 1) = 10q$$

Rearrange terms, cancel 1 and -1:

$$k^5 - k + 5k^4 + 10k^3 + 10k^2 + 5k = 10q$$

Isolate $k^5 - k$:

$$k^5 - k = 5k^4 + 10k^3 + 10k^2 + 5k + 10q$$

Now we need to show that the right hand side is divisible by ten. We can do this as follows. First, rearrange some terms:

$$k^5 - k = 5k^4 + 10k^2 + 5k + 10k^3 + 10q$$

Now note that $10k^3$ and $10q$ are divisible by 10, the latter having come from our inductive hypothesis. So let us focus on the remaining terms, which comprise this formula:

$$5k^4 + 10k^2 + 5k$$

We can show that this is divisible by 10 by factoring out $5k$:

$$5k(k^2 + 2k + 1)$$

$$5k(k + 1)(k + 1)$$

But $k(k + 1)(k + 1)$ is an even number, which, multiplied by 5 is divisible by 10. To show that $k(k + 1)(k + 1)$ we divide into cases. If we suppose that $k$ is odd, then we have odd x even x even, which is even. If we suppose that $k$ is even, then we have even x odd x odd, which is even again.

So the inductive hypothesis is true. If $(k + 1)^5 - (k + 1)$ is divisible by $10$, then so is $k^5 - k$, and vice versa. By induction from the base case in the positive and negative directions, it is true for all $k \in \mathbb{Z}$.

Modular arithmetic wasn't used, but one basic argument which was used is linked to modular arithmetic. Namely, the argument that some $N$ {is/isn't} is divisible by $10$, then $N + 10k (k \in \mathbb{Z})$ likewise {is/isn't} divisible by $10$. This is equivalent to the modular concept that $N$ is congruent to $N + 10k$ modulo $10$, but without the formal trappings. Furthermore the argument about the evenness of $k(k + 1)(k + 1)$ also relies on congruences in disguise. Division into even/odd cases is nothing more than division into the two symbols of the mod 2 congruence. We cannot really even discuss divisibility without invoking ties to congruences. Divisibility by 10 means congruence to 0 mod 10.

share|improve this answer
1  
Have you seen my answer? –  Martin Brandenburg May 28 '13 at 23:09

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.