repunit prime factors

Question

So I am working on this problem... which states:

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form R(10^n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10^n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10^n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10^n).

My general strategy was to find the prime factorization of the highest repunit below 100,000^2 which I assumed if a factor was less than 100,000 it would become a factor of a repunit by 100,000 squared... which apparently isn't true, as that list is: (3, 7, 11, 13, 37, 41, 73, 101, 137, 239, 271, 4649, 9091)

and going as far as I can in 64 bit ints the list is: (3, 7, 11, 13, 17, 19, 31, 37, 41, 53, 73, 79, 101, 137, 239, 271, 4649, 9091, 9901, 21649, 52579)

So most interesting is the numbers are 17 and 19... which leads me to believe that I need to find a very different way around this problem... but I am not sure where to go next.

PS I haven't unit tested my algorithms to verify that the lists are complete and correct... but they look right when checking against the factorizations listed on wikipedia.

Answer 1

Not sure that your statement is right. Did you mean $R(10^n)$ and not R(10n) Note that $$R(k)= \frac{10^k-1}{9}$$

So for $p \neq 3$, $p | R(k)$ if and only if $$10^k \equiv 1 \mod p$$

This says that for $p$ to divide $R(k)$, $p-1$ and $k$ must have some non-trivial common factor and $10$ to the power of this factor should be $1 \mod p$.

For example, if you set $p=19$ then $10 n$ and $18$ must have a nontrivial factor. Thus repunit with 180 ones is $$9 \, R(180) = 10^{180}-1 = \left(10^{18}\right)^{10} - 1 \equiv 1^{10} -1 = 0 \mod 19$$

In fact every $p$ divides $R(10n)$ where $n = p-1$.

If what you meant was $R(10^n)$ then the above logic says that $p-1$ must have a common factor with $10^n$, i.e. $p-1$ must be divisible by $2$ or $5$ or both. Now argue that if $p-1$ is a power of 2, or power of 2 times a power of 5 then we can always find a $n$. If in addition $p-1$ is a multiple of a power of $3$ then use the fact that $10\equiv 1 \mod 3$ to argue the case.

Answer 2

Here is a new proof using repunits that there are infinitely many primes by me with an interesting new result on its divisors

Let p be a prime. > 7 and R(p) be the repunit = (10^p - 1)/9. If q is a prime divisor of R(p) . Then q is congruent to 1 mod p. Or q is of the form kp + 1 for some k. This can be established by the fact that q divides R(q-1) by Fermat's little theorem and further applying Euclidean algorithm.

If q divides 111111 ... p times

also q divides 11111 ( q-1) times

then a divides 11111 ... r times

where r = GCD ( p, q-1) =1 or p

q divies 1 is absurd

hence GCD ( p, q-1) = p

p divides ( q-1)

q = kp +1

In other words all the divisors of R(p) including R(p) are of this type where p is a prime

All the divisors of R(p) are congruent to 1 mod p.

R(p) = (2ap+1) (2bp+1) (2cp+1) ....

All the divisors of R(p) are > p

This also proves a result that for every prime p there exists at least one prime of the type kp+1.

This completes the proof.