# Binomial formula in $GF(2^m)$

there is a binomial formula:

$$(x+y)^n=\displaystyle\sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$$

When operations are done in $GF(2^m)$ then all positive integers are reduced $\bmod2$, so binomial formula for $n=2^i$ in $GF(2^m)$ is:

$$(x+y)^{2^i}=x^{2^i} + y^{2^i}$$

So now the question. If there are reduced all binomial coefficients $\binom{n}{k}$, then why exponents like $2^i$ are not reduced?

-
Working in finite fields reduces coefficients, not exponents. – Qiaochu Yuan May 21 '11 at 11:52
Because only addition and multiplication involve elements of the field (or another ring). The exponents are always integers. – Jyrki Lahtonen Jul 8 '11 at 17:08

It's because multiplication by a coefficient is periodic in the coefficient with the right period $P$: $$(a+P)\cdot b = a\cdot b + P\cdot b \equiv a\cdot b \quad {\rm mod} \quad P$$ because the equivalence modulo $P$ is defined so that it allows me to subtract multiples of $P$ such as $P\cdot b$ above - while powers are not periodic functions of the exponent with the period $P$: $$a^{b+P} \neq a^b \quad {\rm mod}\quad P$$ For a simple example, look at powers of $2$ computed modulo $2$: $$2^0 = 1, \quad 2^1 = 2 = 0, \quad 2^2 = 4 = 0, \dots$$ All the following powers are equal to $0$ modulo $2$ but the initial one, the zeroth power, is not. (Pick more complicated numbers to get the point - to see how complicated the powers may be especially if $P$ is large.) So the results of the exponentiation are not periodic as a function of the exponent, and you are never allowed to simplify the exponents by considering them modulo $P$.
In a finite field $\mathbb{F}_q$, exponentiation to positive powers is periodic, but with period $q-1$, not $q$. This leads to the notion of a reduced polynomial (possibly in several variables) over a finite field and then to a proof of the Chevalley-Warning theorem. Saying "So the results of the exponentiation are not periodic as a function of the exponent" is displaying ignorance of a lot of important algebra and number theory. – Pete L. Clark May 21 '11 at 21:54
For example $\{0,1,x,x+1\}$ with $2=0$ and $x^2=x+1$.