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.

Consider small solutions (P<300) for prime P:

P Solutions P mod8
Regular (10k+3,10k+7)
7 n=2(3m+2)) 7
17 n=2(8m+3)) 1
23 n=2(11m+7) 7
47 n=2(23m+8) 7
97 n=2(48m+5) 1
113 n=4(28 m+15) 1
167 n=2 (83m+40) 7
223 n=2(96m+5) 7
233 n=6(37m+34) 1
257 n=8(29m+4) 1
263 n=16(16 m+11) 7
Irregular
127 n=2(131m+53) 7

Regular (10k+1,10k+9)   
P     Solutions  P mod8 
19 (18m+1) 3 
29 n=28m+17 5 
59 n=58m+33 3 
61 n=60m+13 5 
109 n= 3(36m+5)   5 
131 n = 130m+47  3 
149 n=148m+31 5 
179 n=178m+105 3 
181 n=180m+47 5 
229 n=3(76m+67)  5 
269 n=268m+159 5 
Irregular - 40k+31    
31   n=3(5m+3) 7
71   n=35m+6 7
151   n= 5(15m+8) 7
191   n=95m+44 7
Irregular - Other    
89   n=4(11m+2)  1
251   n= 50m+11 3

It is a sufficient (though not necessary) condition for a prime, P, to divide 2*10^n-1, that it have 10 as a primitive root (e.g. {17,19, 23, 29, 47, 59, 61,71,97...}).  Contrariwise, it is a necessary (though not sufficient) condition for a prime, P, NOT to divide 2*10^n-1, that it NOT have 10 as a primitive root (e.g. {11,13, 37, 41, 43, 53, 67, 73,79, 83,...}). We call such cases 'regular'.

We need the classic result (Legendre?):
(2/P)=(-1)^((P^2-1)/8) = 1, if P={1,7} mod8
(2/P)=(-1)^((P^2-1)/8) = -1, if P={3,5} mod8

Hence, if 2 is a primitive root modP, then P mod8 = {3,5}.

Note that we say nothing about the irregular results P(10k+1,10k+9) (interesting though those are).

Let P be an odd prime. If 2 is a primitive root modulo P, then P mod8 = {3,5}. But the results for P(3,7) above give P always of the form {1,7} mod 8. So 2 is never a primitive root of those numbers.

The required result follows at once, and surprisingly easily; divide the primes into three categories; (3,7) primes (which are all regular for this purpose), regular primes  of the (1,9) category, and other (1,9) primes. If there is an odd number of 9's then every single prime factor will be of the (1,9) category. If there is an even number of 9's then either every single prime factor will be of the (3,7) category, or every (1,9) prime that is a factor will be 'irregular'.

NOTE 1: This rearrangement is helpful: 
(2*10^n-1)  mod P = 0
(2*10^n-1)-1 = 2*(10^n-1)
2*(10^n-1) modP = P-1
(10^n-1) modP = (P-1)/2
 

NOTE 2: Even if 2 is a primitive root of P, there's no guarantee that P will divide 2*10^n-1, just that if it does, it will end in 1 or 9.

NOTE 3: 'Irregular' above means that 10 is not a primitive root of P. (If 10 is a primitive root of P, then P is guaranteed to divide 2*10^n-1, for some n<P; the contrary does not follow, hence 'irregular'.) 

NOTE 4: I haven't attempted the second part of the puzzle.

 

 

Edited on December 16, 2012, 8:29 am

Edited on December 16, 2012, 8:30 am

Posted by broll on 2012-12-16 05:39:50