2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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}

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