Prove that for every two positive integers $a,b$ greater than $1$. there exists infinitly many $n$ such that the equation $\phi(a^n-1)=b^m-b^t$ can't hold for any positive integers $m,t$.
Problem
Source: Iranian Third Round 2020 Number Theory exam Problem4
Tags: number theory, totient function
25.11.2020 08:28
Let FSOC $\exists$ finitely many $n$ for which $\phi(a^n-1)=b^m-b^t$ can't hold for any positive integers $m,t$. Then there exists $N$ s.t. $\forall$ $n\geq N$, $\phi(a^n-1)=b^m-b^t$ has a solution in positive integers $m,t$. Call $a^N$ as $c$. Then $\phi(c^n-1)=b^m-b^t$ has a solution for all $n\in\mathbb{N}$. Now let $p$ be an odd prime not dividing $b,c$. We'll look at $c^{2^kp}+1$ for $k\geq 0$. By $\textit{Zsigmondy's thm}$ there exists prime $q$ which divides $c^{2^{k+1}p}-1$ but doesn't divide $c^{2^{k+1}}-1$ and $c^{2^kp}-1$. Let $m=ord_q(c)$. Then $m$ divides $2^{k+1}p$ but doesn't divide $2^kp$ and $2^{k+1}$. So $m=2^{k+1}p$. However we also have $q$ divides $c^{q-1}-1$ by $\textit{Fermat's little thm}$. So from basic property of order we obtain $2^{k+1}p$ divides $q-1$. More specifically $p$ divides $q-1$. From formula of $\phi$ we obtain $p$ divides $\phi(c^{2^kp}+1)$. Now let us look at $\phi(c^{2^np}-1)$ for some large $n$. We write $c^{2^np}-1$ as $(c^p-1)(c^p+1)...(c^{2^{n-1}p}+1)$. Note that $\gcd$ of any $2$ terms in this expansion is either one $1$ or $2$. So we obtain that $\phi(c^{2^np}-1)$ is divisible by $\frac{\phi(c^p-1)\phi(c^p+1)...\phi(c^{2^{n-1}p}+1)}{2^n}$. Note that $p$ also divides $\phi(c^p-1)$. (This is kind of well known and can be proved using order). From this we obtain $p^n$ divides $\phi(c^{2^np}-1)$. Now there exist $m,t$ s.t. $\phi(c^{2^np}-1)=b^m-b^t=b^t(b^{m-t}-1)$. Thus $p^n$ divides $b^t(b^{m-t}-1)$. Let $m-t=s$. So we obtain $p^n$ divides $b^s-1$ as $p$ and $b$ are coprime. Now let $k$ be $ord_p(b)$ and let $\nu_p(b^k-1)=l$. Clearly $k$ divides $s$ say $s=kr$ by basic property of order. Then by $\textit{LTE}$ we obtain $\nu_p(b^s-1)=\nu_p(b^k-1)+\nu_p(r)=l+\nu_p(r)\geq n$. So $\nu_p(r)\geq n-l$ which implies $r\geq p^{n-l}$. So $s\geq p^{n-l}$ which gives $\phi(c^{2^np}-1)>b^{p^{n-l}}-1$. But selecting $n$ to be large enough we obtain that $b^{p^{n-l}}-1>c^{2^np}-1$ which is clearly a contradiction. Hence our assumption that $\exists$ finitely many $n$ for which $\phi(a^n-1)=b^m-b^t$ can't hold for any positive integers $m,t$ was wrong. So there exists infinitely many $n$ such that the equation $\phi(a^n-1)=b^m-b^t$ can't hold for any positive integers $m,t$. Q.E.D
01.11.2021 07:35
Mr.C wrote: Prove that for every two positive integers $a,b$ greater than $1$. there exists infinitly many $n$ such that the equation $\varphi(a^n-1)=b^m-b^t$ can't hold for any positive integers $m,t$. FTSOC,assume not i.e only finitely many such $n$ exist;consider $n=2^e b^k $ for sufficiently large $(e,k)$ s.t $k>2^e$ Then by the multiplicative-ness of the phi function we get:-$$\varphi\left(a^{2^e b^k}-1 \right)=\varphi \left(a^{b^k}+1 \right) \cdot \prod_{j=1}^{e-1} \varphi \left(a^{2^jb^k}+1 \right)$$Bounding this between two consecutive pairs of $b^{c(e+1)\left(\frac{e}{2}+k \right)}$ gives the result.