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

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

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

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

$$(2^n-1)(2^{\sigma(n)}-1) \equiv 3 \pmod {2^{\varphi(n)}-1}$$

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

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

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

SigmaTotient1(lb,ub)={
forprime(n=lb,ub,
if(!(Mod((2^n-1)*(2^sigma(n)-1),2^eulerphi(n)-1)==3),print(n)))
}

SigmaTotient2(lb,ub)={
forcomposite(n=lb,ub,
if((Mod((2^n-1)*(2^sigma(n)-1),2^eulerphi(n)-1)==3),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^n-1}{b-1}\cdot \frac{b^{\sigma(n)}-1}{b-1} \equiv b+1 \pmod {\frac{b^{\varphi(n)}-1}{b-1}}$$

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

• Nice criterion, if it is actually true. – Peter Jan 14 '18 at 13:06

Let $n=p_1^{a_1}\cdot p_2^{a_2}\cdots p_k^{a_k}$.
Since $\phi(n)$ is divisible by $p_i$ if the exponent $a_i$ is greater than $1$, we have then: $p_i\mid \phi(n), p_i\mid n$ which means that $2^n-1, 2^{\phi(n)}-1$ are both divisible by $2^{p_i}-1$.

If the congruence you mention holds, then $2^{p_i}-1$ must divide $3$, which means $2^{p_i}-1=3$ and $p_i=2$.
This shows that $n=2^{a}\cdot p_2\cdots p_k$.

But then, $\sigma(n)=\frac{2^{a_1+1}-1}{2-1}(p_2+1)\cdots (p_k+1)$ which is divisible (since the other primes are odd) by $2^{k-1}$ and $\phi(n)$ is also divisible by $2^{k-1}$.
This means that (again from the congruence) $2^{2^{k-1}}-1$ divides $3$, which shows $k-1=1\Rightarrow k=2$ and $n=2^a\cdot p$. If $a\ge2$, then $2^{\phi(n)}-1$ is divisible by $5$ and so is $2^{n}-1$ which means that $5\mid 3$ which is false.
This shows the following:
If $n$ is odd, then clearly is a prime.
If it is even, then $n=2p$.
But, now (if $n=2p$) we can see from the congruence that $(2^{2p}-1)(2^{3p+3}-1)\equiv 3\pmod{2^{p-1}-1}$. But from Fermat's Little theorem we know that $2^{p-1}\equiv 1\pmod{p}$, so $(2^{2p}-1)(2^{3p+3}-1)\equiv 3\pmod{p}$ which yields $(2^2-1)(2^3\cdot 2^3-1)\equiv 3\pmod{p}$ and finally $p\mid 362$.
We can check if the even divisors of $362$ satisfy your claim and we are done.
I think this proves the claim.

• I do not understand why you don't accept the answer since it is correct and you need it so much (since you offer a bounty) – Konstantinos Gaitanas Jan 22 '18 at 16:40