Decimal representation of rational numbers and fermat's little theorem. Common thread.

Question

A decimal representation of a rational number is necessarily either terminating or non-terminating and repetitive. This comes from the fact that when you are dividing there are only a finite set of possible remainders (remainder is always less than the divisor). As you go on dividing for decimal representation, the remainder has to repeat.

Similarly, in finite fields, as you go on raising the power of an element, the product has to repeat because there are finite number of possible answers. This leads to Fermat's little theorem.

In both cases, the finiteness of the possible set of answers is leading to these important and beautiful results.

Can you suggest some more examples of this kind - understandable by school and junior college students?

Answer 1

Let $A$ be a finite set, and define some function $$ f:A\rightarrow A. $$ Start with some $x_0\in A$ and let $x_n=f(x_{n-1})$.

What you can show by the pigeonhole principle is that because there is a finite number of outputs, and you're using the same function, you at some point will always need to repeat. Both of your examples are cases of this.

So any repeated function you want on a finite set will provide you will another example.

You can also look into other pigeonhole principle examples but those can get quite weird

Answer 2

An interesting fact is that if the function f(n) is sufficiently like a random function then the birthday paradox comes into play. If there are n possible values, then your sequence may enter a cycle after about $\sqrt n$ steps.

An example is the pollard-rho algorithm where f(x) = (x^2 + c) modulo p.