Is this conjecture related to Euler's totient function known?

217 Views Asked by At

Conjecture:

Let $a,b,n,m$ be natural numbers. Then the expression $$ a^{\frac{{\phi (b^n )}}{{\phi (b)}} - 1} \equiv b^0 + b^1 + b^2 + \ldots + b^{n - 1}\pmod{ b^n} $$ always holds true if $(a,b)=(2m,2m+1)$.


Note:

(1) We have experimentally varified the conjecture by putting values for $(a,b,n)$ as:

$(2,3,2);(2,3,3);(2,3,4);(2,3,5);(2,3,6);(2,3,7);(4,5,2);(4,5,3);(4,5,4);(4,5,5);(4,5,6);(4,5,7);(6,7,2);(6,7,3);(6,7,4);(6,7,5);(6,7,6);(6,7,7);(8,9,2);(8,9,3);(8,9,4);(8,9,5);(8,9,6);(8,9,7)$

So on...and Result always holds true.

(2) We can rewrite the same above expression by substituting value of $(a,b)=(2m,2m+1)$ and then expression will looks like this: $$ \sum\limits_{k = 0}^{n - 1} {(2m + 1)^k } \equiv (2m)^{\frac{{\phi ((2m + 1)^n )}}{{\phi (2m + 1)}} - 1} \pmod{(2m + 1)^n}. $$


Our attempts

Attempt 01:

Since $\gcd(a,b)=1$ as $a$, $b$ are consecutive natural numbers, we can say $\gcd(a,b^n)=1$ then by Euler's formula, we can write $$ a^{\phi (b^n )} \equiv 1 \pmod{b^n} $$ but after this we don't know how to proceed further.


Attempt 02:

Since $b^0+b^1+\ldots+b^k$ is a geometric series, it is $(b^n-1)/(b-1)$ where $k=n-1$. Then $(b^n-1)/(b-1)=(b^n-1)/a$.

But this attempt also does not help us very much.


Attempt 03:

In our third attempt, we expand $(2m+1)^k$ using the binomial theorem and we also used the expression $$ \phi (n^k ) = n^{k - 1} \phi (n) $$(see here) to modify the the power of $2m$ but this technique makes things more complicated.


OUR QUESTION: Is the conjecture above already known?

Case01: if your answer is yes, then provide refrence about how it is related to that theorem.

Case02: if your answer is no, then please provide an approach about how to prove this, otherwise provide a counterexample to prove it wrong.

1

There are 1 best solutions below

5
On BEST ANSWER

Euler's product formula states that $$\phi(\alpha)=\alpha\prod_{p|\alpha \text{ prime}}(1-1/p)$$ for an integer $\alpha>0$, from which it follows that $$\frac{\phi(b^n)}{\phi(b)}=b^{n-1}.$$

Since $a$ is coprime to $b$ and hence to $b^n$, $a$ is invertible modulo $b^n$, and thus your conjecture is equivalent to $$(b-1)^{b^{n-1}}\equiv (b-1)(1+b+\cdots+b^{n-1})\mod b^n,$$ which in turn is equivalent to $$(b-1)^{b^{n-1}}\equiv -1\mod b^n.$$

This last identity can be proven by induction on $n\geq 1$. The case $n=1$ is obvious. For the inductive step, assume that $xb^n=(b-1)^{b^{n-1}}+1$ for some integer $x$. Then $$(b-1)^{b^{n}}=\left((b-1)^{b^{n-1}}\right)^b=(xb^n-1)^b=\sum_{k=0}^b\binom{b}{k}x^kb^{kn}(-1)^{b-k}.$$

Modulo $b^{n+1}$, all terms in the right sum vanish (since $b^{kn}\equiv 0\mod b^{n+1}$ if $k>0$), except the first one, which is $(-1)^{b}=-1$ as $b$ is odd. This means that $$(b-1)^{b^n}\equiv -1\mod b^{n+1},$$ as was the goal.