Let $d(n)$ denote the number of positive divisors of $n$. Find all triples $(n,k,p)$, where $n$ and $k$ are positive integers and $p$ is a prime number, such that \[n^{d(n)} - 1 = p^k.\]
Problem
Source: 2012 Baltic Way, Problem 17
Tags: number theory unsolved, number theory
23.11.2012 00:50
If $n^{d(n)}$ is a perfect square it's easy to conclude that we must have $n=3, k=3, p=2$ or $n=2, k=1, p=3$. If $d(n)$ is even, then it follows. So assume $d(n)$ is odd. Then $v_p(n)$ for each $p$ dividing $n$ must be even, and we can conclude that $n$ is a perfect square, and again it follows. So the only such triplets are the ones mentioned previously. A much quicker solution is simply citing Catalan's Conjecture (or Mihăilescu's theorem).
23.11.2012 11:58
How about Zsigmondy?
29.11.2012 14:04
Yes, applying Zsigmondy's theorem solves the problem immediately.
06.09.2016 09:43
Obviously $n\ge 2$. Case1:$n=2$ $3=p^k\rightarrow p=3,k=1$ which satisfies the condition. Case2:$n\ge 3$ If $d(n)\neq 2$,By Zsigmondy's theorem,∃$q$(prime) s.t. $q|n^{d(n)}-1,q\nmid n-1$.Since $n-1|n^{d(n)}-1$,this is absurd.Hence $d(n)=2$.Then $(n+1)(n-1)=p^k$.For $s>t\ge 0$, \[\left\{\begin{array}{cc} n+1=p^s \\ n-1=p^t \\ \end{array}\right.\]$\rightarrow 2=p^t(p^{s-t}-1)$.If $t=0$,then $p=3,s=1,n=2$ which is absurd.Thus $t\ge 1$ and $p=2,t=1,s=2,n=3,k=3$. which satisfies the condition. From case$1,2$,the answer is $\boxed{(n,k,p)=(2,1,3),(3,3,2)}\blacksquare$
06.09.2016 09:48
Can we quote Zsigmondy on the IMO and TSTs? Itkills many problems instantly.
06.09.2016 09:58
I'm worried about that too. Are you going to participate $IMO$? Anyone who has participated $IMO$:Please tell us Zsigmondy's theorem on $IMO$.
06.09.2016 13:38
I wil try my best to get into the $\mathbb{IMO}$ team for 2017. But most probably I am going to the Astronomy training camp this year.
06.09.2016 14:35
That's wonderful!!!