# Solution to puzzle 149: Ones and nines

Show that all the divisors of any number of the form 19...9 (with an odd number of nines) end in 1 or 9.  For example, the numbers 19, 1999, 199999, and 19999999 are prime (so clearly the property holds), and the (positive) divisors of 1999999999 are 1, 31, 64516129 and 1999999999 itself.

Show further that this property continues to hold if we insert an equal number of zeroes before the nines.  For example, the numbers 109, 1000999, 10000099999, 100000009999999, and 1000000000999999999 are prime, and the (positive) divisors of 10000000000099999999999 are 1, 19, 62655709, 1190458471, 8400125030569, 159602375580811, 526315789478947368421, and 10000000000099999999999 itself.

(Dario Alpern's Java applet Factorization using the Elliptic Curve Method may be useful in obtaining divisors of large numbers.)

## 19...9

It will suffice to show that all the positive prime divisors of a number of the form 19...9 or 10...09...9, end in 1 or 9.  The result will then follow because any divisor is a product of the prime divisors, and any product of numbers ending in 1 or 9 itself ends in 1 or 9.  Thus we seek to show that each prime factor is congruent to ±1, modulo 10.  This constraint on the prime factors suggests that we should try to use the properties of quadratic residues.

Note that a number of the form 19...9 (with an odd number of nines) may be written as (102n − 5)/5.
Consider an odd prime p 5 that divides 102n − 5 = (10n)2 − 5.
Then (10n)2 5 (mod p), so that 5 is a quadratic residue of p.
We now show that this implies p ±1 (mod 10).

The easiest way to do this is by using the Quadratic Reciprocity Theorem.
Since 5 1 (mod 4), 5 is a quadratic residue of p p is a quadratic residue of 5.
Quadratic residues of 5 are congruent to ±1 modulo 5, but, since p is an odd prime, this is equivalent to p ±1 (mod 10).

We have shown that the prime factors of a number of the form 19...9 (with an odd number of nines) are equal to 2 or 5, or are congruent to ±1 modulo 10.
However, a number of this form does not have 2 or 5 as a factor, and hence all of its prime factors are congruent to ±1 modulo 10; that is, they end in 1 or 9.
Therefore, as noted above, all the divisors of any number of the form 19...9 (with an odd number of nines) end in 1 or 9.

## 10...09...9

We will again use the properties of quadratic residues.

Note that 10...09...9 = x2 + x − 1, where x = 10n, and where n is the number of zeroes or nines.
If an odd prime p 5 divides x2 + x − 1 then p divides 4x2 + 4x − 4.
Hence 4x2 + 4x + 1 = (2x + 1)2 5 (mod p), so that 5 is a quadratic residue of p.

Therefore, as above, p ±1 (mod 10).
Also as above, a number of this form does not have 2 or 5 as a factor, and hence all of its prime factors are congruent to ±1 modulo 10; that is, they end in 1 or 9.
Therefore, all the divisors of any number of the form 10...09...9 end in 1 or 9.

## Remarks

It is clear from the above argument that the same property holds for numbers of the form 10...09...9 with any number of zeroes and the same number of nines, not just with an odd number.  For example, the divisors of 100009999 are 1, 31, 3226129, and 100009999 itself.  Indeed, all the prime divisors (other than 2 or 5) of any number of the form x2 − 5, end in 1 or 9.  Further, all the divisors of any number that ends in 1 or 9, and is of the form x2 − 5, end in 1 or 9.

It can also be shown that all the divisors of any number of the form 49...9 (with an even number of nines) end in 1 or 9.  (Consider (102n − 20)/20, for n > 1.)  Many other numbers, such as those of the form 79...9 (with an odd number of nines) can be shown to have the same property.

### Triangular numbers

Noting that the nth triangular number, Tn, is equal to ½n(n + 1), we see that the above result may be expressed by saying that the prime divisors of 2Tn − 1 = n2 + n − 1 are equal to 5, or are congruent to ±1 modulo 10.  We can similarly explore the possible prime factors of numbers of the form mTn + u, for various m and u.

For instance, if an odd prime p divides 4Tn + 1 = 2n2 + 2n + 1, then p divides (2n + 1)2 + 1; that is, −1 is a quadratic residue of p.  Hence p 1 (mod 4), and so all the (positive) divisors of 4Tn + 1 are of the form 4k + 1.

Next, if an odd prime p divides 6Tn + 1 = 3n2 + 3n + 1, then p divides 9(2n + 1)2 + 3; that is, −3 is a quadratic residue of p.  Hence p 1 (mod 6), and so all the (positive) divisors of 6Tn + 1 are of the form 6k + 1.  (See the list of primes which have a given number d as a quadratic residue towards the bottom of the page Quadratic Residue.)  Note that 3n2 + 3n + 1 is the difference between consecutive cubes.

Finally, if an odd prime p divides 10Tn + 1 = 5n2 + 5n + 1, then p divides 25(2n + 1)2 − 5; that is, 5 is a quadratic residue of p.  Hence p ±1 (mod 10), and so all the divisors of 10Tn + 1 are of the form 10k ± 1; that is, they end in 1 or 9.

More generally, to determine which odd primes divide mTn + 1, we seek r and s such that r2(2n + 1)2 + s is a multiple of mTn + 1 = ½mn(n + 1) + 1.  Multiplying by 2 and expanding both sides, we obtain:

8r2n2 + 8r2n + 2(r2 + s) = tmn2 + tmn + 2t,

where t is the multiplier of mTn + 1.
Regarding this equation as a quadratic in n, and equating coefficients, we find that ms = (8 − m)r2 and t = r2 + s.

For a given m, we are interested in the least absolute value of s for which the first of the above equations holds.  For example, if m = 6, we have 6s = 2r2, or 3s = r2, for which we choose s = 3, r = 3, and then m = 12.  That is, 32(2n + 1)2 + 3 = 12(3n2 + 3n + 1).  Hence, if an odd prime p divides 6Tn + 1 = 3n2 + 3n + 1, then p divides 32(2n + 1)2 + 3, so that −3 is a quadratic residue of p, as noted above.

Similarly, if we take m = 1, then s = 7r2, so we choose s = 7, r = 1.  Hence −7 is a quadratic residue of p, in which case it can be shown that p 1, 9, 11, 15, 23, or 25 (mod 28).  So, any prime factor of Tn + 1 is equal to 2 or 7, or is of the form 28k + 1, 9, 11, 15, 23, or 25; a result which is not as striking as, say, that for 10Tn + 1.  (The other prime factors, modulo 28, are of the form 28k + 3, 5, 13, 17, 19, or 27.)

Source: Original