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

Leave a comment

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

Leave a comment

Filed under Algebra, Number theory