Pages

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}$$