LogFAQs > #929149535

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

96065