A facebook friendship problem

Do you know that facebook has its own mathematical problem? It is called the facebook friendship problem. Never heard of it?!

Well, this problem is to prove that if you pick out 6 arbitrary people on facebook, then among these 6 people, you can find 3 people such that they are all mutually friend of each other, or there are no friendships among them at all. 

For example, in the figure below, on the left we have 6 people: Amy, Ben, Cindy, Dan, Emma and Francis. If two of them are friend on facebook then we connect them by a purple line, and if they are not friend on facebook then we connect them by a blue line. 

We can see that in this example, we can pick out 3 people, which are Amy, Dan and Emma, they are all mutually friend of each other because they are connected by purple lines. The same is true for Francis, Ben and Cindy.

In the example on the right, we have 6 people: Kate, Linda, Matt, Noah, Olivia and Peter. Among them we can pick out 3 people, which are Olivia, Noah and Matt, there are no friendships among them because they are connected by blue lines. The same is for Peter, Noah and Matt. 

Power sum and Wolstenholme's theorem

In the last post, we have learned how to derive formulas for the power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k.$$

Today we will investigate some divisibility properties of the power summation $S_k(n)$. We will prove that if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_k(p-1) = 1^k + 2^k + 3^k + \dots + (p-1)^k = 0 \pmod{p}.$$

We will also investigate the following summation $$S_{-k}(n) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{n^k}.$$

There is a theorem in number theory concerning this summation, it is called Wolstenholme's theorem.

Wolstenholme's Theorem. If $p$ is a prime number $>3$ then $$S_{-1}(p-1) = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{p-1} ~=_{Q} ~0 \pmod{p^2} $$ and $$S_{-2}(p-1) = \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \dots + \frac{1}{(p-1)^2} ~=_{Q} ~0 \pmod{p}.$$

We will prove a general result, that is, if $p$ is a prime number and $k$ is not divisible by $p-1$ then $$S_{-k}(p-1) = \frac{1}{1^k} + \frac{1}{2^k} + \frac{1}{3^k} + \dots + \frac{1}{(p-1)^k} ~=_{Q} ~0 \pmod{p}.$$

Power sum

Today we will learn about how to derive the formula for power summation $$S_k(n) = 1^k + 2^k + 3^k + \dots + n^k .$$


Our main tool is the following binomial identity
$$(x+y)^k = x^k + {k \choose 1} x^{k-1} y + {k \choose 2} x^{k-2} y^2 + {k \choose 3} x^{k-3} y^3 + \dots + {k \choose {k-1}} x y^{k-1} + y^k.$$

Euclidean algorithm

In previous post, we have learned about Bézout's Lemma. Today, we will learn about Euclidean algorithm. This algorithm is used to determine the coefficients in the Bézout's equation.

Let us recall Bézout's lemma. 

Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a ~x + b ~y.$$

We use Euclidean algorithm to calculate the greatest common divisor $d$ of the two numbers $a$ and $b$, and determine the two values of $x$ and $y$ in Bézout's equation $$d = a ~x + b ~y.$$

We will see that Euclidean algorithm is motivated from a very simple and natural idea.

Bézout's lemma

Today we will learn a very beautiful result in number theory, the Bézout's lemma, it is stated as follows.

Bézout's Lemma. Let $a$ and $b$ be two integers and $d$ their greatest common divisor. Then there exist two integers $x$ and $y$ such that $$d = a x + b y.$$

Another Proof of Wilson's Theorem

In previous posts, we have learned about modulo for rational numbers. To show its application, today, we will use the language of modulo of rationals to give another proof of Wilson's Theorem.

Wilson's theorem is a well known theorem in number theory. It is stated as follows.

Wilson's Theorem. If $p$ is a prime number then $$(p-1)! = -1 \pmod{p}.$$

Modulo for rational numbers II

In the previous post, we have learned about modulo for rational numbers. Today, we will continue on this topic and will learn about some properties of this modulo.

First of all, let us look at some examples and review the definition: $$\frac{14}{5} =_{Q} ~0 \pmod{7}, $$ $$ \frac{16}{55} =_{Q} ~\frac{9}{55} =_{Q} ~\frac{2}{55} \pmod{7},$$ $$\frac{1}{4} =_{Q} ~\frac{8}{4} =_{Q} ~2 \pmod{7}, \dots$$

Definition. Let $n$ be an integer, and $\alpha$, $\beta$ two rational numbers. We say that $\alpha$ is equal to $\beta$ modulo $n$, and write $$\alpha =_{Q} ~\beta \pmod{n}$$ if and only if there exists an integer $k$ co-prime to $n$ such that $k(\alpha - \beta)$ is an integer and $$k(\alpha - \beta) = 0 \pmod{n}.$$

Modulo for rational numbers

In our series on modulo, we have learned about modulo for integer numbers. Let us recall the definition.

Definition. Let $n$, $a$, $b$ be integer numbers. We say that $a$ is equal to $b$ modulo $n$, and write $$a = b \pmod{n}$$ if and only if $a-b$ is a multiple of $n$.

For example, $$8 = 0 \pmod{4},$$ $$9 = 1 \pmod{4},$$ $$-5 = -1 = 3 = 7 \pmod{4}, \dots $$

Today, we will learn a new concept - modulo for rational numbers. Before going into the details, let us list here a few examples, so that we may roughly see what modulo for rationals is about.

Examples of modulo for rational numbers: $$\frac{8}{5} =_{Q} ~0 \pmod{4}, $$ $$ -\frac{12}{55} =_{Q} ~0 \pmod{4},$$ $$\frac{29}{15} =_{Q} ~\frac{25}{15} = \frac{5}{3} \pmod{4}$$

A proof of Wilson's Theorem using polynomial interpolation

In the last posts, we have learned about polynomial interpolation through two formulas, the Newton's interpolation formula and the Lagrange's interpolation formula. Both formulas can be used to prove the Wilson's theorem.

In this post, we will present a proof of the Wilson's theorem based on the Newton's interpolation formula. The other proof, that is, proving Wilson's theorem based on the Lagrange's interpolation formula, we leave it as a homework exercise.

Wilson's Theorem is a well known theorem in number theory. It says that if $p$ is prime number then the number $(p−1)!+1$ is a multiple of $p$.

Lagrange polynomial interpolation

Today we will continue to learn about polynomial interpolation. In the last post, we have learned about Newton's interpolation formula, today we will learn a different interpolation formula called the Lagrange interpolation formula.


We will use the following example $$P(x) = 2x^2 - 3x + 3$$

This polynomial $P(x)$ is a polynomial of degree $2$ and we can calculate that $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12.$$

The polynomial interpolation problem is the problem of reconstructing the polynomial $P(x)$, given the condition that $P(1) = 2$, $P(2) = 5$, and $P(3) = 12$.

Newton polynomial interpolation

Today, we will learn about polynomial interpolation.

Suppose we have the following polynomial $$P(x) = 2x^2 - 3x + 3$$

Let us calculate the values of the polynomial $P(x)$ for a few values of $x$ as follows $$P(1) = 2 - 3 + 3 = 2,$$ $$P(2) = 8 - 6 + 3 = 5,$$ $$P(3) = 18 - 9 + 3 = 12, \dots$$

Now, suppose that we are given the following information $$P(1) = 2, ~~P(2) = 5, ~~P(3) = 12,$$ can we reconstruct the polynomial $P(x)$?

The answer is, yes, we can. An interpolation formula enables us to reconstruct the polynomial $P(x)$ based on its values. Today, we will learn about Newton's interpolation formula, and in the next post, we will cover Lagrange's interpolation.

1 = 2012 = 2013

In previous posts, we learned about mathematical induction and we used induction to solve some problems. We can see that mathematical induction is a useful technique in problem solving. Today, we will consider two induction proofs that lead to a wrong result that $$1 = 2012 = 2013$$ Let us know if you can identify the wrong steps in the proofs.

Binomial identity

As we are learning about mathematical induction, in this post, we are going to use induction to prove the following:

• formula for the Pascal's triangle $$p_{n,k} = {n \choose k} = \frac{n!}{k! (n-k)!}$$
• the binomial identity $$(x+y)^n = x^n + {n \choose 1} x^{n-1} y + {n \choose 2} x^{n-2} y^2 + \dots + {n \choose {n-2}} x^{2} y^{n-2} + {n \choose {n-1}} x y^{n-1} + y^n$$

Mathematical induction III

Today, we will solve some more problems using mathematical induction.

Problem 7. Observe that $$\cos 2 \alpha = 2 \cos^2 \alpha - 1$$

Prove that we can write $\cos n\alpha$ as a polynomial of $\cos \alpha$.

Mathematical induction II

Today we will use induction to solve some more problems. 

Problem 4. Prove that $$1 \times 2 \times 3 + 2 \times 3 \times 4 + \dots + n (n+1)(n+2) = \frac{1}{4} n(n+1)(n+2)(n+3).$$

Mathematical induction

Today, we will learn about mathematical induction. We usually use induction to prove a certain statement to be correct for all natural numbers.

Let us use $P(n)$ to denote a statement that involves a natural number $n$. To prove that $P(n)$ is correct for all natural number $n$, an induction proof will have the following steps

Step 1: is called the initial step. We will prove that the statement $P(n)$ is correct for the case $n=0$.

Step 2: is called the induction step. This is the most important step. In this step,

• we assume that for any $0 \leq n \leq k$, the statement $P(n)$ is correct;
• with this assumption, we will prove that the statement $P(n)$ is also correct for the case $n=k+1$.

With these two steps, by the mathematical induction principle, we conclude that the statement $P(n)$ must be correct for all natural number $n$.

Pascal's triangle

Today, we will look at a famous number pattern, the Pascal's number triangle.

Pascal's triangle

Pythagorean triples

In geometry, there is a well known theorem, called the Pythagorean Theorem, which says that in a right triangle, the square of the hypotenuse is equal to the sum of squares of the other two sides. 

Pythagorean Theorem: $BC^2 = AB^2 + AC^2$

That is why we call the equation $$x^2 + y^2 = z^2$$ the Pythagorean equation and its solution $(x,y,z)$ is called a Pythagorean triple. Of course, we only consider integer solutions.

Today, we will solve the Pythagorean equation and show that this equation has an infinite number of solutions.

Wilson's Theorem

Today, we will study Wilson's Theorem - a theorem concerning prime numbers. Wilson's theorem says that if $p$ is a prime number then the number $(p-1)! + 1$ will be divisible by $p$.

Here, the notation $n!$ denotes $$n! = 1 \times 2 \times 3 \times \dots \times n.$$

For example,

• $1! + 1 = 2$ is divisible by $2$
• $2! + 1 = 3$  is divisible by $3$
• $4! + 1 = 25$  is divisible by $5$
• $6! + 1 = 721$  is divisible by $7$

Some problems on prime numbers

In previous posts, we have learned about prime numbers, and we know from Euclid's Theorem that there exists an infinite number of primes. In this post, we continue to look at prime numbers. Leading mathematicians like Fermat, Euler, Gauss were all fascinated by prime numbers. There are many problems about primes that even the statements are simple, but they still remain unsolved even to this day.

Euclid's theorem on prime numbers

Continuing with our story about prime numbers, today we will prove that there exists an infinite number of primes. This is called the Euclid's theorem on prime numbers. This theorem has a very simple proof but it is probably one of the most beautiful proofs ever in mathematics.

Prime numbers

Today we will learn about prime numbers - a basic building block of arithmetic.

A prime number is a natural number greater than 1 and has no divisors other than 1 and itself. For example, the numbers 2, 3, 5, 7, 11, 13 are prime numbers. The number 9 is not a prime number because it is divisible by 3. The number 2012 is not a prime number because it is divisible by 2.

The Fermat's point of a triangle II

In the previous post, we have analyzed the Fermat's problem, the problem of finding a point $M$ for a given triangle $ABC$ such that $MA + MB + MC$ is the minimum.

the Fermat's problem: find $M$ so that $MA + MB + MC$ is minimum

The Fermat's point of a triangle

In previous posts about modulo, we learn about the mathematician Fermat and his famous problem $$x^n + y^n = z^n.$$

Today, we will look at a geometry problem that bears his name. As we already know, Fermat was not a professional mathematician, but was a lawyer. He was doing math probably just for fun and most of his achievements that we know of today originated from his letters to his friends and also from his occasional writings on the margin of books that he read. The most famous is, of course, the problem $x^n + y^n = z^n$ and his note "I have found a beautiful proof but there is not enough space" that he wrote on the margin of the book by Diophantus.

The problem that we investigate today was raised in a letter that Fermat sent to an Italian mathematician, Torricelli. In his letter, Fermat challenged Torricelli to find a point such that the total distance from this point to the three vertices of a triangle is the minimum possible. Well, this problem was not hard for Torricelli. Since Torricelli knew how to find such a point, today some people refer to this point as the Fermat's point, and others refer it as the Torricelli's point of the triangle.

the Fermat's problem: find a point $M$ so that $MA + MB + MC$ is minimum

A problem about finding shortest path and a property of the ellipse

Today we will look at two problems that seem to be unrelated. The first one is a beautiful geometry problem about finding shortest path and the other one is about a property of an ellipse.

But first, let us introduce the ellipse. An ellipse is drawn below.

for any point $P$ on the ellipse, $PF_1 + PF_2 = \ell$

Solve for special cases first!

I would like to share with you a lesson that I have learnt. That is when facing a problem and we do not know what to do, the first thing we can do is to look at special cases of that problem. Investigating special cases can help us gain a greater understanding of the problem. To illustrate the point, let us solve some problems.

modulo - Part 6

We recall the definition of modulo. Two numbers $a$ and $b$ are said to be equal modulo $n$ if and only if $a-b$ is a multiple of $n$, and we write $a = b \pmod{n}$. For example, $9 = 1 \pmod{8}$ and $14 = -2 \pmod{8}$. 

In our usual arithmetic, we picture our integer numbers lying on the number line and we do addition and multiplication like this $2 + 7 = 9$, $2 \times 7 = 14$, etc...

our number line

modulo - Part 5

Today we will learn about Fermat's "little" Theorem. We will see that Fermat's little Theorem is very useful in modulo arithmetic. The theorem asserts that for any prime number $p$ and for any number $a$ not divisible by $p$,
$$ a^{p-1} = 1 \pmod{p} . $$

modulo - Part 4

One of the all-time famous mathematicians is Pierre de Fermat. He is a French mathematician and lived in the 17th century.

To mention Fermat, we must mention "his problem" - the Fermat's last problem. The problem that had challenged generations of mathematicians. Probably the reason that his problem is so well-known and attracted so much effort from top mathematicians as well as young school students is that it is stated so simple and that a secondary school student can understand it.

The Fermat's last problem is stated as follows. Prove that for any $n \geq 3$ the following equation does not have non-trivial solutions  

$$ x^n+y^n=z^n $$

Non-trivial solutions here mean non-zero solutions. This is because if  $x$, $y$ or $z$ is equal to 0 then the equation becomes trivial.

modulo - Part 3

Today, we are going to look at some more examples about modulo.

Example 1: Prove that $11 + 2011^{2012} + 2012^{2013}$ is divisible by 13.

modulo - Part 2

Last time, we have learnt about modulo. Two integers $a$ and $b$ are said to be equal modulo $n$, denoted by $a = b \pmod{n}$, iff $a-b$ is divisible by $n$.

For example, $15 = 3 \pmod{4}$ and $99 = -1 \pmod{10}$.

modulo - Part 1

Today we will look at an important concept in number theory -- the concept of modulo. Two integer numbers $a$ and $b$ are said to be equal modulo $n$ iff they have the same remainder when divided by $n$. Or equivalently, iff $(a-b)$ is divisible by $n$. We will write $a = b \pmod{n}$.

What does a 4-dimensional space look like?

We often hear people in physics and mathematics talking about 4-dimensional, 5-dimensional spaces, etc... so what are those spaces? how do we picture these high dimensional spaces?

Similar triangles

Today, we are going to learn about similar triangles. We will use similar triangles to give a proof of Pythagorean Theorem. 

Caveman's multiplication

Today, I am going to tell you a method of doing multiplication by the ancients. I do not remember the name of this method, nor do I know when this method was invented. Let us just call it "the cave-man's multiplication method"!

Morley's Theorem

In a triangle $ABC$, draw the trisectors of the angles $A$, $B$, $C$. These trisectors intersect at $A'$, $B'$ and $C'$ as in the figure below. Prove that the triangle $A'B'C'$ is an equilateral triangle.