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.)

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 (10^{2n} − 5)/5.

Consider an odd prime p 5 that divides 10^{2n} − 5 = (10^{n})^{2} − 5.

Then (10^{n})^{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.

We will again use the properties of quadratic residues.

Note that 10...09...9 = x^{2} + x − 1, where x = 10^{n}, and where n is the number of zeroes or nines.

If an odd prime p 5 divides x^{2} + x − 1 then p divides 4x^{2} + 4x − 4.

Hence 4x^{2} + 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.

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 x^{2} − 5, end in 1 or 9. Further, all the divisors of any number that ends in 1 or 9, and is of the form x^{2} − 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 (10^{2n} − 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.

Noting that the `n`th triangular number, T_{n}, is equal to ½n(n + 1), we see that the above result may be expressed by saying that the prime divisors of 2T_{n} − 1 = n^{2} + 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 mT_{n} + u, for various m and u.

For instance, if an odd prime p divides 4T_{n} + 1 = 2n^{2} + 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 4T_{n} + 1 are of the form 4k + 1.

Next, if an odd prime p divides 6T_{n} + 1 = 3n^{2} + 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 6T_{n} + 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 3n^{2} + 3n + 1 is the difference between consecutive cubes.

Finally, if an odd prime p divides 10T_{n} + 1 = 5n^{2} + 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 10T_{n} + 1 are of the form 10k ± 1; that is, they end in 1 or 9.

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

8r^{2}n^{2} + 8r^{2}n + 2(r^{2} + s) = tmn^{2} + tmn + 2t,

where t is the multiplier of mT_{n} + 1.

Regarding this equation as a quadratic in n, and equating coefficients, we find that ms = (8 − m)r^{2} and t = r^{2} + 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 = 2r^{2}, or 3s = r^{2}, for which we choose s = 3, r = 3, and then m = 12. That is, 3^{2}(2n + 1)^{2} + 3 = 12(3n^{2} + 3n + 1). Hence, if an odd prime p divides 6T_{n} + 1 = 3n^{2} + 3n + 1, then p divides 3^{2}(2n + 1)^{2} + 3, so that −3 is a quadratic residue of p, as noted above.

Similarly, if we take m = 1, then s = 7r^{2}, 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 T_{n} + 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 10T_{n} + 1. (The *other* prime factors, modulo 28, are of the form 28k + 3, 5, 13, 17, 19, or 27.)

Source: Original