Intereting Posts

Nonattacking rooks on a triangular chessboard
Construct a finite field of 16 elements and find a generator for its multiplicative group.
Does $\mathcal{L}^2(\mathbb{R})$ form a metric space with this distance/similarity measure?
$1^n +2^n + \cdots +(p-1)^n \mod p =$?
Suggestions for high school?
$W_1^\perp + W_2^\perp = (W_1 \cap W_2 )^\perp$: Can a set be a function? Can two such “functions” be composed?
Why are smooth manifolds defined to be paracompact?
When to learn category theory?
What is a good way to find an algebraic field extension that is not separable and not normal?
Is it possible for the number created by ordering $1$ to $n$ where $n > 1$ be a palindrome?
A right angle at the focus of a hyperbola
Proving the snake lemma without a diagram chase
How to solve the equation, $(x+y)(y+z)(x+z) = 13xyz$ for $x,y,z \in Z$.
Must an ideal contain the kernel for its image to be an ideal?
Prove every strongly connected tournament has a cycle of length k for k = 3, 4, … n where n is the number of vertices.

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!

- Method to eliminate $x$ between the equation $x^2 + ax + b = 0$ and $xy+ l(x + y) + m = 0$
- Fibonacci sequence divisible by 7?
- Why don't we define division by zero as an arbritrary constant such as $j$?
- How many 0's are in the end of this expansion?
- How many ways are there to define sine and cosine?
- Proportional to 2 Separate Variables vs. Proportional to Product of 2 Variables
- Proof the maximum function $\max(x,y) = \frac {x +y +|x-y|} {2}$
- Analogy between prime numbers and singleton sets?
- Finding $x^4 + y^4 + z^4$ using geometric series
- System of equations: $x^2+y=7, y^2+x=11$

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).

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

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.

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

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

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).

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.

- Continuity of analytic function implies convergence of power series?
- What hexahedra have faces with areas of exactly 1, 2, 3, 4, 5, and 6 units?
- Lee, Introduction to Smooth Manifolds Solutions
- Solving Special Function Equations Using Lie Symmetries
- Calculating probability for forming a triangle
- Prime $p$ with $p^2+8$ prime
- Does measurability/continuity of a mapping follow that of its sections?
- Express logic puzzles with proposition calculus notation
- homomorphism $f: \mathbb{C}^* \rightarrow \mathbb{R}^*$ with multiplicative groups, prove that kernel of $f$ is infinite.
- Limit: $\lim_{x\to 0}\frac{\tan3x}{\sin2x}$
- Reference book on measure theory
- How to calculate Pr(Diseased | 2 Positive Tests)?
- Positive part of $y$ with $y\in L^2(0,T; H_0^1(\Omega))$ and $y'\in L^2(0,T; H^{-1}(\Omega))$
- Show that any set in a metric space can be written as the intersection of open sets
- Shortest distance between two general curves using matlab