Divisors count of $3^n\pm1$

Question

During the investigation of $3^n\pm1$ visually saw that the divisors count of it are sums of $2^m$.

Especially if we take $n=p_1p_2$ ($p_i$ is prime) then at least for $n=p_1p_2<130$ it is either sum of $2^{m_1}+2^{m_2}$ or just a $2^m$.

Actually this is true not only for $3^n\pm1$, but also for $4^n\pm1$ and $5^n\pm1$.

This should be related to Cyclotomic polynomials, but can not find a clue to prove or disprove the assumption.

Here is the list of all $p_1p_2<130$. The pattern below is $(p_1p_2,\tau(3^{p_1p_2}-1))$, where $\tau$ is a divisors count: $${(6, 16), (8, 24), (10, 24), (14, 16), (15, 24), (21, 16),\\ (22, 64), (26, 16), (27, 64), (33, 32), (34, 128), (35, 48),\\ (38, 64), (39, 96), (46, 32), (51, 64), (55, 128), (57, 128), \\(58, 256), (62, 128), (65, 96), (69, 64), (74, 128), (77, 128),\\ (82, 128), (85, 96), (86, 32), (87, 256), (91, 32), (93, 128),\\ (94, 512), (95, 96), (106, 128), (111, 128), (115, 192), (118, 64),\\ (119, 128), (122, 64), (123, 128), (125, 768), (129, 128)}$$

Answer 1

For any prime $p$, and for any integer $n$ not divisible by $p$, denote by $o_p(n)$ the smallest positive integer so that $n^{o_p(n)} \equiv 1 \pmod p$. Also, for any integer $m$, let $v_p(m)$ be the largest non-negative integer so that $p^{v_p(m)} | m$.

Now, let $n = q_1 \cdot q_2$, where $q_1<q_2$ are distinct primes, and $m = 3^n -1$.

If $p | m$ for some prime $p$, then $o_p(3)|q_1q_2$. So, $o_p(3)=1, q_1, q_2, q_1q_2$. So, either $p =2$, $q_1|p-1$, $q_2|p-1$ or $q_1q_2|p-1$.

We use the Lifting the Exponent Lemma repeatedly without comment.

Case 1: $q_1 =2$. Then, $v_2(9^{q_2} - 1) = v_2(9-1) = 3$. For any odd prime dividing $m$, $2q_2 | p-1$, so $v_p(3^{2q_2} - 1) = v_p(3^{p-1} -1)$.

Case 2: $q_1, q_2$ odd primes. Then, $v_2(3^{q_1q_2} - 1) = v_2(3-1) = 1$. If $p \neq q_1, q_2$, then $v_p(3^{o_p(3)} -1) = v_p(3^{q_1q_2} -1) = v_p(3^{p-1}-1)$.

If $p=q_1$, then $q_2 \nmid p-1$, so this cannot happen unless $p =2$. If $p= q_2$, then $o_p(3) = q_1 | p-1$ and $v_p(3^{q_1q_2} -1) = v_p(3^{o_p(3)} -1) + 1 = v_p(3^{p-1}-1) + 1$.

Thus, we conclude that $v_2(m) = 3$ or $1$, and for odd primes, $v_p(m) = v_p(3^{p-1} -1)$ or (for atmost one prime) $v_p(3^{p-1} -1) + 1$.

Number of divisors of $m$ is the product of $(v_p(m)+1)$.

Now, if $p$ is not a Wieferich Prime with base $3$, then $v_p(3^{p-1} -1) = 1$.

Thus, non Wieferich Primes contribute a factor of $2$ to the product (apart from at most one factor which could be $3$), and so we will need a Wieferich Prime with base $3$ and order at least $5$ to contradict the statement. No such primes are known.

Edit: For the general case of $m = 3^n -1$ for any $n$, it is not true. For example, if $n = 2^k$, $v_2(m) = k + 2$, so that indicates looking at $k = 4$. Indeed, for $k=4$, WolframAlpha gives $$m = 3^{16}-1 = 43046720 = 2^6 \cdot 5 \cdot 17 \cdot 41 \cdot 193 $$ so number of divisors is $7 \cdot 2^4$ which is $1110000$ in base $2$.

For $k=8$, Sage took around 15 secs to compute $$m = 3^{256} - 1 = 2^{10} \cdot 5 \cdot 17 \cdot 41 \cdot 193 \cdot 257 \cdot 275201 \cdot 21523361 \cdot 138424618868737 \cdot 926510094425921 \cdot 3913786281514524929 \cdot 153849834853910661121 \cdot 1716841910146256242328924544641$$ So, number of divisors of $m$ is $11 \cdot 2^{12}$ which is cannot be written as the sum or difference of two powers of $2$.

Answer 2

This isn't a disproof, but the following observations will give a clearer understanding of what is needed to produce a counter example.

First, the fundamental theorem of arithmetic says that every natural number can be expressed as the product of a unique multiset of primes. Therefore, $n=p_1^{c_1}p_2^{c_2}p_3^{c_3}...p_k^{c_k}$ where $p_i$ are primes and $c_i\in\Bbb{N}$. Then the number of factors that $n$ has is $$\prod_{a=1}^{k}\left(c_a+1\right)$$ Using this it is easy to show that if all of the exponents of the primes of $n$ are all one less than powers of two then the number of factors will be powers of two. An example of this is $3^6-1$ which has the prime factorization $2^3\cdot 7\cdot 13$. Each of the exponents are on less than a power of two and there are 16 factors in the number a power of two. Also if exactly one of the exponents is one less than a number that can be represented as the sum of two powers of two and the rest of the exponents are one less than a power of two then the number of factors can be represented as the sum of two powers of two. An example of this is $3^{10}-1$ which has the prime factorization $2^3\cdot 11^2\cdot 61$ The exponent for $11$ is one less than a number that can be represented as the sum of two powers of two. The other two exponents are one less than a power of two. The number of factors in this case is 24 which can be represented as the sum of two powers of two.

Second we can use euler's theorem which states that if $gcd(x,y)=1$ then $x|y^{\phi\left(x\right)}-1$. Where $\phi()$ is euler totient function. One way we could try to find a counter example is by making the exponent of one of the primes to be one less than a number that cannot be represented as the sum of two powers of two. The smallest number with this restriction is six. If $p^6|3^n-1$ then it might be a counter example. We can't use euler's theorem in a simple way in this case because then we would have $3^{(p-1)p^5}-1$. Which has far too many prime factors in the exponent to be considered because $n$ is restricted to $p_1p_2$. $x$ is guaranteed to divide $y^{\phi\left(x\right)}-1$, but $x$ can sometimes divide a smaller power $y$ minus one. When it does it the power is a factor of $\phi(x)$. For example $\phi(121)=110$ so if $y$ is coprime with $121$ then $121|y^{110}-1$. In the specific case where $y=3$, $121|3^5-1$. Notice that 5 is a factor of 110. This means that there can be prime power that divides $3^{p_1p_2}-1$ where the power cannot be represented as the sum of two powers of two.

I suspect that there is a counter example but the smallest one will be very large.