2
$\begingroup$

Problem:

Prove or refute: for integer $n\ge 3$, we have $$\omega(3^n-1)>\omega(n),$$ where $\omega(n)$ means number of distinct prime factors of $n$.

I believe the statement is true.

It seems easy to prove when $n$ is a prime, but I am stuck at how to extend my proof to general integers. I tried factorization of $3^n-1$ when $n$ is composite, as is demonstrated here, but cannot proceed further.

Thanks for your help.

$\endgroup$
3
  • $\begingroup$ Of course it is easy to prove for prime $n$; then $\omega(n)=1$ and $3^n-1$ is even, so it suffices to show that $3^n-1$ is not a power of $2$. $\endgroup$
    – Servaes
    Aug 26, 2019 at 8:40
  • 1
    $\begingroup$ @Servaes Yes, it's easy. Notice that $3^n-1\equiv (-1)^n-1\equiv -2 (\mod 4)$. $\endgroup$ Aug 26, 2019 at 8:43
  • $\begingroup$ @WangWeixuan This is useful for my proof in the answer because we do not need the proven Catalan conjecture. $\endgroup$
    – Peter
    Aug 26, 2019 at 8:59

1 Answer 1

4
$\begingroup$

If $p$ is an odd prime , the number $3^p-1$ cannot be a power of $2$ (Catalan's conjecture , now proven , but it might be easier to prove this particular claim), hence $3^p-1$ has an odd prime factor.

Moreover, if $p$ and $q$ are distinct odd primes, we have $\gcd(3^p-1,3^q-1)=3^{\gcd(p,q)}-1=2$ , hence if we choose an odd prime factor of $3^p-1$ and an odd prime factor of $3^q-1$, they must be distinct.

Hence for every odd prime factor of $n$, we have an odd prime factor of $3^n-1$ without duplicates. Since $2$ is always a factor of $3^n-1$, we have shown $\omega(3^n-1)\ge \omega(n)$.

To complete the proof, we have to show that $3^{2p}-1$ has two distinct odd prime factors , if $p$ is an odd prime , but this follows from $\gcd(3^p-1,3^p+1)=2$ and the fact that $3^p+1$ can also be no power of $2$.

$\endgroup$
8
  • 2
    $\begingroup$ I think if $n$ is even you need to find one more factor - for example you need to find three prime factors of $3^{2p}-1$ - but once you have done it for $2p$ the argument can be completed $\endgroup$ Aug 26, 2019 at 8:39
  • $\begingroup$ @MarkBennet I though it would be $\ge$ instead of $>$, thanks for pointing this out. $\endgroup$
    – Peter
    Aug 26, 2019 at 8:48
  • $\begingroup$ @MarkBennet If $n$ is even, say $n=2m$, then $$3^n-1=(3^m-1)(3^m+1),$$ both factors are even and their gcd is $2$, so for $m>1$ this yields three distinct prime factors once you show/note that neither factor is a power of $2$. $\endgroup$
    – Servaes
    Aug 26, 2019 at 8:52
  • $\begingroup$ @MarkBennet Now correct ? $\endgroup$
    – Peter
    Aug 26, 2019 at 8:57
  • 1
    $\begingroup$ Looks good. The issue @WangWeixuan raises is easily dealt with because $2p$ and $q$ have gcd $1$, and the argument in the answer can be adapted. $\endgroup$ Aug 26, 2019 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .