A congruence with the Euler's totient function and number of divisors function

Question

Can you provide a proof or a counterexample to the claim given below ?

Inspired by the congruence $1.3$ in this paper I have formulated the following claim :

Let $n$ be a natural number , let $\tau(n)$ be number of divisors function and let $\varphi(n)$ be Euler's totient function , then :

$$(2^{\varphi(n)}-1)(2^{\tau(n)}-1) +2 \equiv 2^{n-1} \pmod {2^{n}-1}$$

for all primes and no composite with the exception of $4$ .

I have tested this claim up to $5 \cdot 10^6$ .

I was searching for a counterexample using the following two PARI/GP codes :

NumdivTotient1(lb,ub)={
forprime(n=lb,ub,
if(!(Mod((2^eulerphi(n)-1)*(2^numdiv(n)-1)+2,2^n-1)==2^(n-1)),print(n)))
}

NumdivTotient2(lb,ub)={
forcomposite(n=lb,ub,
if((Mod((2^eulerphi(n)-1)*(2^numdiv(n)-1)+2,2^n-1)==2^(n-1)),print(n)))
}

Remark

More generally we can formulate the following claim :

Let $b$ and $n$ be a natural numbers , $b \ge 2$ , then

$$\frac{b^{\varphi(n)}-1}{b-1}(b^{\tau(n)}-1) + b \equiv b^{n-1} \pmod {\frac{b^{n}-1}{b-1}}$$

for all primes and no composite with the exception of $4$ .

Answer 1

We have

$$n = \sum_{d\mid n} \varphi(d)\,,$$

so

$$\varphi(n) + \tau(n) = n - \sum_{\substack{d\mid n \\ d < n}} \varphi(d) + \sum_{d \mid n} 1 = (n+1) - \sum_{\substack{d \mid n \\ 1 < d < n}}\bigl(\varphi(d) - 1\bigr)\,.$$

If $n$ is composite and has a prime factor $\geqslant 5$, it follows that $\varphi(n) + \tau(n) < n-1$. If $n > 9$ is divisible by $8$ or by $9$, it also follows that $\varphi(n) + \tau(n) < n-1$. If $\varphi(n) + \tau(n) < n-1$, it follows that

$$(b^{\varphi(n)} - 1)(b^{\tau(n)} - 1) + b = b^{\varphi(n) + \tau(n)} - (b^{\varphi(n)} - b) - (b^{\tau(n)} - 1) \leqslant b^{\varphi(n) + \tau(n)} < b^{n-1}\,,$$

whence the congruence cannot hold for such $n$.

The remaining cases of composite $n$ - that is, $n \in \{ 4, 6, 8, 9, 12\}$ - are easily checked by hand, and that the congruence holds for prime $n$ follows from $\varphi(n) = n-1$ and $\tau(n) = 2$:

\begin{align} \frac{(b^{n-1}-1)(b^2-1)}{b-1} + b &= \frac{b^{n+1} - b^{n-1} - b^2 + 1 + b^2 - b}{b-1} \\ &= \frac{b^{n+1} - b^{n-1} - b + 1}{b-1} \\ &= b^{n-1} + \frac{b^{n+1}-b^n-b+1}{b-1} \\ &= b^{n-1} +(b-1)\frac{b^n-1}{b-1}\,. \end{align}