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 :




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

  • $\begingroup$ Nice criterion, if it is actually true. $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – Konstantinos Gaitanas Jan 22 '18 at 16:40

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.