Nadim Ul Abrar wrote:Find all pairs of positive integer $(n,p)$ such that
$(i)$ . $ p $ is a prime number
$(ii)$ . $n \leq2p$
$(iii)$ . $ n^{p-1}$ divides $(p-1)^n+1$
Firstly, it is a generalization of $IMO-1990, 3$.
আমার মনে হয় এই ধরনের প্রব্লেম এ সবার আগেই $LTE$ আর
special primes এর কথা মনে করা উচিত। special primes মানে হচ্ছে যে prime গুলা নিয়ে কাজ করলে তাদের মান পাওয়া যায়। যেমন
smallest prime factors or some arbitrary prime factors of $n$.
In this case, assume $q$ to be the smallest prime factor of $n$. Now if $p$ even, then we easily get $n|2\Rightarrow n=1,2$. Let's assume $n>1$ and odd. Then, \[(p-1)^{2n}\equiv1\pmod q\]
Also, $q|(p-1)^n+1$ easily shows $q$ is co-prime to $p-1$. Therefore, \[(p-1)^{q-1}\equiv1\pmod q\]
\[(p-1)^{\gcd(2n, q-1)}\equiv1\pmod q\]
Since $q$ is the smallest prime factor of $n$, every prime factor of $q-1$ is co-prime to $n$. Hence, $\gcd(2n,q-1)=\gcd(2,q-1)=2$. \[(p-1)^2\equiv1\pmod q\]
So we get $q|p-1+1$ or $q|p-1-1$ since $q$ is a prime(otherwise we could hardly conclude that). If $q|(p-1)-1$ then $q|(p-1)^n-1\Rightarrow q|2\Rightarrow q=2$. But this leaves a contradiction.
Thus, $q|p$ and so, $p=q$. Now, see the maximum powers of $p$ in both side to get the value of $p$. Assume $\nu_p(n)=\alpha$.
\[\nu_p(n^{p-1})=(p-1)\alpha\]
\[\nu_p((p-1)^n+1)=\alpha+1\]
Invoking $LTE$, \[(p-1)\alpha\le \alpha+1\]
\[\Rightarrow (p-2)\alpha\le1\]
which would be false for $p>3$. Hence, $p=3,\alpha=1$, $n=3k$. So we are reduced to \[n^2|2^n+1\]
We get \[k^2|8^k+1\]
Next assume $r$ to be the smallest prime factor of $k$. In a similar manner we did to find $p$, \[8^2\equiv1\pmod r\]
And since $3\not|q$, it must be $q=7$. On the other hand, $8^k+1\equiv2\pmod7$. This implies a contradiction. So, we can't have a $k$ such that $k$ has a prime factor. Thus, $k=1$ and then $n=3$
.