APMO 2012 #3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

APMO 2012 #3

G H J

Reveal topic tags

modular arithmetic

L

G H BBookmark kLocked kLocked NReply

Source: APMO 2012 #3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

202 posts

#1 h Apr 2, 2012, 3:09 PM • 5 Y

Y by Davi-8191, chessgocube, SADAT, Adventure10, Mango247

Determine all the pairs $(p , n )$ of a prime number $p$ and a positive integer $n$ for which $\frac{ n^p + 1 }{p^n + 1}$ is an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2903 posts

#2 h Apr 2, 2012, 4:14 PM • 4 Y

Y by Binomial-theorem, chessgocube, Adventure10, Mango247

Ah APMO problems have been posted!

A bit easy for APMO though

First remark that if $p < n$ , then $p^n > n^p$ so $p^n + 1 > n^p + 1$ and the problem obviously doesn't hold. Hence $p \ge n$ .
Consider a prime power $z^k|(p+1)$ . Unless $n \equiv -1 \pmod{z^k}$ we have $\text{ord}_{z^k}(n) = 2p$ . But that's obviously false as $2p > z^k$ , hence $n \equiv -1 \pmod{z^k}$ or all prime powers which divides $(p+1)$ . But this implies $n \equiv -1 \pmod{p+1}$ , and hence as $p \ge n$ the only solutions are when $n=p$ which obviously work. Hence all solutions are $(p,p)$ for $p$ a prime number.

EDIT : Oops my inequality fails when $p=2$ , so $(2,4)$ is also a solution. Here is a proof $a^b > b^a$ when $a > 2$ and $a < b$ to make sure I don't mess up more.
It suffices to show $a^{b/a} > b$ . When $a > e \approx 2.718$ we know $a^z > za$ for $z > 1$ so the result follows. To prove this, consider the function $f(x) = a^x - ax$ . $f'(x) = \ln a a^x - a$ . Remark that $f'(x) \ge 0$ for $x \ge 0$ and the result follows as $f(1) = 0$ .

Now for $p=2$ , $2^n > n^2$ for $n > 4$ so it follows the only solutions are $(p,p)$ and $(2,4)$ .

This post has been edited 1 time. Last edited by dinoboy, Apr 2, 2012, 4:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

245 posts

mlm95

#3 h Apr 2, 2012, 4:24 PM • 6 Y

Y by perfect_square, ---Fermat---, ZHEKSHEN, chessgocube, Adventure10, Mango247

I'm not agree with you $p=2$ and $n=4$ is an answer notice that $2^{4}=4^{2}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1347 posts

WakeUp

#4 h Apr 2, 2012, 10:57 PM • 8 Y

Y by dizzy, Binomial-theorem, AdiletR, Orkhan-Ashraf_2002, Vietjung, chessgocube, Adventure10, Mango247

My solution is slightly different from that of dinoboy's:

If $p=2$ then $n=2$ and by the inequality $2^n>n^2$ for $n>4$ , we get that $n=2$ or $n=4$ work.

Otherwise $p\ge 3$ so $p$ is odd, meaning $n$ must be also odd since $2|n^p+1$ . Hence $p^n+1$ can be factorised as $(p+1)(p^{n-1}-p^{n-2}+\ldots +p^2-p+1)$ . Thus $p+1|n^p+1$ . Let $q$ be a prime factor of $p+1$ . Suppose $q$ is odd. Now $q|n^p+1$ so $n^{p}=-1\pmod{q}$ . Since $q$ is odd, this means $\text{ord}_q(n)\in\{2,2p\}$ .

If $\text{ord}_q(n)=2$ then $n^2=1\pmod{q}$ . If $n=1\pmod{q}$ then $1=n^p=(-1)^p=-1\pmod{q}$ but $q\nmid 2$ , so this is impossible. Hence $n=-1\pmod{q}$ and so $q|n+1$ .

If $\text{ord}_q(n)=2p$ then $2p|q-1$ (note that $n^{q-1}=1\pmod{q}$ by FLT) but also $q|p+1$ . These divisibilities imply that either $q=1$ or $2p\le p$ , both of which are of course contradictory.

So if $q\not= 2$ then $q|n+1$ . If $q=2$ then clearly $q|n+1$ as $n$ is odd.

Now suppose for some prime divisor $r$ of $p+1$ , we have that $v_r(p+1)>v_r(n+1)$ (we denote the number $k$ such that $a^k||b$ as $v_a(b)$ ). Therefore since $p+1|n^p+1=(n+1)(n^{p-1}-n^{p-2}+\ldots +n^2-n+1)$ , we have that $r|n^{p-1}-n^{p-2}+\ldots +n^2-n+1$ . But $n=-1\pmod{r}$ and $p$ is odd, implying that $0=n^{p-1}-n^{p-2}+\ldots +n^2-n+1=1+1+\ldots +1+1+1=p\pmod{r}$ . Therefore $r|p$ , impossible in view of the fact that $r|p+1$ . Hence $v_r(p+1)\le v_r(n+1)$ for all prime divisors $r$ of $p+1$ . Therefore $p+1|n+1\implies p\le n$ . As dinoboy has already noted, we have must $p\ge n$ , so overall $p=n$ giving all solutions to be $(p,p)$ for all primes $p$ and $(2,4)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

571 posts

yunxiu

#5 h Apr 4, 2012, 11:12 AM • 12 Y

Y by Vietjung, golema11, puntre, ZHEKSHEN, chessgocube, Mathlover_1, Adventure10, Mango247, and 4 other users

An other solution:
If $p = 2$ , then ${n^2} + 1 \geqslant {2^n} + 1$ , so we have $n \leqslant 4$ , it is easy to see $n = 2,4$ .
Now we suppose $p$ is an odd prime, so $n$ is odd, because ${n^p} + 1 \geqslant {p^n} + 1 > 3$ , so $n \geqslant 3$ .
Because $f(x) = {x^{1/x}}$ is decrease for $x \geqslant e$ , from ${n^{1/n}} \geqslant {p^{1/p}}$ we have $n \leqslant p$ .
Because $p + 1\left| {{p^n} + 1} \right.$ , ${n^p} + 1 \equiv 0 \equiv {p^p} + 1(\bmod p + 1)$ , so ${n^p} \equiv {p^p}(\bmod p + 1)$ . By $Euler$ theorem ${n^{\varphi (p + 1)}} \equiv 1 \equiv {p^{\varphi (p + 1)}}(\bmod p + 1)$ , so ${n^{(p,\varphi (p + 1))}} \equiv {p^{(p,\varphi (p + 1))}}(\bmod p + 1)$ , hence $n \equiv p(\bmod p + 1)$ , because $1 \leqslant n \leqslant p$ , we have $n = p$ .
Above all, $(p,n) = (p,p),(2,4)$ are the all solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4535 posts

#6 h May 28, 2012, 8:43 PM • 3 Y

Y by Ibraheem, Adventure10, Mango247

Why does ${n^{(p,\varphi (p+1))}}\equiv{p^{(p,\varphi (p+1))}}(\bmod p+1)$ imply $n\equiv p \mod p+1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

571 posts

yunxiu

#7 h May 29, 2012, 1:34 AM • 4 Y

Y by AwesomeToad, ZHEKSHEN, Adventure10, Mango247

AwesomeToad wrote:

Why does ${n^{(p,\varphi (p+1))}}\equiv{p^{(p,\varphi (p+1))}}(\bmod p+1)$ imply $n\equiv p \mod p+1$ ?

Because $p$ is a odd prime, $p + 1$ is even, so every prime factor of $\varphi (p + 1)$ is less then $\frac{{p + 1}}{2} < p$ , hence $\left( {p,\varphi (p + 1)} \right) = 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

944 posts

#8 h Aug 23, 2013, 1:41 AM • 2 Y

Y by Adventure10, Mango247

Can someone tell me if this solution is valid or not? I'm not really to sure about it so I would appreciate any input. Thanks in advance. (Also, I wasn't sure whether to make a new thread or to revive this old one, so I apologize if I have done the wrong thing)

my solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2229 posts

#9 h Mar 9, 2014, 6:44 AM • 2 Y

Y by Adventure10, Mango247

@sicilianfan: Your solution is correct. Nice argument regarding how much each quantity increases! And also the fact that $n \cong -1 (mod p+1)$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

944 posts

#10 h Mar 10, 2014, 2:40 AM • 2 Y

Y by Adventure10, Mango247

Thanks for the feedback, but there actually was a problem with my solution (of which I was informed a while ago): I assumed that just because $\text{ord}_{p+1}(n)=2$ that $n \equiv -1 \pmod{p+1}$ which is in fact only true if $p+1$ has a primitive root (this is what I overlooked), which is certainly not a valid assumption. It can be fixed by taking mod $q$ where $q$ is a prime that divides $p+1$ instead, and patching from there.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

95 posts

#11 h Nov 2, 2014, 8:37 PM • 7 Y

Y by Ferid.---., jlammy, rightways, Adventure10, Mango247, farhad.fritl, and 1 other user

If $p=2$ , then $n^2 + 1 \geq 2^n + 1 \implies n \leq 4$ . Easily, we can see $(p,n) = (2,2); (2,4)$ are the only solution in this case.

Suppose now that $p \geq 3$ is an odd prime. Since $n^p + 1 \geq p^n + 1$ , we have $n \geq 3$ . Now $n^p \geq p^n \implies n^{\frac{1}{n}} \geq p^{\frac{1}{p}} \implies n \leq p$ since $f(x) = x^{\frac{1}{x}}$ is a decreasing function for $x \geq e$ .

$(p+1) \mid p^n + 1 \implies (p+1) \mid n^p + 1$ . Hence $n^p \equiv -1 \pmod {p+1}$ , so it follows that $\text{ord}_{p+1}(n) = 2$ or $2p$ . The second option is absurd, since $2p > p+1 > \phi (p+1)$ , so $\text{ord}_{p+1} (n) = 2$ : i.e. $n^2 \equiv 1 \pmod {p+1}$ . Now $-1 \equiv n^p \equiv n^{p-1}\cdot n \equiv n \pmod {p+1}$ , so $p=n$ .

Thus our only solutions are $\boxed{(p,n) = (p,p); (2,4)}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

189 posts

vi1lat

#12 h Dec 16, 2014, 1:41 PM • 2 Y

Y by Adventure10, Mango247

What is the mean $ord$ ??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

151 posts

JackXD

#13 h Dec 17, 2015, 7:24 PM • 2 Y

Y by Adventure10, Mango247

Let $p$ be an odd prime.

Then $p^n+1|n^p+1 \implies p^{\frac{1}{p}} \le n^{\frac{1}{n}} \implies n \le p$ because $f(x)=x^{\frac{1}{x}}$ is decreasing function for $x \ge e$ .
It is easy to see that $n$ must be odd.Let $r$ be the order of $n$ modulo $p+1$ .Then $p^n+1|n^p+1 \implies p+1|n^{2p}-1 \implies r|2p$ .Clearly $r \le p$ and $r$ cannot be $p$ .Also $r=1 \implies p+1|n^p-1 \implies p+1|2$ which is absurd.So $r=2$ and $p+1|n+1$ which means $p \le n$ .This along with the first line's inequality yeilds $n=p$ .

For $p=2$ we have $2^n+1|n^2+1 \implies 2^n \le n^2 \implies n \le 4$ .Checking we get solutions $n=2,4$ .

Thus the solutions are $(p,n) \equiv (2,4),(p,p)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

321 posts

K.titu

#14 h Dec 17, 2016, 3:51 PM • 2 Y

Y by Adventure10, Mango247

Hi dear mathlinkers
I have a question
What made you to think about $p+1$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

uraharakisuke_hsgs

365 posts

uraharakisuke_hsgs

#16 h Nov 17, 2017, 5:45 PM • 2 Y

Y by Adventure10, Mango247

Fisrt , if $p > 2$ then $n$ is odd . Let $q$ is a prime number of $p+1$ . Then , $q | n^p+1 \implies q | n^{2p}-1$ , and $q| n^{q-1}-1$ , and because $q < p$ then $q | n^2 - 1$ , which implies $q | n+1$
And we have $v_q(p^n+1) = v_q (p+1) < v_q(n^p+1) = v_q(n+1) \implies p+1 | n+1 \implies p \leq n$
But we have $n^p > p^n \implies plog(n) \geq nlog(p) \implies \frac{log (n)}{n} \geq \frac{log (p) }{p}$
Let $f(x) = \frac{log x }{x}$ , then $f'(x) = \frac{1 - log x }{x^2}$ , then , for $x > 10$ , $f$ is decreasing . So , for $n , p > 10$ we have $n \leq p$
Then $n = p$
For the cases $n$ or $p < 10$ we can check that $(n,p) = (4,2)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

820 posts

#17 h Jul 27, 2019, 8:54 PM • 1 Y

Y by Adventure10

Obviously we need $n^p \equiv -1 \pmod{p^n+1} => n^{2p}=1 \pmod{p^n+1}$ .
Thus $O_{p^n +1}(n) \mid 2p$ , but it doesn’t divide $p$ - thus it must equal $2$ or $2p$ .
First let’s deal with the easier case, where order is $2$ . Here we can clearly see that as $n^2-1 \geq p^n+1$ , which is obviously false.
Now, what’s left is the case where $O_{p^n+1}(n)=2p$ .
In this case, we must again split into cases- before that, let’s consider some prime $q$ such that $v_q(p+1)=\alpha>0$ - here notice that as $n \equiv 1\pmod{2}$ for odd primes, $q^{\alpha} \mid p^{n}+1$ .
Clearly, we need $O_{q^\alpha}(n)= 2$ or $2p$ , by similar logic- if $2p$ , we get an immediate contradiction as $2p>p+1$ .
Now let’s look at the case when $O_{q^{\alpha}}(n)=2$ .
Now, as $(n+1)(n-1)= 0\pmod{q^{\alpha}}=> q^{\alpha} \mid n+1$ (almost forgot to consider $q=2$ separately, but in the end it doesn’t matter as $n$ is odd) for all such $q^{\alpha} \mid p+1$ . Hence, in a rather elegant manner, we get $p+1 \mid n+1$ , which of course kills the problem as $p \geq n => (p,p)$ is only solution for odd primes.

Now, you could manually check for $p=2$ and that’ll give you and extra solution $(2,4)$ , hence concluding the problem with the solution set $(p,p),(2,4)$ for all primes $p$ .

I felt this was actually quite a nice problem and a great fit for P3 (okay maybe a bit on the easier side, I suppose, but I’m not a very good judge), simply because if you don’t notice a few key points(at least if you solve it the way I did), the problem becomes hellish to solve- that makes me wonder, who proposed this?

This post has been edited 3 times. Last edited by ubermensch, Jul 27, 2019, 8:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1010 posts

mira74

#18 h Apr 6, 2020, 1:39 AM • 12 Y

Y by tworigami, anish9876, GameMaster402, CantonMathGuy, giacomorizzo, kevinmathz, Kagebaka, Toinfinity, p_square, niyu, khina, IAmTheHazard

Made with some people.
Assume $p=2$ , and deal with $p>2$ later.
Leaving $n \leq 4$ , we have $n^2+1 < 2^n+1$ , and there are no integers in $(0,1)$ .
Looking at $n \leq 4$ , we see $n=2 ,4$ work.
See that for $p$ odd, $p^n+1$ is even, so $n^p+1$ is even
Then, $n$ must be odd as well
Assume $n \neq p$ , since we can see that $n=p$ works.
Realize that $p+1 \mid p^n+1$ from $n$ odd, so $p+1 \mid n^p+1$
Note that since any prime $q \mid p+1$ is $<p$
Abusing order, this implies $q \mid n^p+1 \Rightarrow q \mid n+1$ .
Thus, $p+1 \mid n+1$ , so $n>p$ .
Inequalities kill the rest of the problem: we claim $n^p+1>p^n+1$ .
Observe that $f(x)=\ln(\sqrt[x]{x})$ has $f'(x)=\frac{1-\ln(x)}{x^2}$ , it decreases for $x>e$ , so $\sqrt[n]{n} \leq \sqrt[p]{p}$ , implying result.
Now, we are left with the final answer of $(2,4)$ and $(p,p)$ .
YUH $\blacksquare$

This post has been edited 3 times. Last edited by mira74, Apr 6, 2020, 1:41 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1671 posts

pad

#19 h May 23, 2020, 1:21 AM

Y by

Assume $p$ is odd; we will deal with $p=2$ later. Then $p^n+1$ is even, so $n^p+1$ is even, so $n$ is odd. Suppose $q\mid p+1$ for a prime $q$ . Then
$q\mid p+1 \implies q\mid p^n+1 \implies q\mid n^p+1\implies n^p\equiv -1 \pmod{q}, \ n^{2p} \equiv 1 \pmod{q}.$ Let the order of $n \pmod{q}$ be $x$ . Then $x\nmid p, x\mid 2p$ , so $x=2,2p$ . We also have $x\mid q-1$ ; hence if $x=2p$ then $2p \mid q-1$ , so $q \ge 2p$ , contradicting $q \mid p+1$ by size. Hence $x=2$ . So $n^2 \equiv 1\pmod{q}$ , which means $q\mid (n-1)(n+1)$ . We claim we actually have $q\mid n+1$ .

If $q\mid n+1$ , we have proved the claim.
If $q\mid n-1$ , then $q\mid n^p-1$ . But $q\mid p+1 \mid p^n+1 \mid n^p+1$ , so we also have $q\mid 2$ . So $q=2$ . But since $n$ is odd, $2\mid n+1$ , so this proves our claim.

Therefore, $q\mid p+1 \implies q\mid n+1$ . Now, we use LTE. Note that $q\mid p+1, n+1$ , so $q\nmid p,n$ . We have
$\begin{align*} \nu_q(n^p+1) &= \nu_q(n+1) + \nu_q(p) = \nu_q(n+1) \\ \nu_q(p^n+1) &= \nu_q(p+1) + \nu_q(n) = \nu_q(p+1). \end{align*}$ But $p^n+1\mid n^p+1$ , so therefore $\nu_q(n+1) \ge \nu_q(p+1)$ . Since $q$ was defined to be any prime divisor of $p+1$ , we conclude that $p+1\mid n+1$ .

In particular, $p\le n$ . Now, we use size. Since $p^n+1\mid n^p+1$ , we know $p^n \le n^p$ . So $n \ln p \le p \ln n$ , i.e. $\tfrac{n}{\ln n} \le \tfrac{p}{\ln p}$ . Let $f(x) = \tfrac{x}{\ln x}$ . It is not hard to show that $f(x)$ is increasing for $x\ge 3$ . But $x$ increased from $p$ to $n$ , while $f(x)$ decreased from $p$ to $n$ . Therefore, either $p<3$ or $n=p$ . If $p<3$ , then $p=2$ , and only $(p,n)=(2,2),(2,4)$ works here. Finally, the solutions are $(p,n)=(p,p),(2,4)$ .

Remarks

This post has been edited 3 times. Last edited by pad, May 23, 2020, 1:23 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#20 h May 15, 2021, 12:14 AM • 1 Y

Y by centslordm

The answer is $(2,4)$ and $(p,p)$ , where $p$ is prime, only. These can be easily checked. For $p=2$ , we can find that the only solutions are $n=2,4$ , since anything larger results in $p^n+1>n^p+1$ . Henceforth assume $p \geq 3$

Note that it is well-known that if $a>e>2$ and $b>a$ , then $a^b>b^a$ . Since we need $n^p+1 \geq p^n+1$ and $p \geq 3$ , it follows that $b \leq a$ . Now, since $p \geq 3$ , $p^n+1$ is even and hence $n^p+1$ is even too, so $n$ is odd. As such, any prime $q \mid p+1$ must divide $p^n+1$ . Let $Q=q^e \mid p+1$ , where $q$ is a prime, $Q \neq 2$ and $e=v_q(p+1)$ . Then we need $n^p \equiv -1 \pmod{Q}$ . This is enough to imply that $\operatorname{ord}_Q(n) \mid 2p$ . However, we also cannot have $\operatorname{ord}_Q(n) \mid p$ , else $n^p \equiv 1 \pmod{Q}$ . This narrows down the options to $\operatorname{ord}_Q(n)\in \{2,2p\}$ . However, the latter is impossible for size reasons as $Q \leq p+1$ , so $\operatorname{ord}_Q(n) \leq Q-1\leq p \leq 2p$ . Hence we conclude that $\operatorname{ord}_Q(n)=2$ for all prime powers $Q \neq 2$ dividing $p+1$ , implying $n \equiv -1 \pmod{Q}$ . This also works if $Q=2$ , in which case $n \equiv 1 \equiv -1 \pmod{Q}$ . Hence by CRT, we have $n \equiv -1 \pmod{p+1}$ . But we also have $b \leq a$ , so $n=p$ . Thus no other solutions exist. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

478 posts

#22 h Oct 26, 2021, 4:49 AM

Y by

syk0526 wrote:

Determine all the pairs $(p , n )$ of a prime number $p$ and a positive integer $n$ for which $\frac{ n^p + 1 }{p^n + 1}$ is an integer.

Assume that $n \neq p$ since when $n=p$ we obtain $(n,p)=(p,p)$ which works.
Henceforth assume that $p \ge n$ and $p \ge 2$ i.e when $p=2$ we obtain $(n,p)=(2,4)$ which works.
Clearly $n$ is odd let $\tilde{p}$ be a prime dividing $p+1$
Notice that $\nu_{\tilde{p}}(p^n+1)=\nu_{\tilde{p}} (p+1)+\nu_{\tilde{p}} (n)$ i.e $\tilde{p}|n^p+1 \implies ord_{\tilde{p}}(n)=\{1,2,2p\}$ The first and last cases are impossible hence $n^2+1 \equiv 0 \pmod {\tilde{p}}$ implying
$p+1 \equiv 1 \pmod 4 \implies 4|p$ ,contradiction so $(n,p)=(4,2),(p,p)$

This post has been edited 1 time. Last edited by Sprites, Oct 26, 2021, 6:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

548 posts

#23 h Feb 4, 2022, 4:34 PM

Y by

Lemma:if $a$ and $b$ positive integer numbers and $a \leq b \implies b^a \leq a^b$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

121 posts

mijail

#24 h Feb 7, 2022, 5:01 PM

Y by

Funny problem!

Suppose that $p \neq 2$ because if we have $p=2$ then $n^2+1 \ge 2^n +1 \implies n \leq 4$ so we have the solutions: $(p,n): (2,2); (2,4)$

Claim: $p+1 \mid n+1$
Proof: First we have that $p^n+1$ is even so $n$ is odd then $p+1 \mid p^n+1\mid n^p+1$ so $p+1 \mid n^{2p} -1 \implies p+1 \mid n^{(2p,\phi(p+1))}-1$ but $\phi(p+1) \leq p-1$ so $(\phi(p+1),p)=1 \implies (2p,\phi(p+1)) \mid 2 \implies p+1 \mid n^2 -1 \implies p+1 \mid n+1$ . (Because $p$ is odd) $\square$

Let $n=pu$ .Then we have that $p^n +1 \leq n^p +1 \implies p^pu \leq (pu)^p \implies p^{u-1} \leq u$ but if $u \ge 2$ we have that: $\lfloor u \rfloor +1 > u \ge p^{u-1} \ge 3^{u-1} \ge 3^{\lfloor u \rfloor-1} \implies \lfloor u \rfloor +1 \ > 3^{\lfloor u \rfloor-1}$ This is false if $u \ge 2$ so we have $n <2p$ and $p+1 \mid n+1$ so $p=n$ . This concludes the problem. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

439 posts

#25 h Feb 28, 2022, 6:32 PM

Y by

I really enjoyed from this problem.
If $p=2$ , we easily get $n=2$ or $n=4$ . If $n=1$ , we get there is no solution. If $n=2$ we get $p=2$ . Now assume $p,n>2$ . Since $p^n\leq n^p$ and $p,n>e$ , we get $p\geq n$ . $n=p$ is obviously solution. Now assume $p>n$ . Since $p$ is odd, we get $n$ is odd also. So $p+1\mid n^p+1$ . Consider odd prime divisor $q$ of $p+1$ . Since $p>q-1$ , we get $\gcd(2p,q-1)=2$ . Since $n^{q-1}\equiv n^{2p}\equiv 1 \pmod{q}$ , and $\gcd(2p,q-1)=2$ , we get $n^2\equiv 1 \pmod{q}$ . So $n^p+1\equiv (n^2)^{\frac{p-1}{2}} \cdot n+1\equiv n+1\equiv 0 \pmod{q}$ . So $q\mid n+1$ . Also we have $v_q({p^n+1})=v_q({p+1})+v_q({n})=v_q({p+1})\leq v_q({n^p+1})=v_q({n+1})+v_q({p})=v_q({n+1})$ . So if $q$ is odd prime divisor of $p+1$ , then $v_q({p+1})\leq v_q({n+1})$ . Now let's deal with $v_2$ . Since $v_2({p+1})\leq v_2({n^p+1})=v_2({n+1})$ , we get $v_2({p+1})\leq v_2({n+1})$ . So $v_r({p+1})\leq v_r({n+1})$ for all prime number $r$ . So we get $p\leq n$ , which is contradiciton. So all solutions are $\boxed{n=p}$ , $\boxed{p=2,n=4}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

67 posts

ZNatox

#26 h Jan 5, 2023, 6:39 PM

Y by

If $p=2$ , we get $n=2,4$ .
Now suppose $p>2$ , then $n$ is odd, and we can't have $n=1$ , thus: $n \le p$ .
$p+1 \mid p^n+1 \mid n^p+1 \mid n^{2p}-1$ which implies $O_{p+1}(n) \mid 2p$ . If $O_{p+1}(n)$ is odd we get $O_{p+1}(n) \mid p$ clearly impossible. Thus: $O_{p+1}(n) \in \{2,2p\}$ . Can we have: $O_{p+1}(n)=2p$ ? No, the reason being: $\phi(p+1)\le (p+1)<2p$ . Thus: $O_{p+1}(n)=2$ which gives us that: $p+1 \mid (n-1)(n+1)$ or $\frac{p+1}{2^{v_2(p+1)}} \mid (n-1) × \frac{n+1}{2^{v_2(p+1)}}$ , but $\frac{p+1}{2^{v_2(p+1)}}$ is odd, and therefore coprime with $n-1$ , and by LTE $\frac{n+1}{2^{v_2(p+1)}}$ is an integer, thus $p+1 \mid n+1$ , which gives us $p=n$ .

This post has been edited 6 times. Last edited by ZNatox, Jan 5, 2023, 6:46 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

104 posts

#28 h Aug 17, 2023, 4:08 PM

Y by

Interesting. Suppose that $n$ and $p$ are not equal and $p>2$ :
We know that $n^p$ > $p^n$ , since $n,p>e$ ( $n=2$ case is impossible because $n$ must be odd according to mod 2 and $n=1$ is easy) we have $p>n$ (It is well known that for $a,b>e$ , if $a^b>b^a$ , then $b>a$ ). We have $2 \mid p^n+1\mid n^p+1$ , then $n$ is odd, then $p+1 \mid p^n+1 \mid n^p+1$ . Let $\operatorname{ord}_{p+1}(n)=k$ , since $n^{2p} \equiv 1 \pmod{p+1}$ , we know that $k \mid 2p$ , we know that $k<2p$ , and $k$ is not equal to $p$ (because $n^p \equiv -1 \pmod{p+1}$ ), which means that $k \mid 2$ , then $n^p+1 \equiv n+1 \pmod{p+1}$ , since $p+1 \mid n^p+1$ , we have $n \equiv p \pmod{p+1}$ , which is contradicting $p>n$ , then $p$ must be equal to $n$ for $p,n>3$ . For $p=2$ we have $2^n+1>n^2+1$ for $n>4$ , you can check the cases $n=1,2,3,4$ , which gives the solutions $(2,4)$ and $(2,2)$ . Then answers are $(p,p)$ and $(2,4)$ where $p$ is an any prime number.

This post has been edited 4 times. Last edited by X.Allaberdiyev, Aug 17, 2023, 4:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1455 posts

#29 h Mar 4, 2024, 5:20 AM

Y by

I claim the answers are $n = p$ for all $p$ and $n = 4, p = 2$ .

First, it is well known that $a^b > b^a$ when $a < b$ and both $a, b \geq 3$ (the result follows form taking a log of both sides and a derivative to show strict monotonicity).

In the case when $p = 2$ , by bounding we have $n \leq 4$ and here only $n = 4$ works. In the case $n = 1$ , the value is less than $1$ , and in the case $n = 2$ , there is death by parity for $p \geq 3$ . Otherwise, we have $n \geq 3$ and thus $n \leq p$ . Obviously $n = p$ works.

Now notice that since $p^n + 1$ is even, we must have $n$ odd, so it follows $n^p \equiv -1 \pmod{p + 1}$ . In particular, since $p+1$ is composite and thus $p \nmid \phi(p+1)$ , it follows that there is a unique solution to $n^p \equiv -1 \pmod{p+1}$ up to $p + 1$ . Since $n = p$ suffices, this must be the only solution, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4188 posts

#30 h Mar 5, 2024, 6:24 PM

Y by

The answer is $n=p$ and $p=2,n=4$ only.

For $p=2$ , we have $2^n+1\mid n^2+1$ , which only has $n=2$ and $n=4$ as a solution since $2^n>n^2$ for all $n\geq 5$ . $n=1$ gives $p+1\mid 2$ which clearly does not work, and $n=2$ gives $p^2+1\mid 2^p+1$ which can only work for $p=2$ since $2^p+1$ is odd.

Thus, assume $n,p\geq 3$ from now on. This means that for $n^p$ and $p^n$ , the one with the higher exponent is larger, which means that we must have $n\leq p$ .

If $n$ is even, we must have $p=2$ since the numerator is odd, but we have already shown that the only solution for $p=2$ is $n=2$ and $n=4$ . From now on, assume $n$ odd, so $p+1\mid p^n+1$ . Thus, $p+1\mid n^p+1$ $n^p\equiv -1\pmod{p+1}$ $n^{2p}\equiv 1\pmod{p+1}.$ Thus the order of $n$ mod $p+1$ must divide $2p$ but not $p$ , which means it is either $2$ or $2p$ . However, it cannot be $2p$ since that is larger than the modulus of $p+1$ , hence the order is $2$ so $n\equiv -1\pmod{p+1}$ . Since $n\leq p$ , the only solution is $n=p$ in this case.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

16 posts

#31 h Mar 5, 2024, 9:19 PM

Y by

Only $n = p, (2,4)$ satisfy the condition.
For $p=2, p=3$ we can just check until the denominator gets bigger than the numerator.
So we can assume $p$ is odd and if $n > p \iff p^n > n^p$ so $n \le p$ It is clear that if we
let $\frac{n^p + 1}{p^n + 1} = k$ for some positive integer we have for $p > 2$ $k=1$ if and only if $n = p$ so we can assume $n < p$
$n^p + 1 - k = p^nk \Rightarrow n \equiv k-1 \pmod p \Rightarrow n = k-1$ $(k-1)^p + 1 - k = p^nk \Rightarrow p = k-1$ so $n = p$ and there are no solutions for $k > 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

38 posts

#32 h Mar 11, 2024, 12:59 AM

Y by

Solution pairs $(n,p)$ , are $(p,p)$ for all primes, and $(4,2)$ . Check $p=2$ manually, and by size, assume that $n<p$ , as $n=p$ obviously works. Now assume for sake of contradiction some other $n$ works for an odd prime $p$ .

By orders, if a prime $q \mid n^p + 1$ , either $q \equiv 1 \pmod p$ or $q\mid n+1$ . By parity, $n=p-1$ dies so consider $n<p-1$ : this means $n+1 < p$ . By LTE, any prime dividing $n+1$ cannot divide $\frac{n^p+1}{n+1}$ , but $n^p+1 \equiv n+1 \pmod p$ , which means the primes dividing $n^p+1$ that aren't $1 \pmod p$ , are exclusively those dividing $n+1$ : their product is thus less than $p$ . However, as $2 \mid p^n+1$ , then there exists some primes that aren't $1 \pmod p$ that have product greater than $1$ which is a contradiction.

I read the other solutions and noticed that I could have just considered $p+1$ instead.

This post has been edited 2 times. Last edited by mathfun07, Mar 26, 2024, 11:04 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

alexanderhamilton124

397 posts

alexanderhamilton124

#33 h Oct 5, 2024, 9:32 AM • 3 Y

Y by ubermensch, L13832, Nobitasolvesproblems1979

For $p = 2$ : We have $2^n > n^2$ for $n \geq 5$ , which means we have to check $n = 1, 2, 3, 4$ which gives $(4, 2)$ as a solution, and $(2, 2)$ .

From now on, assume $p$ odd. Clearly, $p^n + 1$ is even, which means $n$ has to be odd. Consider a prime $q$ such that $q \mid p + 1$ . Since $p + 1 \mid p^n + 1$ , $q \mid n^p + 1 \implies n^p \equiv -1 \mod{q} \implies n^{2p} \equiv 1\mod{q}$ . So, $\text{ord}_q(n) \mid 2p$ , and it can't be $1$ or $p$ since $\text{ord}_q(n) \nmid p$ , and it can't be $2p$ , since $2p > p + 1 > q - 1$ . So, $\text{ord}_q(n) = 2$ , and $n \equiv -1 \mod{q}$ .

By LTE, we have $v_q(p^n + 1) = v_q(p + 1) + v_q(n)$ , and since $q \mid n + 1$ , $q \nmid n$ , and $v_q(p^n + 1) = v_q(p + 1)$ . We have $v_q(n^p + 1) = v_q(n + 1)$ , so $v_q(n + 1) \geq v_q(p + 1) \implies p + 1 \mid n + 1$ , so $p \leq n$ . For $n > p$ , however, $p^n > n^p$ , a contradiction, which means $n = p$ is the only solution here, and we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

71 posts

EVKV

#34 h Apr 23, 2025, 6:21 PM • 1 Y

Y by Nobitasolvesproblems1979

CASE 1: n=pk+r where $k \geq 4$ and $0 \leq r$ < $p$

Claim 1.1 : $p^n$ > $n^p$

Proof 1.1 : This is equivalent to proving $p^{\frac{n}{p}}$ > $n$ => $p^{k}$ > $pk+r$
=> $p^{k}$ > $p(k+1)$ => $p^{k-1}$ > $(k+1)$ which is clearly true for all primes as $k \geq 4$

CASE 2: n=p+r where $0 \leq r$ < $p$ $p \neq 2$

Claim 2.1 : Only n=p satisfies this

Proof 2.1 : $p+1 | (p+r)^{p} +1$ so, $(p+r)^{2p} \equiv 1$ mod $p+1$
Now the order of $p+r$ mod $p+1$ $\in$ { $2,2p$ }
however 2p>p+1 ,thus order is 2
So, $p+r \equiv -1$ mod $p+1$ $p+r \equiv -1 + r \equiv -1$ mod $p+1$
$r \equiv 0$ mod $p+1$ thus r=0

Thus n=p

CASE 3: n=p-r where $0 \leq r$ < $p$ $p \neq 2$

Claim 3.1 : Only n=p satisfies this

Proof 3.1 : $p+1 | (p-r)^{p} +1$ so, $(p-r)^{2p} \equiv 1$ mod $p+1$
Now the order of $p-r$ mod $p+1$ $\in$ { $2,2p$ }
however 2p>p+1 ,thus order is 2
So, $p-r \equiv -1$ mod $p+1$ $p-r \equiv -1 + r \equiv -1$ mod $p+1$
$-r \equiv 0$ mod $p+1$ thus r=0

Thus n=p

CASE 4: n=2p+r where $0 \leq r$ < $p$ $p \neq 2$

Claim 4.1 : This has no solution

Proof 4.1 : $p+1 | (2p+r)^{p} +1$ so, $(2p+r)^{2p} \equiv 1$ mod $p+1$
Now the order of $2p+r$ mod $p+1$ $\in$ { $2,2p$ }
however 2p>p+1 ,thus order is 2
So, $2p+r \equiv -1$ mod $p+1$ $2p+r \equiv -2 + r \equiv -1$ mod $p+1$
$r \equiv 1$ mod $p+1$ thus r=1

Claim 4.1.1 : $p^{2p+1}$ > $(2p+1)^p$

Proof 4.1.1 : This is equivalent to proving $p^{\frac{2p+1}{p}}$ > $2p+1$
=> $p^{2}$ > $2p+1$ which is clearly true for all primes as $p \geq 3$

Thus No solution

CASE 5: n=3p+r where $0 \leq r$ < $p$ $p\neq2$

Claim 5.1 : This has no solution

Proof 5.1 : $p+1 | (3p+r)^{p} +1$ so, $(3p+r)^{2p} \equiv 1$ mod $p+1$
Now the order of $3p+r$ mod $p+1$ $\in$ { $2,2p$ }
however 2p>p+1 ,thus order is 2
So, $3p+r \equiv -1$ mod $p+1$ $3p+r \equiv -3 + r \equiv -1$ mod $p+1$
$r \equiv 2$ mod $p+1$ thus r=2

Claim 5.1.1 : $p^{3p+2}$ > $(3p+2)^p$

Proof 5.1.1 : This is equivalent to proving $p^{\frac{3p+2}{p}}$ > $3p+2$
=> $p^{3}$ > $3p+2$ which is clearly true for all primes as $p \geq 3$

Thus No solution

CASE 6: p=2 n=2k+r

Claim 6.1 : (n,p)=(2,2) , (4,2) satisfy it

Proof 6.1 : By Case 1 $k \leq 3$ which then bashing with both r=1,0 we get only 2,2 and 4,2 satisfy the problem

Done

Remark: Grt problem on bounding and simple orders

I rate it 10 mohs

Solved: 17/4/25

This post has been edited 3 times. Last edited by EVKV, Apr 23, 2025, 6:35 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a