9
$\begingroup$

Repunits are numbers whose digits are all $1$. In general, finding the full prime factorization of a repunit is nontrivial.

Sequence A067063 in the OEIS gives the smallest prime factor of repunits. There are no $7$'s (just the number $7$, not as a digit in a different prime) that I can see in the sequence.


$7$ does divide many repunits, but always does when $3$ is also a factor, so $7$ never shows up as the smallest prime factor. The table of the first $508$ smallest prime factors of repunits shows that $7$ is not the smallest prime factor of any of those repunits.

My question is can $7$ ever be the smallest prime factor of a repunit?

I tried to find a repunit with $7$ as the smallest factor but searched very far and $3$ is always a factor whenever $7$ is.

I tried to prove that it can't be but I have no idea how.

$\endgroup$
4
  • 5
    $\begingroup$ Hint: think about $R(6) = 111111$. Also the fact that $$1001=7\cdot 11 \cdot 13$$ will help. $\endgroup$ Nov 28 '19 at 2:23
  • 1
    $\begingroup$ yes $7$ is a factor of $111111$ but so is $3$ ... so it is not the smallest prime factor $\endgroup$ Nov 28 '19 at 2:25
  • 4
    $\begingroup$ I don't think Zubin Mukerjee was trying to give a counter example. I think that was a hint as to why $7$ can never appear without $3$. If $3\not\mid 1111....$ but $7\mid 111....$ then $1111.....111\pmod {1001}$ is divisible by $7$ but $3$ isn't. Is that possible. $\endgroup$
    – fleablood
    Nov 28 '19 at 2:48
  • 6
    $\begingroup$ Yes, $R(6)$ is what I used to show that $7$ cannot be the smallest prime factor, ever. The idea is that if $R(n)$ is divisible by $7$, then $n$ is divisible by $6$, which means $n$ is divisible by $3$, which means $R(n)$ is divisible by $3$, so $7$ isn't the smallest prime factor. See my answer for the full argument @VincentLuo $\endgroup$ Nov 28 '19 at 2:50
11
$\begingroup$

Can $7$ be the smallest prime factor of a repunit?

No, it cannot.

The main idea is as follows: If the $n^\text{th}$ repunit $R(n)$ is divisible by $7$, then $n$ is divisible by $6$, which means $n$ is divisible by $3$, which means $R(n)$ is divisible by $3$, so $7$ cannot be the smallest prime factor.

The full argument is fleshed out below.


Let $R(n)$ be the $n^\text{th}$ repunit, e.g. $R(4) = 1111$.

One interesting property about repunits is that if an integer $m$ divides $R(n)$, then $m$ divides $R(2n)$, and $m$ divides $R(3n)$, and so on. This is because, for any positive integer $n$, we have the factorization $$R(2n) = \left(10^{n}+1\right)R(n)$$ and, more generally, for any positive integers $k$ and $n$, we can factor as follows:

$$R(kn) = \left(\displaystyle\sum\limits_{j=0}^{k-1} 10^{jn}\right)R(n)$$


What this means, for your problem, is if a prime $p$ divides a repunit $R(n)$, then it will also divide $R(kn)$ for all $k$.

This tells us that:

  • Every other repunit is divisible by $11$. $$11 \,|\, R(2) \implies\,\Big(\,\,\,n \equiv 0 \pmod{2} \iff 11 \,|\, R(n) \,\,\,\Big)$$ Here, the "$\iff$" bidirectionality follows from the fact that $11 \not| \,\,R(1)$.

  • Every third repunit is divisible by $3$. $$3 \,|\, R(3) \implies \,\Big(\,\,\,n \equiv 0 \pmod{3} \iff 3 \, |\, R(n) \,\,\,\Big)$$ Here, the "$\iff$" bidirectionality follows from the fact that $3 \not| \,\,R(1)$ and $3 \not| \,\,R(2)$.

  • Every third repunit is divisible by $37$. $$37 \,|\, R(3) \implies \,\Big(\,\,\,n \equiv 0 \pmod{3} \iff 37 \, |\, R(n) \,\,\,\Big)$$ Here, the "$\iff$" bidirectionality follows from the fact that $37 \not| \,\,R(1)$ and $37 \not| \,\,R(2)$.

  • Every sixth repunit is divisible by $13$.$$13 \,|\, R(6) \implies \,\Big(\,\,\,n \equiv 0 \pmod{6} \iff 13 \, |\, R(n) \,\,\,\Big)$$ Here, the fact that each of $1, 11, 111, 1111, 11111$ are not divisible by $13$ implies the "$\iff$" bidirectionality.

  • Every sixth repunit is divisible by $7$.$$7 \,|\, R(6) \implies \,\Big(\,\,\,n \equiv 0 \pmod{6} \iff 7 \, |\, R(n) \,\,\,\Big)$$ Here, the fact that each of $1, 11, 111, 1111, 11111$ are not divisible by $7$ implies the "$\iff$" bidirectionality.


This last fact implies that $7$ can never be the smallest prime factor of a repunit, because whenever $n \equiv 0 \pmod{6}$, it's also true that $n \equiv 0 \pmod{3}$, so whenever $7$ is a factor of a repunit, $3$ will be as well.

By a similar argument, $13$ and $37$ also cannot be the smallest prime factor of a repunit.

$\endgroup$
1
  • 5
    $\begingroup$ Beautiful. +1.. $\endgroup$
    – Shailesh
    Nov 28 '19 at 2:51
4
$\begingroup$

The repunits as a recurrence obey $$ r_{n+1} = 10 r_n + 1 $$ see https://en.wikipedia.org/wiki/Pisano_period

The code making the table of Pisano periods below. The simple outcome: the possible values of $r_n \pmod{21}$ are $$ 0, 1, 2, 6, 11, 19 . $$ In particular, the remainder after dividing by 21 can be $6,$ but is never $7$ or $14 \pmod {21}.$ Thus, $r_n$ can be divisible by $3$ alone, without any $7.$ Once $r_n$ is divisible by $7,$ the only possibility is $0 \pmod {21},$ meaning also divisible by $3$

   mpz_class rep = 0;
      for(int n = 1; n <= 45; ++n){
         rep = rep * 10 + 1;
      cout << "  n: " << n  << "  rep: " << rep << " mod 21: " << rep % 21 << endl;
       }

with no extra symbols. This is also a complete proof:

jagy@phobeusjunior:~$ ./mse

Wed Nov 27 18:45:37 PST 2019

  n: 1  rep: 1 mod 21: 1
  n: 2  rep: 11 mod 21: 11
  n: 3  rep: 111 mod 21: 6
  n: 4  rep: 1111 mod 21: 19
  n: 5  rep: 11111 mod 21: 2
  n: 6  rep: 111111 mod 21: 0
  n: 7  rep: 1111111 mod 21: 1
  n: 8  rep: 11111111 mod 21: 11
  n: 9  rep: 111111111 mod 21: 6
  n: 10  rep: 1111111111 mod 21: 19
  n: 11  rep: 11111111111 mod 21: 2
  n: 12  rep: 111111111111 mod 21: 0
  n: 13  rep: 1111111111111 mod 21: 1
  n: 14  rep: 11111111111111 mod 21: 11
  n: 15  rep: 111111111111111 mod 21: 6
  n: 16  rep: 1111111111111111 mod 21: 19
  n: 17  rep: 11111111111111111 mod 21: 2
  n: 18  rep: 111111111111111111 mod 21: 0
  n: 19  rep: 1111111111111111111 mod 21: 1
  n: 20  rep: 11111111111111111111 mod 21: 11
  n: 21  rep: 111111111111111111111 mod 21: 6
  n: 22  rep: 1111111111111111111111 mod 21: 19
  n: 23  rep: 11111111111111111111111 mod 21: 2
  n: 24  rep: 111111111111111111111111 mod 21: 0
  n: 25  rep: 1111111111111111111111111 mod 21: 1
  n: 26  rep: 11111111111111111111111111 mod 21: 11
  n: 27  rep: 111111111111111111111111111 mod 21: 6
  n: 28  rep: 1111111111111111111111111111 mod 21: 19
  n: 29  rep: 11111111111111111111111111111 mod 21: 2
  n: 30  rep: 111111111111111111111111111111 mod 21: 0
  n: 31  rep: 1111111111111111111111111111111 mod 21: 1
  n: 32  rep: 11111111111111111111111111111111 mod 21: 11
  n: 33  rep: 111111111111111111111111111111111 mod 21: 6
  n: 34  rep: 1111111111111111111111111111111111 mod 21: 19
  n: 35  rep: 11111111111111111111111111111111111 mod 21: 2
  n: 36  rep: 111111111111111111111111111111111111 mod 21: 0
  n: 37  rep: 1111111111111111111111111111111111111 mod 21: 1
  n: 38  rep: 11111111111111111111111111111111111111 mod 21: 11
  n: 39  rep: 111111111111111111111111111111111111111 mod 21: 6
  n: 40  rep: 1111111111111111111111111111111111111111 mod 21: 19
  n: 41  rep: 11111111111111111111111111111111111111111 mod 21: 2
  n: 42  rep: 111111111111111111111111111111111111111111 mod 21: 0
  n: 43  rep: 1111111111111111111111111111111111111111111 mod 21: 1
  n: 44  rep: 11111111111111111111111111111111111111111111 mod 21: 11
  n: 45  rep: 111111111111111111111111111111111111111111111 mod 21: 6

Wed Nov 27 18:45:37 PST 2019

jagy@phobeusjunior:~$ 
$\endgroup$
1
1
$\begingroup$

$7|1001 = 7*11*13$

So $7|1001*111 = 111,111$ so if $7|\underbrace{1111.....1}_n$ then

$7|\underbrace{11111.....1}_n - 111111$

$ = \underbrace{1111111....111}_{n-6}000000$

and as $10$ and $7$ are relatively prime. $7|\underbrace{1111111....111}_{n-6}$

So by induction if $n \equiv a \pmod 6$ then $7|\underbrace{1111...1}_{a}$.

So we just need to show when does $7|1,11,111,1111,11111,111111$

And that is only $7|111111 = 111*1001 = (3*37)*(7*11*13)$.[*]

So $7|\underbrace{1111......1}_n$ if and only if $6|n$ in which case $3,11,13,37$ will also divide the repunit.

Thanks to Zubin Mukerjee for the hint.

.....

[*]. $7|\underbrace{111...1}_{a < 6}\iff 7|\underbrace{111...1}_{6-a}$ but $7\not \mid 1(a=1)$ and $7\not \mid 11 (a=2)$ and so $7\not \mid 11111 (6-1)$ and $7\not\mid 1111 (6-2)$ while $7\not \mid 111 =3*37$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.