Complex number

Today we will learn about the complex numbers. The crucial point about complex numbers is that we accept a very special number that we will denote it by $i$. This number $i$ is very special because it satisfies the following identity $$i^2 = -1.$$

So a complex number will have the form $$a + ib$$ where $a$ and $b$ are two real numbers. When $b=0$ then $a + ib = a$ is just a normal real number, and when $a=0$ then $a + ib = ib$ is called a pure imaginary number. Here are some examples of complex numbers: $$1+ i, ~~ 2 - 3i, ~~ -\sqrt{3} + 4i, ~~5i - 4, ~~6, ~~i, ~~-3i, ~~4 + 2i, \dots$$

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.