Current Events > Why is x^5 - x always divisible by 10 for any positive integer x?

(+) Yeah! (+)

Well?
---

... because of how multiplication works...?
---

Hint: x^5 - x = x (x^2 - 1)(x^2 + 1)
---

Something about how it's the same as x(x^4 - 1).
And then you say that divisible by give numbers can be written as 5n.
One way to brute force it could be to explore all five kinds of numbers and plug them into this expression and see what happens:
(5n - 2)
(5n - 1)
5n
(5n + 1)
(5n + 2)
---

Manocheese posted...

Hint: x^5 - x = x (x^2 - 1)(x^2 + 1)

Oh yeah that's an even better representation
---

So, you could also do it with

5n
(5n + 1)
(5n + 2)
(5n + 3)
(5n + 4)


And the trick is to show that when you plug in all these into the expression it's divisible by 5. The factorizations help because you just need to show that one factor is divisible by 5.
Wolframalpha can help us, I use it to expand the (x^4 - 1) factor. Of course, if you do it by hand, you can use the binomial theorem instead. It's not so bad. The expanded form is the most straightforward IMO because we can just look at the terms and conclude they're all individually divisible by 5:

5n: This is trivial to show even without the factorization.
(5n + 1): https://www.wolframalpha.com/input/?i=%285n+%2B+1%29%5E4+-+1
(5n + 2): https://www.wolframalpha.com/input/?i=%285n+%2B+2%29%5E4+-+1
(5n + 3): https://www.wolframalpha.com/input/?i=%285n+%2B+3%29%5E4+-+1
(5n + 4): https://www.wolframalpha.com/input/?i=%285n+%2B+4%29%5E4+-+1

EDIT: If we're using Wolframalpha, we could of course have done the exact same thing on the original x^5 - x form as well. The factorizations just make things easier to do by hand.
---

Because math
---

Prove it works for n=1.

Assume it works for k<n.

Prove it works for k+1.
---

Shut the fuck up
---

Don't even need to factorialize, just calculate

1^5 = 1, 1-1 = 0 ~ 0mod5
2^5 = 32, 32-2 = 2 ~ 0mod5
3^5 = 243, 243-3 = 240 ~ 0mod5
4^5 = 1024, 1024-4 =1020 ~ 0mod5
---

Use induction. Verify it for x = 1.

Suppose x^5-x is divisible by 10.

Then (x+1)^5 - (x+1) =

x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 - x - 1 =

(x^5 - x) + 5x^4 + 10x^3 + 10x^2 + 5x =

(x^5 - x) + x*(5x^3 + 5) + 10*(x^3 + x^2)

The first part is divisible by 10

The second part is divisible by 10 (you can verify further)

The third part is divisible by 10
---

ZeldaMutant posted...

Don't even need to factorialize, just calculate

1^5 = 1, 1-1 = 0 ~ 0mod5
2^5 = 32, 32-2 = 2 ~ 0mod5
3^5 = 243, 243-3 = 240 ~ 0mod5
4^5 = 1024, 1024-4 =1020 ~ 0mod5

You at least also need to argue why it's enough to show for 1-4.
---

scar the 1 posted...

ZeldaMutant posted...

Don't even need to factorialize, just calculate

1^5 = 1, 1-1 = 0 ~ 0mod5
2^5 = 32, 32-2 = 2 ~ 0mod5
3^5 = 243, 243-3 = 240 ~ 0mod5
4^5 = 1024, 1024-4 =1020 ~ 0mod5

You at least also need to argue why it's enough to show for 1-4.

And also why it's enough to show divisible by 5. Or more precisely make the fairly trivial argument that the expression is also always divisible by 2.

@konokonohamaru how do you know x(5x^3 + 5) is a multiple of 10? The only idea I got is using induction again.

EDIT: Nvm, got it.
---

You guys nailed it. Actually, x^p - x is divisible by 2p whenever p is an odd prime. Though the general proof is way more difficult than for specific values.
---

Oh divisible by 10. For some reason i thought divisible by 5.
---

FLOUR posted...

Actually, x^p - x is divisible by 2p whenever p is an odd prime.

Interesting. Don't feel like proving it tho :v
---

FLOUR posted...

You guys nailed it. Actually, x^p - x is divisible by 2p whenever p is an odd prime. Though the general proof is way more difficult than for specific values.

so this was some kind of a test?
---

konokonohamaru posted...

Use induction. Verify it for x = 1.

Suppose x^5-x is divisible by 10.

Then (x+1)^5 - (x+1) =

x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1 - x - 1 =

(x^5 - x) + 5x^4 + 10x^3 + 10x^2 + 5x =

(x^5 - x) + x*(5x^3 + 5) + 10*(x^3 + x^2)

The first part is divisible by 10

The second part is divisible by 10 (you can verify further)

The third part is divisible by 10

This is great.
---

FLOUR posted...

You guys nailed it. Actually, x^p - x is divisible by 2p whenever p is an odd prime. Though the general proof is way more difficult than for specific values.

Oh, right, Fermat's small theorem. I couldn't figure out a proof, so I checked Wikipedia and woah, there's quite a few. Most of them seem unintuitive, in the sense that you wouldn't approach a number theoretic problem from a weird necklace-counting angle. But in the middle there's a proof that uses tools mentioned in this thread, tools I tried using but got stumped. The trick was a very fascinating property of a certain object named after another famous mathematician. A property I never spotted despite using the object quite a bit. I've learned something today.
---

ZeldaMutant posted...

FLOUR posted...

You guys nailed it. Actually, x^p - x is divisible by 2p whenever p is an odd prime. Though the general proof is way more difficult than for specific values.

Oh, right, Fermat's small theorem. I couldn't figure out a proof, so I checked Wikipedia and woah, there's quite a few. Most of them seem unintuitive, in the sense that you wouldn't approach a number theoretic problem from a weird necklace-counting angle. But in the middle there's a proof that uses tools mentioned in this thread, tools I tried using but got stumped. The trick was a very fascinating property of a certain object named after another famous mathematician. A property I never spotted despite using the object quite a bit. I've learned something today.

Do elaborate please
---

My intuition was to brute force the proof by using the multinomial expansion and looking at the coefficients.

Looked up the necklace proof... very clever!
---

scar the 1 posted...

ZeldaMutant posted...

FLOUR posted...

You guys nailed it. Actually, x^p - x is divisible by 2p whenever p is an odd prime. Though the general proof is way more difficult than for specific values.

Oh, right, Fermat's small theorem. I couldn't figure out a proof, so I checked Wikipedia and woah, there's quite a few. Most of them seem unintuitive, in the sense that you wouldn't approach a number theoretic problem from a weird necklace-counting angle. But in the middle there's a proof that uses tools mentioned in this thread, tools I tried using but got stumped. The trick was a very fascinating property of a certain object named after another famous mathematician. A property I never spotted despite using the object quite a bit. I've learned something today.

Do elaborate please

My idea was to use induction and the binomial expansion theorem.

To start, x^p - x is obviously divisible by 2, since odd minus odd is even. In fact, Fermat's little theorem is "x^p - x is divisible by p if p = prime", and that's what we're going to prove by induction.

Induction start step: x=1. 1^p - 1 = 0, which is divisible by any p.

Assume the theorem holds for x. Then for x+1,

(x+1)^p - (x+1) = 1*x^p + [a whole mess of binomical coefficients] + 1*1^p - (x+1) = x^p - x + [mess]

As per the assumption, x^p - x is divisible by p. So all we have to prove is that [mess] is divisible by p.
Feels impossible, right? And how do I get the fact that p is prime involved? So I gave up.

But wikipedia gave the answer. As I knew, the binomial coefficients can be found in Pascal's Triangle, but I had never realized one beautiful property of the triangle and the coefficients.

https://media.sciencephoto.com/image/a9000148/800wm/A9000148-Pascal_s_triangle.jpg

Now let's look at row 5, aka the (a+b)^5 coefficients. 1, 5, 10.
As for row 7, it's 1, 7, 21, 35.
And for row 11, it's 1, 11, 55, 165, 330, 462.

See the pattern? They're all divisible by the row number! This holds for all primes! The only expections are the 1s, but those are outside [mess], so no need to worry. So, if every coefficient in [mess] is divisible by p, then clearly the whole [mess] is divisible by p.

Now that we spotted this, we just have to prove it. The coefficients can be calculated as (n choose m), aka n!/(m!(n-m)!), where m runs from 0 to n. We need to prove that this is divisible by n if n=prime and 0<m<n.

n! is obviously divisible by n.

Because m is smaller than n, m! (1*2*3...*m) does not include n in the product. Furthermore, since n is prime, it cannot be the product of any of the numbers in m!. Thus, m! is not divisible by n. The same logic holds for (n-m)!.

So, we have an expression where the numerator is divisible by n, but the denumerator isn't. And since n is prime, there's nothing in the denumerator to divide it either. So whatever integer the division results in, it has to be divisible by n!
---

scar the 1 posted...

Oh divisible by 10. For some reason i thought divisible by 5.

If it's divisible by 10, it's divisible by 5 anyway.

Questionmarktarius posted...

scar the 1 posted...

Oh divisible by 10. For some reason i thought divisible by 5.

If it's divisible by 10, it's divisible by 5 anyway.

Right, but divisible by 5 does not by itself imply divisible by 10.

ZeldaMutant posted...

Oh nice, yeah that makes sense
---