# 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.

# 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.)