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

Read the rest of this entry »

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.

Read the rest of this entry »

Proofs from the Book

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.

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

Read the rest of this entry »