Let $p>2$ be a prime number, $m>1$ and $n$ be positive integers such that $\frac {m^{pn}-1}{m^n-1}$ is a prime number. Show that: $$pn\mid (p-1)^n+1$$
Problem
Source: Turkey Team Selection Test 2019 Day 3 Problem 8
Tags: number theory
26.03.2019 11:52
Outline of the solution: 1- $n=p^{k}$ Consider $n=p^{k}.t$ and prove that $\frac{m^{p^{k+1}}-1}{m^{p^{k}}-1}$ divides $\frac{m^{p^{k+1}t}-1}{m^{p^{k}t}-1}$ so $t=1$. 2- Using $LTE$, $p^{k+1}$ divides $(p-1)^{p^{k}}+1$.
27.03.2019 03:47
Not much different from the outline above. The key identity, that we use is $(m^a-1,m^b-1)=m^{(b,a)}-1$. We begin by proving $n$ is a power of $p$. To see this, we first show $p\mid n$. Assume, $p\nmid n$. If $n=1$, then we have the condition trivially. If not, then let $m^{pn}-1=(m^n-1)q$ for some prime $q$. Note that, if $(p,n)=1$, then $(m^p-1,m^n-1)=m-1$. Hence, $m^{pn}-1=\ell \cdot \frac{m^p-1}{m-1}(m^n-1)$ for some $\ell>1$, and we have therefore, $q=\ell \frac{m^p-1}{m-1}$, thus $q$ is never a prime. Now, let $n=p^k n_1$ with $p\nmid n_1$. Suppose, $n_1>1$. We have, $m^{p^{k+1}n_1}-1 = (m^{p^k n_1}-1)q$ for some prime $q$. Now, observe that, $(m^{p^{k+1}}-1,m^{p^k n_1}-1)=m^{p^k}-1$. Hence, for some $\ell'>1$, it holds: $$ m^{p^{k+1}n_1}-1 = \ell' \frac{m^{p^{k+1}}-1}{m^{p^k}-1} (m^{p^k n_1}-1) =(m^{p^k n_1}-1)q \implies q=\ell' \frac{m^{p^{k+1}}-1}{m^{p^k}-1}, $$and since by assumption $n_1>1$, it follows that $\ell'>1$, and thus $q$ is never a prime. Hence, $n=p^k$. Finally, we have, using lifting the exponent lemma, $v_p((p-1)^{p^k}+1)=v_p(p)+v_p(p^k)=k+1$, hence, $p^{k+1}=pn \mid (p-1)^n+1$, where $v_p(x)$ is the $p-$adic valuation of $x\in\mathbb{Z}$, that is, $p^{v_p(x)}\mid x $, and $p^{v_p(x)+1}\nmid x$.
09.09.2019 21:21
@above,I think you should clearify why $\ell '>1$.It follows easily from zigmondy's Theorem.Do you have any more elementry solution?
02.10.2021 17:54
I will repeatedly use the fact that $\text{gcd}(m^x - 1 , m^y - 1) = m^{\text{gcd}(x,y)} - 1$ for any $m > 1$ and $x,y \in \mathbb{N}$. Let $\frac{m^{np} - 1}{m^n - 1} = q$ where $q$ is a prime. Now if $p \nmid n$, then $\text{gcd}(m^p - 1 , m^n - 1) = m - 1$ and so $\frac{m^p - 1}{m-1}$ divides $m^{pn} - 1$ and that $\text{gcd}(m^n - 1 , \frac{m^p - 1}{m-1}) = 1$, these two imply that $\frac{m^p - 1}{m-1} = q = \frac{m^{pn} - 1}{m^n - 1}$. But, $m^{p+n} > (m^n - 1)(m^p - 1) = (m-1)(m^{np} - 1) > m^{np}$, implying that $(p-1)(n-1) = pn - p - n + 1 < 1$, a contradiction. So $p \mid n$. Let $n = p^k \cdot t$ where $\text{gcd}(t,p) = 1$. We have $\frac{m^{p^{k+1} \cdot t} - 1}{m^{p^k \cdot t} - 1} = q$. Since $\text{gcd}(\frac{m^{p^{k+1}} - 1}{m^{p^k} - 1} , m^{p^k \cdot t} - 1) = 1$ and $\frac{m^{p^{k+1}} - 1}{m^{p^k} - 1} \mid m^{p^{k+1} \cdot t} - 1$, this means that $\frac{m^{p^{k+1}} - 1}{m^{p^k} - 1} = q = \frac{m^{p^{k+1} \cdot t} - 1}{m^{p^k \cdot t} - 1}$. But since the function $f(x) = \frac{c^{px} - 1}{c^x - 1}$ is increasing, this means $t = 1$. But then by LTE, $v_p((p-1)^n + 1) = 1 + v_p(n) = k + 1$, giving us $pn = p^{k+1} \mid (p-1)^n + 1$, as wanted.
20.07.2024 14:31
\[q(m^n-1)=m^{np}-1\]Let's show that $n=p^\alpha$ which would be enough since $p^{\alpha+1}|(p-1)^{p^\alpha}+1$ comes from LTE. Claim $1$: $p|n$ or $n=1$. Proof $1$: Suppose that $p$ doesn't divide $n>1$. By Zsigmondy, there exists a prime divides $m^p-1$ but not $m^i-1$ for $i\leq p-1$. If that prime is $r$, then $r|m^p-1|m^{np}-1|q(m^n-1)$. If $r|m^p-1$ and $r|m^n-1$, then $r|m^{(n,p)}-1=m-1$ but this contradicts. So $r|q$ or $r=q$. This gives that $q|m^p-1$. But $m^p-1\geq q=\frac{m^{np}-1}{m^n-1}$ yields $(m^p-1)(m^n-1)\geq m^{np}-1$ or $m^{n+p}-m^p-m^n\geq m^{np}-2$ Since $p,n>1,$ we have $pn+1>p+n$ thus, $m^{np}-2\leq m^{n+p}-m^p-m^n\leq m^{np}-m^p-m^n$ which gives that $2\geq m^n+m^p$ so $m=1$ but this is impossible.$\square$ Let $n=p^\alpha k$ where $(p,k)=1$. Denote $m^{p^\alpha}=a$. Hence $q=\frac{m^{p^{\alpha+1}k}-1}{m^{p^\alpha k}-1}=\frac{a^{pk}-1}{a^k-1}$ By Claim $1$, we get that $p|k$ or $k=1$. Since $p\not| k,$ we have $k=1$. Thus, $n=p^{\alpha}$ as desired.$\blacksquare$