# Why x^p-1 Factors over GF(2) the Way It Does

Let $p$ be a prime number. We know that $F_2=GF(2)=\{0,1\}$. Let $F_2[x]$ be the ring  the polynomials with indeterminate $x$ and coefficients in $F_2$. The polynomial $(x^p-1) \in F_2[x]$ factors over $F_2$ as  follows for various $p$:

$x^3-1=(1+x) (1+x+x^2).$
$x^5-1=(1+x) (1+x+x^2+x^3+x^4).$
$x^7-1=(1+x) (1+x+x^3) (1+x^2+x^3).$
$x^{11}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}).$
$x^{13}-1=(1+x) (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9+x^{10}+x^{11}+x^{12}).$
$x^{17}-1=(1+x) (1+x^3+x^4+x^5+x^8) (1+x+x^2+x^4+x^6+x^7+x^8).$

None of the factors above can be factored anymore, hence they are irreducible over $F_2$. Let us call $x+1$ the trivial factor since the root $x= 1$ already belongs to $F_2$. But why do we have two nontrivial irreducible factors of $x^7-1$, each of degree 3, whereas $x^{13}-1$ has only one non-trivial irreducible factor of degree 12? It appears that either there is only one nontrivial factor, or the degree of all nontrivial factors is the same. Why?

# Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code

To this day, no method of finding a generator of $Z_p^*$ is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of $Z_p^*$.Keith Conrad

An $n$th root of unity in a finite field $F$ is an element $r \in F$ satisfying $r^n=1$, where $n$ is an integer. If $n$ is the smallest positive integer with this property, $r$ is called a primitive $n$th root of unity. If $r$ is a primitive $n$th root of unity, then all elements in the set $\mu_n = \{1, r, r^2, \cdots, r^{n-1}\}$ are also roots of unity. Actually, the set $\mu_n$ form a cyclic group of order $n$ under multiplication, with generator $r$.

Problem: Suppose you are given a finite field $F=GF(2^d)$ of degree $d$, and you are promised that there indeed exists a primitive $p$th root of unity $r\in F$ for $p$ prime. Find $r$, and in particular, produce a C++code that finds it.

In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.

# Euler’s Criterion for Quadratic Residues

Here we would show a beautiful application of Fermat’s Little Theorem.

An integer $a$ is a quadratic residue with respect to prime $p$ if $a \equiv x^2 \mod{p}$ for some integer $x$.

Given a prime $p$ and an integer $a$, how fast can we decide whether $a$ is a quadratic residue modulo $p$? As it turns out (courtesy to Euler), pretty fast.

# Fermat’s Little Theorem

Introduction

This is a beautiful theorem which states that the difference between a positive integer $a$ and a prime power of $a$, $a^p-a$, is divisible by $p$. It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.

# Proofs from the Book

This book, inspired from Paul Erdős‘ notion of the Book, presents some beautiful proofs to some intriguing math problems. Both the problems and proofs presented here are elegant, clear, and artistic.

# Euler’s Product Form of Riemann Zeta Function

Riemann zeta function is a rather simple-looking function. For any number $s$, the zeta function $\zeta(s)$ is the sum of the reciprocals of all natural numbers raised to the $s^\mathrm{th}$ power.

$\begin{array}{ccl}\zeta(s)&=&\displaystyle\sum_{n=1}^{\infty}{\frac{1}{n^s}}\\&=&1+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\frac{1}{5^s}+\frac{1}{6^s}+\cdots\end{array}$

Although the variable $s$ is a complex number, for the sake of simplicity, we will treat $s$ as real.  (Real numbers are a subset of complex numbers.)