The 1-digit self-replicating numbers are 0, 1, 5, and 6, because , , , and . These numbers all satisfy the congruence .
For 2-digit self-replicating numbers, n is self-replicating if . But if 100 divides , then so do 4 and 25, and we get the simultaneous congruences
It follows from the first of these congruences that or 1 (mod 4).
For the second congruence, we notice that 25 divides , and so either 5 divides both n and (which cannot happen) or 25 must divide n or . It follows that or 1 (mod 25). So we have four pairs of simultaneous linear congruences:
and , with solution which isn’t a 2-digit number;
and : this has the solution , which we saw earlier;
and : this has the solution , with ;
and , with solution which isn’t a 2-digit number.
So the only two 2-digit self-replicating numbers are and .
Likewise, for 3-digit self-replicating numbers, we have the congruence , from which we get the simultaneous congruences
These in turn lead to the simultaneous linear congruences or 1 (mod 8) and or 1 (mod 125), and on examining these in pairs, as above, we find that the only 3-digit self-replicating numbers are and 625, with and .Squares and non-squares
We conclude this chapter by looking at some more quadratic congruences. Our explorations will lead us to one of the most important results in number theory, the law of quadratic reciprocity.
We’ll start with the congruence
We can solve this by multiplying by 4 and adding 9 to both sides, giving
Taking the square root now gives or , and these two linear congruences can then be solved to give and . These solutions are correct, because
It turns out that many quadratic congruences can likewise be rewritten in the form —here, , , and —and this leads us to investigate which numbers b are squares (mod n) and which ones are non-squares. We’ll now explore this question when n is an odd prime number.
Let’s first find the squares (mod p) when . Because is always a square, whatever the value of p, we’ll seek only non-zero squares.
When , the non-zero squares are and ,
so the only non-zero square (mod 3) is 1, and the only non-square is 2.
When , the non-zero squares are
so the non-zero squares (mod 5) are 1 and 4, and the non-squares are 2 and 3.
When , the non-zero squares are:
so the non-zero squares (mod 7) are 1, 2, and 4, and the non-squares are 3, 5, and 6.
When , the non-zero squares are:
so the non-zero squares (mod 11) are 1, 3, 4, 5, and 9, and the non-squares are 2, 6, 7, 8, and 10.
We notice that in each case the numbers of squares and non-squares are the same, and this is the case for all primes. The squares are often called quadratic residues (mod p) and the non-squares are called quadratic non-residues (mod p).
If we multiply two squares (mod p) together, then the product is also a square: this is because
We can likewise prove that
the product of any two non-squares (mod p) is a square,
and
the product of a square and a non-square (mod p) is a non-square.
For example, when ,
6 and 7 are both non-squares, and their product is a square;
5 is a square and 7 is a non-square, and their product is a non-square.
Given an odd prime number p, how can we decide whether a given number a is a square or a non-square (mod p)? For example, knowing that 2027 is a prime, is 1066 a square or a non-square (mod 2027)? We’ll answer this question later.
In 1798 Adrien-Marie Legendre introduced a useful notation that helps us when answering such questions. If p is an odd prime number and a is a number that’s not divisible by p, then his Legendre symbol (a / p) is defined by
for example, and , because 5 is a square and 6 and 7 are non-squares (mod 11). We note that, for any odd prime number p, and any number a that is not divisible by p,
for example, .
There are some useful rules that help us to find Legendre symbols. The first is:
If a and b are not divisible by p, and if , then .
For example, 42 is a square (mod 11), because , and so
The second rule restates the above remarks about multiplying squares and non-squares:
If a and b are not divisible by p, then .
For example, 42 is a square (mod 11), because
It can also be shown that, for any odd prime p,
These results conveniently tell us when −1 and 2 are squares (mod p). For example,
and , because and ;
and , because and .
Suppose next that we wish to decide whether 41 is a square (mod 23).
By the first rule we can write
So
