Category Archives: elementary

The smallest number paradox goes like this: consider the natural numbers: 0,1,2,3,… . Each can be specified by a string of characters. For example, “0” itself specifies 0. However, on my computer there are only finitely many bits. Therefore, only finitely many numbers can be specified as a string on my computer. In other words, […]

## Fibonacci sequence modulo m

The Fibonacci sequence is an infinite sequence of integers $f_0,f_1,f_2,\dots$ defined by the initial values $f_0 = f_1 = 1$ and the rule $$f_{n+1} = f_n + f_{n-1}$$ In other words, to get the next term you take the sum of the two previous terms. For example, it starts off with: $$1,1,2,3,5,8,13,21,34,55,\dots$$ You can define […]

## What is a Liouville number?

An irrational number $r$ is called a Liouville number if for every positive integer $n$ there exists integers $p$ and $q \gt 1$ such that $$| r – p/q | \lt 1/q^n.$$ The requirement that $q \gt 1$ is crucial because otherwise, all irrational numbers would satisfy this definition. Liouville numbers are transcendental. In an […]

## All set endomorphisms of a finite field are polynomial

Let $F$ be a finite field. Did you know that given any function $\varphi:F\to F$, there exists a polynomial $p\in F[x]$ such that $\varphi(a) = p(a)$ for all $a\in F$? It’s not hard to produce such the required polynomial: $$p(x) = \sum_{a\in F} \left( \varphi(a)\prod_{b\not= a}(x – b)\prod_{b\not=a}(a-b)^{-1} \prod \right)$$ This works because every […]

## When Is Squaring and Cubing a Group Homomorphism?

Let $G$ be a group. Define $\varphi:G\to G$ by $\varphi(x) = x^2$. When is $\varphi$ a homomorphism? Clearly, $\varphi$ is a homomorphism whenever $G$ is abelian. Conversely, if $\varphi$ is a homomorphism then for any $x,y\in G$, we get $xyxy = \varphi(xy) = \varphi(x)\varphi(y) = x^2y^2$. So, $xyxy = xxyy$. Canceling the $x$ from the […]