Novel Prime Factors of Repunits

Proof that every repunit has a novel prime factor

Using Zsigmondy's Theorem, the proof is simple. From Wikipedia:

In number theory, Zsigmondy's theorem, named after Karl Zsigmondy, states that if a > b > 0 are coprime integers, then for any integer n ≥ 1, there is a prime number p (called a primitive prime divisor) that divides aⁿ − bⁿ and does not divide a^k − b^k for any positive integer k < n, with the following exceptions: [things that don't apply here].

Consider the repunits times 9: that is, 10ⁿ-1. By Zsigmondy's Theorem with a=10, b=1, there is some prime p | 10ⁿ-1 that does not divide any 10^k-1, k < n.

• Since p is prime and 10ⁿ-1 = 9 · R_n, it must divide either 9 or R_n.

• p cannot divide 9, since 9 = 10¹-1.

• Therefore p divides R_n.

• p cannot divide any R_k, since it doesn't divide 10^k-1 = 9 · R_k.

Therefore the p from Zsigmondy's Theorem is a novel prime factor of any R_n, n ≥ 2. ∎

---

An example of a repeated novel prime factor

The prime 487 is a repeated prime factor of R₄₈₆:

By the Fermat-Euler theorem, 10^487-1 ≡ 1 (mod 487). The order of 10 mod 487, that is, the smallest power of 10 that is 1 mod 487, therefore must be a divisor of 486. In fact, the order is equal to 486. It also happens that not only is 10⁴⁸⁶ ≡ 1 (mod 487), it's also 1 (mod 487²).

See here that the order of 10 mod 487 is 486; that is, that no smaller 10^k-1 is divisible by 487. Obviously, 487 doesn't divide 9, so it must divide R₄₈₆.

CJam, 18 bytes

{{)'1*imf}%W%:-_&}

Test it here.

Starting at 19 (the first repunit prime after 2) it will take a fairly long time.

Explanation

This is an unnamed block (CJam's equivalent of a function), which expects the input number n on the stack and leaves a list of prime factors instead:

{      e# Map this block over [0 1 ... n-1]...
  )'1* e#   Increment and create a string of that many 1s.
  i    e#   Convert to integer.
  mf   e#   Get its prime factors.
}%
W%     e# Reverse the list.
:-     e# Fold set difference onto the list, removing from the first list the elements of
       e# all other lists.
_&     e# Remove duplicates. Unfortunately, this necessary. Thomas Kwa found that the 486th
       e# repunit contains 487^2 (where 487 is a novel prime factor).

Pyth, 16 14 13 bytes

-F_m{P/^Td9SQ

As best I can tell, 19 takes forever.

-F_m{P/^Td9SQ      Implicit: Q = input
           SQ      Inclusive range 1 to Q
                        Implicit lambda d:
    {P                  unique primes dividing
       ^Td              10**d
      /   9                  //9
   m               map lambda over the range
   m{P/^Td9SQ      Unique prime factors of all repunits up to the Qth
  _                Reverse the list
-F                 Reduce by set difference

Try it here.