Go Bugs Go!

How to construct a regular polygon with 15 sides

To feed your curiosity, today we will look at a compass and straightedge construction of the regular polygon with 15 sides and we will show that there is a connection between this construction problem with the measuring liquid puzzle that we have learned from our previous post.

Measuring liquid puzzle

Today we will look at a brainteaser puzzle: "how to measure out exactly 1 liter of water using a 3-liter jug and a 5-liter jug." We will analyse this puzzle to see that, despite its innocent look, this puzzle has a close connection with the linear Diophantine equation.

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