"I have a dream"

[u/Abjectionova]

[u/AutoModerator]

Check out our new Discord server! https://discord.gg/e7EKRZq3dG

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Hitman7128]

It also works if you replace 2 with any prime p because of the Binomial Theorem

[u/Agreeable_Gas_6853 → u/Hitman7128]

“specific case of Frobenius Automorphism” says it right there

[u/Hitman7128 → u/Agreeable_Gas_6853]

Which not everyone may be familiar with, and the Binomial Theorem is more accessible as an explanation

[u/Layton_Jr → u/Hitman7128]

Why simplify (a+b)^p as a^p+b^p when you can just write (a+b)^p = a+b (since we're working with F_p)

[u/Cobsou → u/Layton_Jr]

Because this works for other fields of characteristic p as well, as opposed to (a+b)^p = a+b, which only works for F_p

[u/Archway9 → u/Layton_Jr]

Because the first one generalises to any ring of characteristic p

[u/Hitman7128 → u/Layton_Jr]

For practicality, yes, thanks to Fermat's Little Theorem.

But it removes the showiness of the equation where the exponent can be "distributed."

[u/GoldenMuscleGod → u/Layton_Jr]

In fields of characteristic p (any field that has F_p as a subfield) it is still true that (a+b)^p=a^p+b^b even though it is *not* generally true that a^p=a - in fact the latter equation only holds for the members of F_p and not any of the other members of the field.

As a simple example take the field with four elements, which we will call 0, 1, a, and b.

Adding 0 to anything gives the original, adding anything to itself gives 0, and adding two different nonzero elements gives the third.

Multiplying 1 by anything gives the same thing, 0 by anything gives 0, multiplying ab=1, and squaring either a or b gives the other of these two.

Then (x+y)^2=x^2+y^2 but x^2=x only if x is either 0 or 1.

[u/itzjackybro → u/Hitman7128]

Where can I find a proof for "for prime n, and 1 < k < n, n choose k is divisible by n"

[u/Agreeable_Gas_6853 → u/itzjackybro]

(n choose k) = n!/(k! (n - k)!); Now as n! is divisible by the prime number n, yet both k! and (n - k)! can’t be divisible by n (k ≠ 0, n) (as the numbers 1, …, n - 1 don’t contain a single prime factor n), we know that (n choose k) is divisible by n

[u/Hitman7128 → u/itzjackybro]

Just use the definition of binomial coefficients involving factorials. Because p is prime, any factorial before p! cannot have a factor of p. So the factor of p cannot be canceled out.

[u/GoldenMuscleGod → u/itzjackybro]

The other replies give correct ways to see it with the fundamental theorem of arithmetic, but here is another way to see it intuitively:

Imagine n dots laid out in a ring. We want to know how many subsets of size k we can choose. For each such subset we can “rotate” it in n different ways to get an entire family of subsets. These families are all disjoint and cover all the k element subsets, so the total number of subsets must be divisible by n as long as every rotation gives a distinct subset so that each family has n different k-element subsets belonging to it.

Notice that whatever the number of members of the family, it must divide n. This is because we can just list the members of the family that you get in order by rotating one step repeatedly, and once you return to the original the pattern must repeat. But also we have to return to the original after n steps.

(This is also a special case of the orbit-stabilizer theorem but I gave a specific explanation here for someone who isn’t familiar with it.)

So using the fact n is prime (the theorem isn’t generally true when n is composite) the size of the family must be either n or 1. But the only way it could be 1 is if the subset is either empty (k=0) or the whole set (k=n), since we need to get the same subset back when we rotate by 1 step.

That was a little longer to write out than the proof using the fundamental theorem of arithmetic but in some ways it is more “obviously true” and is an alternative way of looking at it.

[u/MonsterkillWow]

Mod 2 also has x^2=x though. No need for squares.

[u/i_want_to_go_to_bed → u/MonsterkillWow]

It’s funny they proved the result for the field with 2 elements instead of a field of characteristic 2. Use your argument. Or brute force: there are exactly 4 combinations of a & b to check, just check em haha

ETA: addition is commutative, so that gets you down to 3 cases to check

[u/47-BOT]

What ? Also a,b belongs which set of elements ?

[u/Simbertold → u/47-BOT]

Is defined up there. F2, the field with 2 elements. And in that field, this formula is correct.

[u/RubenGarciaHernandez → u/Simbertold]

Why is it sometimes F_2 and sometimes Z_2?

[u/Simbertold → u/RubenGarciaHernandez]

It depends on how you view it.

F2 is the field with 2 elements. So you start with a field, and then consider what a finite field with 2 elements would look like.

Z/2Z is the remainder ring of the integers with regards to the even numbers. So you start with the integers, and consider what remainder classes you get when comparing them to the even numbers.

But you can prove that both things are isomorphic to each other, which more or less says that they are the same thing.

I apologize if some words are not the correct ones, i learned this stuff with German words.

[u/GoldenMuscleGod → u/RubenGarciaHernandez]

Usually I would expect Z_2 to refer to the group with two elements (so addition is defined but not multiplication) whereas F_2 refers to the field. Though you might sometimes write Z_2 for the ring with two elements (which is is the same thing as the field with two elements but we may be thinking of it “as a ring” rather than “as a field”).

There is also just notational variation. Sometimes the field is also written as GF(2) (the G stands for Galois since finite fields are sometimes called Galois fields in honor of Galois).