# Number of prime factors of $3^n-1$

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.

• 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$. Aug 26, 2019 at 8:40
• @Servaes Yes, it's easy. Notice that $3^n-1\equiv (-1)^n-1\equiv -2 (\mod 4)$. Aug 26, 2019 at 8:43
• @WangWeixuan This is useful for my proof in the answer because we do not need the proven Catalan conjecture. Aug 26, 2019 at 8:59

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$$.

• 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 Aug 26, 2019 at 8:39
• @MarkBennet I though it would be $\ge$ instead of $>$, thanks for pointing this out. Aug 26, 2019 at 8:48
• @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$. Aug 26, 2019 at 8:52
• @MarkBennet Now correct ? Aug 26, 2019 at 8:57
• 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. Aug 26, 2019 at 10:42