Why is the last digit of n^5 equal to the last digit of n? [video] | Hacker News Reader

Why is the last digit of n^5 equal to the last digit of n? [video]

youtube.com

17 pointsiamzlatan8 comments

This reminds me why I don't like induction proofs. Although sound, almost by definition no insight can be obtained from it for either why the proposition is true, or why the proof itself is valid.

Here's another proof I just though of that doesn't use induction: Let's prove that x^5-x is divisible by 10.

  x^5-x = x(x^4-1) = x(x^2+1)(X^2-1)

We want to prove that among these 3 multiplied elements, we can find the factors 2 & 5. 2: If x is even, it's x. If x is odd, it's the other ones. 5: Consider the following table of : x | x^2 (mod 5)

  x | x^2 | Which element is divisible by 5
  -------------------------------------------
  0    0       x
  1    1       x^2-1
  2    4       x^2+1
  3    4       x^2+1
  4    1       x^2-1

so we get that in all cases there is a factor of 5 as well.

Not sure this provides more insight into why the proposition is true, but IMO this proof feels more valid.

You can do it without a table by factoring

x (x^2-1) (x^2+1) =

x (x-1) (x+1) (x^2 - 4 + 5) =

x (x-1) (x+1) ((x-2)(x+2) + 5)

Now one of the five consecutive numbers (x-2), (x-1), x, (x+1), (x+2) must be divisible by 5, so the whole is as well.

I agree with you about induction.

I find proof by induction very intuitive: “If every ‘legal’ step holds, then any way of chaining legal steps also holds”. There can be a lot of information gleaned from the steps (operational semantics for example).

Playing around with induction on church encodings and other inductively defined structures certainly helped me to build the intuition though.

That leads me to think what can be even more unsatisfying proof.

How about the following: It is easy to see that the last digit of x^5 is same as k^5, where k is the last digit of x. Then the problem reduces to proving that the ten possibilities, 0^5, 1^5, 2^5, ... 9^5 ends respectively in 0, 1, 2, ...9.

Intuitively, induction proofs are valid because you're checking the theorem for every natural number n. Of course, you're doing that in a clever way because the naive way would take a little too long, but still that's what it is all about.

TL;DW: proof by induction.

Basis is trivial: 0⁵ = 0.

Inductive step:

Assume that n⁵ - n is divisible by 10.

We'll show that (n + 1)⁵ - (n + 1) is divisible by 10, too.

(n + 1)⁵ - (n + 1)

= n⁵ + 5n⁴ + 10n³ + 10n² + 5n + 1 - n - 1

= (n⁵ - n) + 10(n³ + n²) + 5n(n³ + 1)

Notice that:

* (n⁵ - n) is divisible by 10, as per the inductive hypothesis;

* 10(n³ + n²) is obviously divisible by 10;

* either n or n³+1 is even, so 5n(n³ + 1) is divisible by 10.

QED.

Dupe: https://news.ycombinator.com/item?id=15572593

Alternative proof:

From Fermat's little theorem: n^5 ≡ n (mod 5).

Therefore (n^5 - n) is divisibe by 5.

(n^5 - n) is always even, so it's also divisble by 10.

Reply on news.ycombinator.com