You are currently browsing the category archive for the ‘Number Theory’ category.

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

An integer is a quadratic residue with respect to prime if for some integer .

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

**Introduction**

This is a beautiful theorem which states that the difference between a positive integer and a prime power of , , is divisible by . 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.

Riemann zeta function is a rather simple-looking function. For any number , the zeta function is the sum of the reciprocals of all natural numbers raised to the power.

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