# Category Archives: Number theory

## Automorphic Numbers

In this post we discuss automorphic numbers. Note that all numbers involved in this post are non negative integers.

Definition: Let $x$ have $n$ digits in its base $10$ representation. Then $x$ is said to be automorphic if $x^2\equiv x\pmod {10^n}$.

In our base $10$ representation this means that the last $n$ digits of $x^2$ are precisely $x$. In other words, the digits of $x$ are appended to $x^2$. Note that since the digits of $x$ are appended to $x^2$ they are also appended to $x^m$ for any $m\ge 1$.

A list of some automorphic numbers can be found here. Our aim here is to characterize all such numbers in base $10$.

Theorem: The automorphic numbers in base $10$ are given by $\{0,1\}\cup\{5^{2^m}\pmod {10^m}:m\ge 1\}\cup\{16^{5^m}\pmod {10^m}:m\ge 1\}$.

Proof: Suppose $x$ is an automorphic number of $n$ digits. Then,

$x(x-1)\equiv 0\pmod {10^n}$

which is equivalent to

$\Big(x\equiv 0\text{ or }1\pmod{2^n}\Big) \text{ and } \Big(x\equiv 0\text{ or }1\pmod{5^n}\Big)$

which is equivalent to the occurrence of exactly one of the following:

Case 1: $x\equiv 0\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}$

Case 2: $x\equiv 1\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}$

Case 3: $x\equiv 1\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}$

Case 4: $x\equiv 0\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}$

Now we consider all these cases one by one. Case 1 is equivalent to $x\equiv 0\pmod {10^n}$. Since $x$ had $n$ digits so this means $x=0$. Similarly $x=1$ in case 2.

Now suppose case 3 holds. By the Chinese Remainder theorem there exists a unique solution to these two congruences modulo $10^n$. We show that $5^{2^n}$ is a solution to them. By uniqueness it will then follow that case 3 is equivalent to saying that $x\equiv 5^{2^n}\pmod {10^n}$. Since $x$ has $n$ digits and $5^{2^n}\pmod {10^n}$ has at most $n$ digits so we will therefore have $x$ equal to $5^{2^n}\pmod {10^n}$. Hence $x\in\{5^{2^m}\pmod {10^m}:m\ge 1\}$.

We first show that $5^{2^n}\equiv 1\pmod {2^n}$. Proceed by induction on $n$. For $n=1$ note that $5^{2}\equiv 1\pmod 2$.

Now assume the result for $k$. Then $5^{2^k}=q2^k+1$ and squaring yields $5^{2^{k+1}}=q^2 2^{2k}+q2^{k+1}+1=(q^2 2^{k-1}+q)2^{k+1}+1$ and so $5^{2^{k+1}}\equiv 1\pmod {2^{k+1}}$ thereby completing the induction step. Next observe that as $n<2^n$ so $5^{2^n}\equiv 0\pmod {5^n}$ follows immediately, thereby completing case 3.

Note that our argument also implies that any number of the form $5^{2^m}\pmod{10^m}$ is automorphic. Indeed, if $a=5^{2^m}\pmod{10^m}$ had $t\le m$ digits then we have shown that $a^2\equiv a\pmod {10^m}$. Now as $10^t$ divides $10^m$ so $a^2\equiv a\pmod {10^t}$, i.e. $a$ is automorphic.

To finish the proof we now consider case 4. We show that $16^{5^n}$ is a solution to the congruences of case 4. Clearly $16^{5^n}\equiv 0\pmod {2^n}$ as $n<4.5^n$. To show $16^{5^n}\equiv 1\pmod {5^n}$ we proceed by induction as before. The base case may be explicitly worked out or be shown to hold by invoking Fermat’s theorem: $m^p\equiv m\pmod p$, for any prime $p$ and integer $m$. Next assume the result for $k$, so that $16^{5^k}=q5^k+1$. Raising both sides to the fifth power yields the result for $k+1$. The rest of the argument is similar.$\Box$

Filed under Miscellaneous, Number theory, Recreational Mathematics

## The infinitude of the primes

As we all know, a (natural) number $p>1$ is called prime if its positive divisors are only $1$ and $p$. The fact that prime numbers are infinite in number was proved by Euclid (although it is not clear whether he discovered it) and the proof is a little gem of mathematical reasoning. We present his proof below:

Theorem: There are infinitely many prime numbers.

Proof: Consider any list of prime numbers, say $p_1,p_2\cdots p_n$. The number $P=p_1p_2\cdots p_n+1$ is clearly not on the list. If $P$ is not prime, then by definition there is a prime number $p$ which divides $P$. Clearly $p\ne p_i$ for any $i$ as otherwise $p$ divides $1$, a contradiction.  So $p$ is a prime number not on the list. If, on the other hand, $P$ is prime, then it is anyway a prime number not on the list. Hence our list is incomplete.$\Box$

We now give another beautiful proof for the same theorem owing to Euler. Although it does not strictly qualify as a valid mathematical proof by modern standards and is really nothing more then heuristic reasoning yet its “wow factor” is so high that as an exception it is still referred to as a proof. It can be recast into a more rigorous form but we do not so here so that its original taste is not disturbed. The essential argument here is that if the primes were finite then the product $\prod_{\text{p prime}}\frac{1}{1-1/p}$ would be finite which is not the case.

Theorem: There are infinitely many prime numbers.

Proof: Let $P$ denote the set of all primes. Now consider the product $\prod_{p\in P}\frac{1}{1-1/p}$ i.e.

$(\frac{1}{1-1/2})(\frac{1}{1-1/3})(\frac{1}{1-1/5})\cdots\\\\=(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}\cdots)(1+\frac{1}{3}+\frac{1}{9}+\frac{1}{27}\cdots)(1+\frac{1}{5}+\frac{1}{25}+\frac{1}{125}\cdots)\cdots$

by the formula of the geometric series.

Next we observe that if we multiply out the terms (assuming such a multiplication is valid) then the reciprocal of every positive integer will occur exactly once by the uniqueness of the fundamental theorem of arithmetic. If $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ is the unique factorization of $n$ then $\frac{1}{n}$ would result in the multiplication only when $\frac{1}{p_1^{\alpha_1}},\cdots \frac{1}{p_k^{\alpha_k}}$ are multiplied. Hence the above product

$\prod_{p\in P}\frac{1}{1-1/p}=\sum_{n=1}^\infty \frac{1}{n}$. The latter harmonic series is well known to be divergent. Hence there must be infinitely many terms in $P$.$\Box$