Re:Why is the last digit of n^5 equal to the last digit of n...
by air7 on Friday November 03, 2017 @08:53PM
(#15623240)
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.
Re:Why is the last digit of n^5 equal to the last digit of n...
by davemp on Friday November 03, 2017 @09:51PM
(#15623417)
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.
Re:Why is the last digit of n^5 equal to the last digit of n...
by karthickgururaj on Saturday November 04, 2017 @12:04AM
(#15623713)
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.
Re:Why is the last digit of n^5 equal to the last digit of n...
by kleiba on Friday November 03, 2017 @08:57PM
(#15623254)
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.
Here's another proof I just though of that doesn't use induction: Let's prove that x^5-x is divisible by 10.
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) 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.
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.
Playing around with induction on church encodings and other inductively defined structures certainly helped me to build the intuition though.
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.
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.
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.