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.

Continue reading “Euler’s Criterion for Quadratic Residues”

Advertisements

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.

Continue reading “Fermat’s Little Theorem”

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

Continue reading “Euler’s Product Form of Riemann Zeta Function”