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 »

This is elementary, yet useful and interesting.

Statement: All eigenvalues of a Hermitian matrix are real.

Proof:

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.
The Math Book

The Math Book

This book presents glimpses (literally, with one page picture and one page description to each topic) to some selected people/ideas/discoveries/milestones from Mathematics. Inspiring. Someone with a college math/CS background is bound to be enthralled. The most remarkable part of this book is that it never goes deep into any topic, it just gives a flash and then diving deep is up to you. I bought this book for my little sister in mind, but I will keep it myself, see!

This video, from http://dimensions-math.org, gives an awesome mathematical introduction to higher physical dimensions. There are several videos, available with subtitle and narration in several languages. You can download them freely.

[blip.tv http://blip.tv/play/gYY47OUcAg?p=1 width=”550″ height=”443″]

On the other hand, this video, from http://www.tenthdimension.com/, presents higher dimensions from a different viewpoint.. Baffling.

You don’t need to go to stars to feel the amazing. Our body — the mechanism of life — is an incomprehensible wonder. This video shows how our cellular machinery creates one molecule of protein.

 

Compared to the age and expanse of the universe, we humans are so small and insignificant. We should be more humble.

 

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 »

If we have a random variable X and any number a, what is the probability that X \geq a? If we know the mean of X, Markov’s inequality can give an upper bound on the probability that X.  As it turns out, this upper bound is rather loose, and it can be improved if we know the variance of X in addition to its mean. This result is known as Chebyshev’s inequality after the name of the famous mathematician Pafnuty Lvovich Chebyshev. It was  first proved by his student Andrey Markov who provided a proof in 1884 in his PhD thesis (see wikipedia).

Read the rest of this entry »