As mentioned earlier, the simplest algorithm for finding the square root of a leftin is to try all digits from right to left, eliminating the ones that don't work. However, you don't always get the expected two square roots per number.
First we will search for the square roots of 1 among L2 . If there were any digits to the right of the decimal point, the right-most digit of its square would need to be 0. The only digit that fits is 0. So all digits to the right of the decimal point must be 0. This is a general principle for any number base.
SQ1: aL0, if bLf such that b2 = a, bL0 .
So we will look for the square roots of 1 in L0 . In order that b2 be 1, its right-most digit must produce a right-most digit of 1 when squared. The only possibility is 1.
Next we look for any two digit numbers ending with 1, which, when squared gives us the two right-most digits 01. There are two possibilities.
...012 = ...112 = ...01
The third digit gives us 4 possibilities, but two of these get weeded out when we look at the fourth digit. After trying more digits, we see that we end up with two square roots of 1 base 2, ...(0)1 and ...(1). These are simply 1 and -1.
We'll try finding 1 base 10 as the next example. If b2 = 1, the right-most digit of b (since it is in L0 according to SQ1) must be 1 or 9. The next digit gives us four possibilities:
...012 = ...512 = ...492 = ...992 = ...01.
The third digit gives us the 8 possibilities ...001, ...501, ...251, ...751, ...249, ...749, ...499 and ...999. When we try the fourth digit, we see that half of those won't work (e.g. ...x5012...0001 for any digit x.) At each step from now on, the left-most digit will be ambiguous until we try the next digit to the left. We will find that four different values emerge for 1.
(0)1 and (9) we recognize as 1 and -1, which we would expect, but what about the "extra" square roots? We will call ...751 q and come back to it later. Note that the other square root ...249 = -q.
A proof that there really are four square roots of 1 base 10 can start from the four numbers given above. It's simple to have a computer verify that these are the only possibilities for the given number of digits.
Question: How do you show that each of these square roots of 1 has only a single possibility for each digit you add? Note that you need to look at two digits to successfully narrow down each digit.
At this point it's useful to look at a table of square roots to get a feel for which numbers have square roots in various bases as well as how many square roots different bases produce.
Next, a few theorems to set the stage for an important conjecture.
SQ2: If mLf and m2 = n, then (-m)2 = n.
(-m)2 = (0-m)2 = 02 - 2*0*m + m2 = m2 = n.
Divisor of 0 Theorem 1: aLf , if mLf such that am=0, then nL0 such that an=0.
We'll break it into two cases:
Divisor of 0 Theorem 2: aLf , if mL0 , m0 such that am=0, then nL0 such that an=0 and the right-most digit of n, d0, is not 0.
Negative Uniqueness: mLf m0, m-m.
If m = -m, then 2m=0. From the above theorems we can see that if m 0 then n L0 such that 2n=0 and the right-most digit of n, d0, is not 0.
From these results, we can see that, except for 0, square roots come in pairs, with one being the additive inverse of the other.
Number of Square Roots Conjecture: The number of square roots of 1 present in Lk is 2 raised to the power of the number of unique prime factors in k.
Thus any prime number base would have two square roots of 1. Any number base that's a power of a prime would also produce two square roots. Since 10=2*5, it has four square roots of 1. 30=2*3*5, so it has 8 square roots. 20=2*2*5, which is only two unique prime factors, so it has four square roots of 1.
The perfect squares (1, 4, 9, etc.) have the expected positive and negative integer square roots. Additionally, we can see that q times either of these square roots would also be a square root. For example, 2 and -2 are square roots of 4, thus 2q and -2q are also square roots. Clearly it's simple to find four square roots of the perfect squares.
From this, we might expect that any leftin with a square root has four square roots, but this is not true. Consider (q+1)2 which has the obvious square roots (q+1) and -(q+1). If we try multiplying (q+1) by q, we find we don't generate another square root.
q(q+1) = q2 + q = 1 + q
(q+1)2 has only two square roots.
Question: Do any leftins have more square roots than 1 does in a given base?
The two square roots of 17 base 2 are
How do you decide which of these is positive and which is negative? With LZ it's quite obvious: positive integers start with (0) and negative integers start with (k-1). Ordering an irrational (or even an arbitrary rational) is not obvious.
© Scott Sherman 1999