Factorisation of repunits and determination whether a number is prime. Are these two questions linked?

495 Views Asked by At

Let $R(n)$ denote a repunit in decimal number system of $n$ digits. With the exception of $2,3$ and $5$ (which have easy divisibility tests), its factors can only be of two types:

  1. Positive integers of the form $nm+1$ where $m$ is a natural number.
  2. The divisors of $R(k)$, where $k$ is a factor of $n$.

(So for the first type of factors, the smallest factor of $R$(n) can be $n+1$ and the largest, the number itself.)

Firstly i wanted to ask is this a well established and documented result?

Secondly has this way of factoring a repunit been used in factoring a number or more importatnly in forming a primality testing algorithm?

1

There are 1 best solutions below

3
On

I have deleted my earlier answer, because it referred to a different formulation of the question, and also because in the ensuing discussion I think I may have understood what OP has in mind.

As stated now, the question appears to claim that the factors of a repunit $$ R(n) = \frac{10^n - 1}{ 10 -1} $$ are of one of the following form

  • congruent to $1$ modulo $n$,
  • repunits $R(k)$, with $k \mid n$,
  • $3$.

This is of course not true, as $101$ divides $R(8)$, but does not fit in any category.

What is true is that if $p \ne 3$ is a prime divisor of $R(n)$, but not of any $R(k)$, with $k < n$, then $n$ is the period of $10$ modulo $p$, and thus $n$ divides $\varphi(p) = p - 1$, so that $p$ is congruent to $1$ modulo $n$.