First of all, if $p=2$, then $x$ is $1$ or $2$. Assume now $p\ge 3$. Clearly, $x$ must be odd (let's say that $x=2k+1$), and let's assume $x>1$. Let $q$ be the smallest prime divisor of $x$. We have $q|((p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1=p(p-2)$. Assume $q\ne p$. We find that $q|p-2$. At the same time, we have $q|(p-1)^x+1=(p-1)^{2k+1}+1=[(p-1)^{2k}-1](p-1)+p$, so $q|p$, which contradicts the fact that $q|p-2$ and $q$ is odd. This means that $q=p$, so $x\in\{p,2p\}$, and since it's odd, we have $x=p$. We now have to find those odd primes $p$ s.t. $p^{p-1}|(p-1)^p+1$. After expanding the binomial on the right, we find that the expression on the right is $p^2+kp^3$, so $p-1\le 2$, meaning that the only odd prime satisfying this is $p=3$ (it it does satisfy the relation, since $3^2|2^3+1$). The solutions are then $(1,p)$ for any prime $p$, $(2,2)$ and $(3,3)$.

OFFICIAL SOLUTION Clearly we have the solutions $(1,p)$ and $(2,2)$, and for every other solution $p \geq 3$. It remains to find the solutions $(x,p)$ with $x \geq 2$ and $p \geq 3$. We claim that in this case $x$ is divisible by p and $x y 2p$, whence $x = p$. This will lead to $$p^{p-1}|(p-1)^{p}+1=p^{2}\left(p^{p-2}-{p \choose 1}p^{p-3}+ \cdots + -{p \choose p-3}p-{p \choose p-2}+1\right)$$ therefore, because all the terms in the brackets excepting the last one is divisible by $p$,$p-1 \leq 2$. This leaves only $p=3$ and $x=3$. Let us prove now the claim. Since $(p-1)^{x}+1$ is odd, so is $x$ (therefore $x < 2p$). Denote by q the smallest prime divisor of $x$. $q|(p-1)^{x}+1$ we get $(p-1)^{x} \equiv -1 \pmod {q}$ and $(q,p-q)=1$. But $(x,p-q)=1$ (from the choice of q) leads to the existence of integers $u,v$ such that $ux+v(q-1)=1$, whence $p-1 \equiv (p-1)^{ux}$. $(p-1)^{v(q-1)} \equiv (-1)^{u} \cdot 1^{v} \equiv -1 \pmod {q}$, because $u$ must be odd. This shows that $q|p$, therefore $q=p$. In conclusion the required solutions are $(2,2), (3,3)$ and $(1,p)$, where $p$ is an arbitrary prime.

@all : can you please explain $q|[(p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1$ Sincerely Davron

grobber wrote: At the same time, we have $q|(p-1)^{x}+1=(p-1)^{2k+1}+1=[(p-1)^{2k}-1](p-1)+p$, so $q|p$, which contradicts the fact that $q|p-2$ and $q$ is odd. i dont get this why does q divide p. please someone explain.

orl wrote: Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p - 1}$ is a divisor of $(p - 1)^{x} + 1$. First the case where $p=2$: $x \mid 2$. So there are solutions $(p,x) = (2,1)$ and $(p,x) = (2,2)$. Then the case where $x=1$. (I will use that $x$ has prime divisors later) $1^{p-1} \mid (p-1)^1 + 1 \iff 1 \mid p$ always holds. So $(1,p)$ are also solutions. $x^{p-1} \mid (p-1)^x + 1 \mid (p-1)^{2x} - 1$. Let $q$ be the smallest primedivisor of $x$. Then $(p-1)^{2x} \equiv 1 \bmod q \Rightarrow (p-1)^{(2x,q-1)} \equiv 1 \bmod q$. But $(2x,q-1) \le 2(x,q-1) = 2$. So $q \mid (p-1)^2-1 = p(p-2)$. If $q \mid p$ then $q=p$. Since $x$ is odd and $x \leq 2p$ we see that $x=p > 2$. Then $p^{p-1} \mid (p-1)^p + 1 = (p-1)^p - (-1)^p$ It is well known that $v_p(a^n-b^n) = v_p(n) + v_p(a-b)$ when $a \equiv b \bmod p$ and $(ab,p)=1$. Hence $v_p( (p-1)^p - (-1)^p ) = v_p(p) + v_p(p-1-(-1))=2$. Hence $p-1 \le 2$. And then $p=3$ gives the solution $(x,p)=(3,3)$. Now assume that $q \mid p-2$. Then $q^{p-1} \mid (p-1)^{2x} - 1^{2x}$. So $v_q( (p-q)^{2x} - 1^{2x} ) = v_q(p-2) + v_q(2x) \ge p-1$. But since $q$ is odd: $v_q(2x) = v_q(x)$. And $q \ge 3$. Hence $v_q(n) \le log_3(n)$ when $n \in \mathbb{N}$. So: $log_3(p-2) + log_3(x) \ge p-1$. $x \le 2p$: $log_3(p-2) + log_3(2p) \ge p-1 \iff 2p^2-4p \ge 3^{p-1}$ Let $f(p) = 3^{p} - 2(p+1)^2+4(p+1) = 3^p - 2p^2+2$. Then $f(p-1) \le 0$. $f'(p) = \ln (3) \cdot 3^p -4p$ and $f''(p) = \ln^2(3) \cdot 3^p > 0$ But $f'(2) = \ln (3) \cdot 3^2 - 4 \cdot 2 > 3^2 - 4 \cdot 2 = 1 > 0$. Since $f''(p) > 0$ we see that $f(p)$ is increasing when $p \ge 2$. But $f(2) = 3^2-2\cdot2^2+2 = 3 > 0$ Hence: When $p \ge 3$ we see that $f(p) > 0$. So $q \mid p-2$ doesn't give any solutions. QED

Setting $n=1$ we get the solutions $(1,p)$ with $p$ prime. For $p\in\{2,3\}$ we find that $(2,2)$ and $(3,3)$ are solutions too. Now let $n>1$ and $p>3$, then $n$ has to be odd. Case 1. $n$ is a prime power, so write $n=q^\alpha$. Then we get $(p-1)^{q^\alpha}\equiv -1 \mod q \Leftrightarrow p\equiv 0 \mod q \Leftrightarrow p=q$, implying that $\alpha=1$. Now $(p-1)^p+1=\sum_{i=0}^p \binom{p}{i} p^i (-1)^{p-i}+1\equiv \sum_{i=3}^{p-2} \binom{p}{i}p^i (-1)^{p-i} - \frac{p-1}{2} p^3+p^2 \equiv 0 \mod p^{p-1}$ and as the LHS is divisible by $p^2$ but not by $p^3$, the congruence cannot hold, so there are no solutions. Case 2. $n$ has at least two distinct prime factors. Let $q$ be the smallest prime divisor of $n$, then $n=a\cdot q^\alpha$ with $\gcd(q,a)=1$ and $a\ge 3$, so $3q^\alpha<2p$. Now we have $(p-1)^{aq^\alpha}\equiv -1 \mod q^{\alpha(p-1)}$. Squaring, we get $(p-1)^{2aq^\alpha}\equiv 1 \mod q^{\alpha(p-1)}$. As $ord_{q^{\alpha(p-1)}}(p-1)|\gcd\left(2aq^\alpha,\varphi\left(q^{\alpha(p-1)}\right)\right)=\gcd\left(2aq^\alpha,(q-1)q^{\alpha(p-1)-1}\right)=2q^\alpha$ we also have $(p-1)^{2q^\alpha}\equiv 1 \mod q^{\alpha(p-1)}\Leftrightarrow\left((p-1)^{q^\alpha}-1\right)\left((p-1)^{q^\alpha}+1\right)\equiv 0 \mod q^{\alpha(p-1)}$. As $gcd\left((p-1)^{q^\alpha}-1,(p-1)^{q^\alpha}+1\right)=1$ we get $(p-1)^{q^\alpha}\equiv \pm 1 \mod q^{\alpha(p-1)}$. If $(p-1)^{q^\alpha}\equiv 1 \mod q^{\alpha(p-1)}$ it follows that $(p-1)^{aq^\alpha}\equiv 1 \equiv -1 \mod q^{\alpha(p-1)}$, a contradiction. But now $q^{\alpha(p-1)}|(p-1)^{q^\alpha}+1$. We know from Catalan's conjecture that equality cannot hold here, further $(q^\alpha)^{p-1}>(p-1)^{q^\alpha}\Leftrightarrow\frac{\ln(q^\alpha)}{q^\alpha}>\frac{\ln(p-1)}{p-1}$ which is clearly true, as $f'(x)= \left(\frac{\ln(x)}{x}\right)'=\frac{1-\ln(x)}{x^2}$, so $f(x)$ is strictly decreasing for $x>e$. We conclude that there are no more solutions. Hence, $(1,p),(2,2),(3,3)$ are the only solutions. $\square$

Here is my solution(not exactly written up in the most organized way):

Once the cases $x=1$ and $p\mid x$ have been dealt with using, for example, LTE (giving solutions of $\left(1,p\right),\left(2,2\right)$ and $\left(3,3\right)$) and it has been noted that $x$ is otherwise odd, another way to finish it off is to use orders: $x^{p-1}\mid\left(p-1\right)^{x}+1\mid\left(p-1\right)^{2x}-1$. Thus if $q$ is the smallest a prime divisor of $x$ (the case $x=1$ has already been dealt with) then we have that $q\mid\left(p-1\right)^{x}+1\Rightarrow q\nmid\left(p-1\right)^{x}-1$ ($x$ is odd means $q\neq2$) and $q\mid\left(p-1\right)^{2x}-1$. Thus $\text{ord}_{q}\left(p-1\right)\nmid x$ and $\text{ord}_{q}\left(p-1\right)\mid2x$ hence, as $x$ is odd, $\text{ord}_{q}\left(p-1\right)$ is twice a factor of $x$ so $\frac{\text{ord}_{q}\left(p-1\right)}{2}$ is a factor of $x$ so is either $1$ or at least $q$. Now by FLT: $\frac{\text{ord}_{q}\left(p-1\right)}{2}\mid\text{ord}_{q}\left(p-1\right)\mid q-1$ so $\frac{\text{ord}_{q}\left(p-1\right)}{2}\leq q-1\Rightarrow\frac{\text{ord}_{q}\left(p-1\right)}{2}=1\Rightarrow\text{ord}_{q}\left(p-1\right)=2$. Now $\text{ord}_{q}\left(p-1\right)=2\Rightarrow\left(p-1\right)^{2}\equiv1\mod{q}\Rightarrow\left(p-1\right)^{x-1}\equiv1\mod{q}$ ($x$ is odd means $x-1$ is even). Thus $\left(p-1\right)^{x}\equiv p-1\mod{q}\Rightarrow\left(p-1\right)^{x}+1\equiv p\mod{q}$. But $q\mid\left(p-1\right)^{x}+1$ so $q\mid p\Rightarrow q=p\Rightarrow p\mid x$ which is a case that has already been dealt with.

frill,your solution is really nice.....I like it.... BTW I don,t know why no one thought of using orders earlier....

Davron wrote: @all : can you please explain $q|[(p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1$ Sincerely Davron $q|(p-1)^{2x}-1$ because $(p-1)^{2x}-1=((p-1)^x+1)((p-1)^x-1)$ and $q|(p-1)^{q-1}-1$ from fermat's little theorem,so $q$ will divide GCD of them

First, note that if $x = 1$, then the desired relation trivially holds for all $p.$ Hence, the pair $(1, p)$ is valid for all primes $p.$ Now, let us consider the cases of $x = p$ and $p = 2, 3.$ If $x = p \ne 2, 3$, then we must have $p^{p - 1} \mid (p - 1)^p + 1.$ But note that $p \mid (p - 1) + 1$, so we may apply LTE to find that $v_p\left((p - 1)^p + 1^p\right) = v_p(p) + v_p(p) = 2.$ It follows that $p - 1 \ge 2$, which is impossible from the assumption that $p \ne 2, 3.$ If $p = 3$, we are searching for $x \in \{1, 2, 3, 4, 5, 6\}$ such that $x^2 \mid 2^x + 1.$ By testing these six possibilities, we find the solutions $(1, 3), (3, 3).$ If $p = 2$, we are searching for $x \in \{1, 2, 3, 4\}$ such that $x \mid 2.$ Thus we obtain the solutions $(1, 2), (2, 2).$ Furthermore, note that if $x$ is even, then $x^{p - 1} \mid (p - 1)^x + 1 \implies p - 1$ is odd, and so $p = 2$, which is a case that was already covered. Henceforward, we may assume that $x$ is odd. Now, suppose that $x > 1$, and let $q \ne 2, p$ be the least prime divisor of $x.$ Then we have the relation $$(p - 1)^x \equiv -1 \pmod{q^{p - 1}} \implies (p - 1)^x \equiv -1 \pmod{q} \implies (p - 1)^{2x} \equiv 1 \pmod{q}.$$ Hence, if we let $d = \text{ord}_q(2)$, it is well-known that $d \mid 2x.$ Furthermore, since $p - 1$ and $q$ are clearly relatively prime, we derive that $$(p - 1)^{q - 1} \equiv 1 \pmod{q} \implies d \mid q - 1 \implies d \le q - 1.$$ Now, note that if $d \ne 2$, then there is some prime divisor of $d$ that is also a divisor of $x.$ However, this is impossible, because said divisor would have to be less than $q$ (because $d \le q - 1$), and we assumed that $q$ was the least prime divisor of $x.$ Therefore, we conclude that $d = 2.$ It follows that $$(p - 1)^2 \equiv 1 \pmod{q} \implies p(p - 2) \equiv 0 \pmod{q} \implies p - 2 \equiv 0 \pmod{q},$$ because we assumed that $q \ne p.$ It follows that $(p - 1)^x + 1 \equiv 1^x + 1 \equiv 2 \pmod{q}.$ However, this contradicts $(p - 1)^x + 1 \equiv 0 \pmod{q}$, so we conclude that there are no such solutions. In summary, the desired pairs are $(2, 2), (3, 3)$, and $(1, p)$ for any prime $p.$

1999 ISL NT 1 wrote: Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p-1}$ is a divisor of $(p-1)^{x}+1$. If $x=p$ then we have $p^{p-1} \mid (p-1)^p+1$. Since $p \mid (p-1)+1$, by LTE we know that $v_p((p-1)^p+1) = v_p((p-1)+1)+v_p(p) = 2$. Therefore, $p-1 \le 2 \implies p=2,3$. These yield the valid pairs $\boxed{(2,2), (3,3)}$. If $x=1$ then all pairs in the form $\boxed{(1,p)}$ where $p$ is a prime work. Now assume $p >2, x>1$ and $p \neq x$. We have $x^{p-1} \mid (p-1)^x+1 \mid (p-1)^{2x}-1$. Notice that $x$ must be odd because $(p-1)^x+1$ is odd ($p >2$). Therefore, $\gcd(x^{p-1}, (p-1)^x-1)=1$ because $x^{p-1} \mid (p-1)^x+1$ and the smallest prime that divides $x^{p-1}$ is greater than $2$. Then if $q$ is the smallest prime factor of $x$, we know that $\text{ord}_q(p-1) \mid 2x$ and $\text{ord}_q(p-1) \nmid x$. Since $x$ is odd, we know that $\text{ord}_q(p-1) \ge 2q$ or $\text{ord}_q(p-1)=2$. However, since $\phi(q) = q-1$, we know that $\text{ord}_q(p-1) \mid q-1$ so we must have $\text{ord}_q(p-1)=2$. Hence, $(p-1)^2 \equiv 1 \pmod{q}$. Then $(p-1)^x+1 \equiv 0 \pmod{q} \implies p \equiv 0 \pmod{q}$. Since $p$ is prime, $p=q$ so $p$ must also equal $x$ since $x \le 2p$, which goes against our assumptions. Therefore, we are done. $\blacksquare$

Hey, noob here. A bit off-topic question, but is there something wrong with this statement below? (Not that it's useful) This is for cases $x > 1, p > 2$. $x^{p - 1} \mid \left(p - 1\right)^x + 1 \Rightarrow \nu_p(x^{p - 1}) \leq \nu_p(\left(p - 1\right)^x + 1^x) = \nu_p(p) +\nu_p(x) = 1 + \nu_p(x) \Rightarrow \left(p - 2 \right)\nu_p(x) \leq 1$

My solution: If $p=2$, then $x \mid 2 \Rightarrow x=1,2$. So from now on assume that $p$ is odd. Now, $x^{p - 1} \mid \left(p - 1\right)^x + 1 \Rightarrow (p-1) \cdot \nu_p(x) = \nu_p(x^{p - 1}) \leq \nu_p(\left(p - 1\right)^x + 1) = \nu_p(p) +\nu_p(x) = 1 + \nu_p(x) \Rightarrow \left(p - 2 \right)\nu_p(x) \leq 1$. CASE-1 ($\nu_p(x) \geq 1$): $p-2 \leq 1 \Rightarrow p \leq 3 \Rightarrow p=3$. And, $p \mid x \Rightarrow 3 \mid x$ and $x \leq 2p = 6$ $\Rightarrow x=3$ or $6$. But $x^2 \mid 2^x+1 \Rightarrow x=3$ CASE-2 ($\nu_p(x)=0$): Notice that $x=1$ works for all $p$, so from now on assume that $x \not= 1$. Let $m$ be a prime divisor of $x$. Note that as $p \nmid x$, so $p \not= m$. Then, $(p-1)^x+1 \equiv 0 \pmod{m} \Rightarrow (p-1)^{2x} \equiv 1 \pmod{m}$ Thus, $ord_m(p-1) \mid 2x$. Also $ord_m(p-1) \mid \phi(m) \Rightarrow ord_m(p-1) \mid m-1$. Also as $ord_m(p-1) \leq m-1$, so $ord_m(p-1) \mid gcd(m-1,2x)$. But as $m \mid x \Rightarrow m-1 \nmid x$. SUBCASE-1 ($m \not= 3$): $m-1 \nmid 2 \Rightarrow gcd(m-1,2x)=1 \Rightarrow ord_m(p-1) = 1 \Rightarrow p \equiv 1 \pmod{m}$ $\Rightarrow (p-1)^x+1 \equiv 1 \equiv 0 \pmod{m} \longrightarrow CONTRADICTION$. SUBCASE-2 ($m=3$): $m-1 \mid 2 \Rightarrow gcd(m-1,2x) =2 \Rightarrow ord_m(p-1)=1 \text{or} 2$. By a similar argument as in subcase-1, $ord_m(p-1) \not= 1 \Rightarrow ord_m(p-1) = 2 \Rightarrow (p-1)^2 \equiv 1 \pmod{m}$ $\Rightarrow p(p-2) \equiv 0 \pmod{m} \Rightarrow p-2 \equiv 0 \pmod{m} \Rightarrow (p-1)^x+1 \equiv 2 \equiv 0 \pmod{m} \longrightarrow CONTRADICTION$. Thus, The only solutions are $(x,p)=(1,p),(2,2),(3,3)$.

Okayish question, a little hard for a $P4$, but nothing that can't be destroyed by a little bit of LTE and a heavy dose of orders- here's the sketch of my solution. First let's take the case for odd primes- we immediately see that $n$ can't be even, thus we can directly use LTE for the case when $n$ is divisible by $p$ (hence $n=p$). We get $v_p((p-1)^n+1)=2$, thus $p-1=2=>p=3 => (3,3)$ is the only solution of the form $(p,p)$ for odd primes.

(as $q$ is smallest prime dividing $n$ and is not $2$). Also, as $O_q(p-1)$ doesn't divide $gcd(n,q-1)=1 => O_q(p-1)=2 => (p-1) \equiv -1 \pmod{q} => q \mid p$. As we've separately considered the case $n=p$, we get no solution from this case (as $q>1$ for $n>1$). Now all we've left is special cases- $n=1,p=2,p=3$- solving for these gives us the complete solution set $(p,n)=(2,2),(3,3),(p,1)$, and we're done.

Case $1$: $x$ is odd. If $x=1$, clearly $(p,x)=(p,1)$ satisfies the above. Let $q$ be the minimal prime divisor of $x$. Then $$(p-1)^x+1 \equiv 0( \text{mod } q)$$ $$(p-1)^{\text{gcd}(2x,q-1)} \equiv 1(\text{mod } q)$$ $$(p-1)^2 \equiv 1 (\text{mod } q) \text{ by the minimality of q}$$ $$p-1 \equiv -1(\text{mod } q) \implies p \equiv 0(\text{mod } q)\implies p=q$$ Therefore, $p|x$ for odd $x$, and by LTE $$v_p(x^{p-1})=(p-1)v_p(x) \leq v_p(p)+v_p(x)=1+v_p(x)=v_p((p-1)^x+1^x) \text{ since } x^{p-1}|(p-1)^x+1$$ It's easy to see the restraints force $p=3$ and $v_3(x)=1$, and letting $x=3k, k\neq 0(\text{mod } 3)$. Letting $q$ be the minimal prime divisor of $k$ $$2^{3k}+1 \equiv 0 (\text{mod } q) \implies 2^{\text{gcd}(6k, q-1)}\equiv 1(\text{ mod } p) \implies \text{gcd}(q-1,6)=1$$ It's easy to see $\text{gcd}(q-1,6)=1,2$ has no solutions, while the other two cases imply $q=7$. However, if $7|k|x|2^x+1$ is impossible since $x \equiv 0 (\text{mod } 3) \implies 2^x+1 \equiv 2 (\text{mod } 7) \text{ since } 2^3 \equiv 1 (\text{mod } 7)$. Therefore, the only odd cases are when $(p,x)=(1,1), (3,3)$. Case $2$: $x$ is even. If $p$ is odd $$v_2(x^{p-1})=(p-1)v_2(x) \leq v_2((p-1)^x+1)=0$$ which is clearly impossible. Therefore, $p=2$, and its easy to see only $x=1,2$ satisfies this. Therefore, $(p,x)=(p,1),(2,2),(3,3)$.

First let's examine the case for $x=1$ From here we see that $1\mid p$, so we already have a parametric solution $(x,p)\in\{(1,p)\mid \forall p \in P\}$, where $P$ denotes the set of prime numbers. Now let's examine the case when $p=2$, from here we see that $x \mid 2$, and so we see that $x$ is equal to $1$ or to $2$, so another solution appears $(x,p)=(2,2)$ Now let's move onto the case for when $x > 1$ and $p>2$, and let's say that $q$ is the smallest prime number that divides $x$, so $q \mid x$. We easily see that $x \equiv 1 (mod \; 2)$, since $(p-1)^x+1$ is always odd, so we have that $q > 2$ Since $q\mid x$, that implies $q^{p-1} \mid x^{p-1} \mid (p-1)^x+1$, that implies $(p-1)^x \equiv -1 \; (mod \; q)$, and this implies $(p-1)^{2x} \equiv 1 \; (mod \; q)$, from here it is obvious that $q \nmid p-1$ From FLT we have that $(p-1)^{q-1} \equiv 1 \; (mod \; q)$ From this result and the one before hand we have that $(p-1)^{(2x,q-1)} \equiv 1 \; (mod \; q)$, but we know that $(2x,q-1)=2$, so we have that $(p-1)^2 \equiv 1 \; (mod \; q)$, which implies $p(p-2) \equiv 0 \; (mod \; q)$ From this we have two cases.The first case is when $p \equiv 2 \; (mod \; q)$, but returning to $(p-1)^x+1$, we get that this is congruent to $2\; (mod \; q)$, but since we have that $q \mid (p-1)^x+1$, we have that $q=2$, which isn't allowed since $q>2$ So we have the second case $p \equiv 0 \; (mod \; q)$, but this implies that $p=q$, but using the condition $x \leq 2p$, we get that $x=p$ Plugging in our result we have that: $$p^{p-1} \mid (p-1)^p +1$$ $$p^{p-1} \mid 1+\sum_{k=0}^{p} {p \choose k}p^{p-k}(-1)^k$$ $$p^{p-1} \mid \sum_{k=0}^{p-1} {p\choose k}p^{p-k}(-1)^k$$ $$p^{p-1} \mid p^2(1+\underbrace{\sum_{k=0}^{p-2}{p \choose k}p^{p-k-2}(-1)^k}_{\equiv 0 \; (mod \; p)})$$ From here we have that $p-1=2 \implies p=3$.So we have yet another solution. So the only solutions are: $$(x,p)\in\{(1,p);(2,2);(3,3) \mid \forall p \in P\}$$ Where $P$ denotes the set of prime numbers . . .

I claim the answer is $(p, 1)$ for any prime $p$, and the pairs $(2, 2)$ and $(3, 3)$. It's easy to see that $(p, 1)$ is a solution for all $p$, so we can assume that $n \neq 1$ for the rest of this solution. We begin by checking the case of even $n$. Then we have for some $k$ that $$2 \; | \;(p - 1)^{2k} + 1 \implies 2 \mid p,$$ so we would need $p = 2$, and checking we have $n \mid 1 + 1$, so $(2, 2)$ is the only solution for even $n$. We now prove the following claim. Claim. Fix a prime $p$, and let $n>2$ be odd. If $p \nmid n$ then $n$ is not a solution.. Proof. Since $n \neq 1$, $n$ has some minimal prime divisor $q$, with $q \neq p$. Let $n = qk$ for some positive integer $k$. Using the third condition we have $$\begin{align*} (p - 1)^{qk} &\equiv -1 \pmod{q}\\ \implies (p - 1)^{2qk} &\equiv 1\;\;\; \pmod{q}. \end{align*}$$ Let the order of $p - 1$ modulo $q$ be $m$. By the fundamental theorem of orders, we have $m \mid 2qk$. Also as $q \nmid p - 1$, by Fermat's little theorem we have that $m \mid q - 1$, and thus $m \nmid q$. We now do casework on the condition that $m \mid 2k$. Case 1 ($m = 1$). We have $(p - 1) \equiv 1 \pmod{q}$, and thus $(p - 1)^n + 1\equiv 1 + 1 \equiv 2 \equiv 0 \pmod{q}$, which implies that $q = 2$. However, we assumed that $n$ is odd, and thus $q$ is also odd, which is a contradiction. Case 2 ($m > 1$ is odd). In this case we must have $m \mid k$. Assume that $k \neq 1$ (as we already covered $m = 1$). Then as $m \mid q - 1$, $m < q$ and thus there is some prime factor of $k$ (and hence of $n$) less than $q$, which contradicts the minimality of $q$. Case 3 ($m = 2$). In this case, we have $(p - 1)^2 \equiv 1 \pmod{q}$, that is, $(p - 1) \equiv -1 \pmod{q}$, and $p \equiv q$. However, we assumed that $p \nmid n$, so this is a contradiction. Case 4 ($m > 2$ is even). Let $m = 2m'$. Then the condition $m' \mid k$ is already covered in Case 2. Thus as every case leads to a contradiction, $n$ is not a solution. We have shown that $n$ can be one, and we have dealt with the cases where $n$ is even, and then $p \nmid n$. As $n \leq 2p$, we now need to only consider the case of $n = p$ for an odd prime $p$. It suffices to find all odd primes $p$ such that $$\nu_p((p - 1)^p + 1) \geq p -1.$$ As $p \mid (p - 1) + 1$ and $p \nmid p - 1$, we can apply the exponent lifting lemma. we have $$\nu_p((p - 1)^p + 1) = \nu_p(p - 1 + 1) + \nu_p(p) = 2\nu_p(p) = 2.$$ Thus $\nu_p(p^{p - 1}) = p - 1 = 2$, thus $p = 3$ only, and we get the pair $(3, 3)$, which is all of the solutions.

If $x = 1$, then all $p$ work. If $p = 2$, then $x = 2$ works. Assume now that $x,p > 2$. Let $q$ be the minimal prime divisor of $x$. We have that $$\text{ord}_q(p-1) \mid 2x, q-1 \implies \text{ord}_q(p-1) \mid 2 \implies q \mid p(p-2).$$ If $q \mid p$, then $x = p$ and $x = 2p$ are the only possibilities, but $x = 2p$ fails by parity. If $x = p$, then $$p^{p-1} \mid (p-1)^p + 1 \implies p-1 \le \nu_p((p-1)^p + 1)$$ so by LTE $p - 1 \le 2 \implies p = 3$, which works and gives $x = 3$. If $p \equiv 2 \pmod q$, then $(p-1)^x \equiv -1 \pmod q \implies 2 \equiv 0 \pmod q \implies q = 2$, which again fails due to parity. To summarize, our solutions are $\boxed{(1, p), (2, 2), (3, 3)}$

orl wrote: Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p-1}$ is a divisor of $(p-1)^{x}+1$. x is odd else LHS even and RHS odd. Assume p=2, then we have x|2, x=1,2. Now assume x is not 1 or 2, and we also note that obviously all pairs (1,p) work. We claim the answers are $\boxed{(x,p)=(1,p), (2,2), (3,3)}$. Consider the smallest prime q | x: $$(p-1)^x\equiv-1\pmod q\implies(p-1)^2\equiv(p-1)^{\gcd(2x, q-1)} \equiv 1 \pmod q\implies p \equiv \{0,2\} \pmod q;$$ the latter implies -1=$(p-1)^x$ = 1 mod q implies q=2, contradiction, so p=q|x. Looking at v_p with LTE, (p-1)v_p(x)\le v_p(x)+1 implies p=3 which gives x=3.

Long solution with unnecessary claims (probably), though very quick and easy to find. We can see $x = 1$ works for all primes $p$ so disregard this case from now on. Note that we want, $$\begin{align*} (p-1)^x \equiv - 1 \pmod{x^{p-1}} \end{align*}$$ Consider the smallest prime $q \mid x$. Then we have, $$\begin{align*} (p-1)^{2x} \equiv 1 \pmod{q} \end{align*}$$ Then $\text{ord}_{q}(p-1) \mid \gcd(2x, q - 1) = 2$. Assume that $\text{ord}_{q}(p-1) = 1$. Then we find that $p \equiv 2 \pmod{q}$. However then we require that $(p-1)^x + 1 \equiv 2 \equiv 0 \pmod{q}$ implying $q = 2$. Then plugging back in we wish to find solutions to $x \mid 2$ so $x = 2$ works. Now in our second case we must have $\text{ord}_{q}(p-1) = 2$. Then we have, $$\begin{align*} p^2 - 2p &\equiv 0 \pmod{q}\\ \iff p(p - 2) &\equiv 0 \pmod{q} \end{align*}$$ Then as we have alread considered $p \equiv 2$, we need $p \equiv 0 \pmod{q}$. However as $p$ is prime we need $p = q$ and hence $p$ is the smallest prime divisor of $x$. Now note LTE we have $\nu_p((p-1)^x + 1) = 1 + \nu_p(x)$. Also we easily find that $\nu_p(x^{p-1}) = \nu_p(x) \cdot (p-1)$. Then we obviously need, $$\begin{align*} 1 + \nu_p(x) &\geq (p-1) \cdot \nu_p(x) \\ \iff 1 &\geq (p-2) \cdot \nu_p(x) \end{align*}$$ Which holds if and only if $\nu_p(x) = 0$, $p = 2$ or $p = 3$ and $\nu_3(x) \leq 1$. If $\nu_p(x) = 0$, then $x = 1$ as $p$ is the smallest prime divisor of $x$. Then if $p = 2$ we must have $x \mid 2$ which holds if and only if $x = 2$. Finally if $p = 3$ and $\nu_3(x) = 1$ we have $x^2 \mid 2^x + 1$. However from 90IMO3 and orders argument gives that this has solutions only when $x = 3$. Then our final solution set is $\boxed{\{(1, p), (2, 2), (3, 3)\}}$.

We uploaded our solution https://calimath.org/pdf/IMO1999-4.pdf on youtube https://youtu.be/DtVQP4OXVCw.

If $x = 1$, then all $p$ work. For $p=2$, then $x$ is $1$ or $2$. Assume now $p\ge 3$. Let $x>1$, then let the samllest prime factor of x be q. We have $(p-1)^{2x} \equiv 1 \pmod{q}$. This implies $q-1 \mid 2x$. This forces $q=2.$ Now since $v_2(2x^{p-1}) > v_2(p-1)^x +1)$, the only case to be checked now is $x=p$ $p^{p-1} \mid (p-1)^p + 1 \implies p-1 \le \nu_p((p-1)^p + 1)$ $\implies p-1 \le 2 \implies p\le3$ Now checking for $p=3$. We get a solution as $(3,3)$ Therefore the solutions are $\boxed{(1, p), (2, 2), (3, 3)}$

Solution without the bound of $x$ If $p=2$, then $x=2$, so for now assume $p\geq 3$ If $x=1$ all $p$ primes work, so also assume $x\geq 2$ Let $q$ be the smallest prime dividing $x$ then $(p-1)^{2x}\equiv 1\pmod q$ and as $(p-1)^{q-1}\equiv 1\pmod q$ then $\operatorname{Ord}_q(p-1)\mid 2\gcd\left(x,\frac{p-1}{2}\right)=2$ so $(p-1)^2\equiv 1\pmod q$ so $p=q$ or $p\equiv 2\pmod q$, the latter gives $(p-1)^x+1\equiv 2\pmod q$ impossible. If $p=q$ then, by Lifting the Exponent $$\nu_p((p-1)^x+1)=\nu_p(p)+v_p(x)\geq (p-1)\nu_p(x)$$ so $1\geq (p-2)v_p(x)\geq (p-2)\cdot 1$ so $p=3$ which gives to find all integers $x$ such that $x^2\mid 2^x+1$ which by IMO 1990/3 only $x=3$ works so the solutions are $\boxed{(x,p)=(1,p),(2,2), (3,3)}$

I was given no condition bounding $x$: The solution set is $(x,p) \in \{(1,p), (2,2), (3,3)\}$. Note that if $x=1$, all $p$ work. Also, if $p=2$, we must have $x \mid 2$, which gives the unique solution $(x,p)=(2,2)$. Assume $x>1$ and $p>2$ for the remainder of this solution. Let $q$ be the smallest prime dividing $x$. We have $$\operatorname{ord}_q(p-1) \mid \gcd(2x,q-1) = 2.$$ Hence, $$(p-1)^2 \equiv 1 \pmod{q} \iff p(p-2) \equiv 0 \pmod{q}.$$ Hence, $p \equiv 0,2 \pmod{q}$. The latter gives $$(p-1)^x+1 \equiv 2 \pmod{q},$$ implying that $q=2$. However, $(p-1)^x+1$ is odd, so this yields a contradiction. Otherwise, we have $p \equiv 0 \pmod{q} \iff p=q$, so LTE gives $$\nu_p((p-1)^x+1) = \nu_p(p)+\nu_p(x) \ge \nu_p(x^{p-1}) = (p-1) \nu_p(x)$$ $$\implies 1+\nu_p(x) \ge (p-1) \nu_p(x) \iff (p-2) \nu_p(x) \le 1.$$ Since $\nu_p(x) \ge 1$, we must have $p=3$. The problem is now reduced to finding all $x$ such that $x^2 \mid 2^x+1$. Lemma The only value $x$ satisfying this is $x=3$. Proof: Consider IMO 1990/3. $\square$ Hence, the unique solution here is $(x,p)=(3,3)$. This completes our solution set.

The condition $x \leq 2p$ turns out to be unnecessary. Our solutions are $\boxed{(1,p),(2,2),(3,3)}$. We proceed first by tackling edge cases: If $x=1$, $p$ can be any prime. If $p=2$, $x$ is either 1 or 2. Otherwise, $p$ is odd, forcing $x$ to be odd. Then we require $$(p-1) \cdot v_p(x) \leq v_p((p-1)^x+1) = v_p(x) + 1 \implies (p-2) \cdot v_p(x) \leq 1.$$ If $p=3$, IMO 1990/3 tells us $x$ is either 1 or 3. Otherwise, $\gcd(x,p)=1$. Suppose the least prime divisor of $x$ is $q>2$. Then $$\operatorname{ord}_q(p-1) \mid 2n, p-1 \text{ but not } n \implies \operatorname{ord}_q(p-1) = 2 \implies p=q,$$ contradiction. $\blacksquare$

We claim that the only such pairs are $(2,2)$, $(3,3)$, and $(1,p)$ for any prime $p$. (This proof assumes there is no bound on $x$.) We start with the trivial case when $p=2$. We end up with $x\mid 2$, which clearly gives only $x=1$ and $x=2$ as solutions. For odd primes, we know that $(p-1)^x+1$ is odd, and thus $x$ must be odd. For any $p$, $x=1$ clearly works since $1$ divides everything. Assuming $x\neq 1$, we let $q$ be the smallest prime divisor of $x$. We know that the order of $p-1\pmod{q}$ divides $\gcd(q-1,2x)$. Since $x$ only has prime factors at least $q$, it is clear $x$ and $q-1$ are relatively prime and thus $\gcd(q-1,2x)$ must be exactly $2$. The order cannot be $1$, because in that case $q\mid (p-1)^x-1$, not $(p-1)^x+1$, so the order must be $2$. This implies that $p-1\equiv -1\pmod{q}$, so $p\equiv 0\pmod{q}$ and thus $p=q$. Now we use LTE to rule out all cases except $p=3$. We know that $\nu_p((p-1)-(-1))=1$, so $\nu_p((p-1)^x-(-1)^x)=1+\nu_p(x)$. We also have that $\nu_p(x^{p-1})=(p-1)\nu_p(x)$. Note that since $p=q$, we have $p\mid x$. This means that for $p>3$, $(p-1)\nu_p(x)>1+\nu_p(x)$, so there are no solutions. For $p=3$, if $\nu_3(x)=1$ then they have equal values, so this case has to be resolved separately. We can check to see that $(3,3)$ is a solution. Now we have to rule out other solutions. Our previous bound showed that $\nu_3(x)=1$ was the only one possible. Let $r$ be the minimum other prime that is a factor of $x$. Then the order of $2\pmod{r}$ divides $\gcd(r-1,2x)$. Similar to before, other than a factor each of $2$ and $3$, $2x$ only contains prime factors greater than $r$, and thus the order must divide $6$. Furthermore, the order being $1$ or $3$ won't work, so it must be $2$ or $6$. However, $3$ is the only working prime for order $2$, while no primes exist for order $6$ since $2^6-1=63$ but $7$ has order $3$ since $2^3-1=7$. Thus, there can be no other prime factors, and we are done.

Note that when $x=1$ every prime works so we will only consider the cases where $x \neq 1$. Now note that for any prime factor $q \mid x$ we have $(p-1)^x \equiv -1 \mod{q}, (p-1)^{2x} \equiv 1 \mod{q}$ which means $\delta_{q}(p-1)=\gcd(2x, q-1)$ which is either $2$ or $1$ since $q-1$ is corpime with $x$. If it is $1$, then $(p-1)^x \equiv 1 \equiv -1 \mod{q} \implies q=2 \implies p=2$ in which case we have $(p-1)^x+1=2$ which is divisible only by $1,2$ so $(x,p)=(2,2)$ is the new solution. If $\delta_q(p-1)=2$ then $p-1 \equiv -1 \mod{q} \implies p \equiv 0 \mod{q} \implies p=q$. Then that means $q \leq x \leq 2q$ but if $x=2q$ then that means $(p-1)^x+1$ has a prime factor where the order is 1, but we dealt with that in the previous case already. Thus $x=q=p$. Then we have $p^{p-1} \mid (p-1)^p+1$. By LTE we get that $\nu_p((p-1)^p+1)=\nu_p(p)+\nu_p(p)=2$. Thus the division only holds when $p=2, 3$, but we dealt with the case when $p=2$ already so we check the solutions for $p=3$ which gives us a new solution $(x,p)=(3,3)$, and if $p \geq 5$ clearly there are no solutions as the division no longer holds. Thus the solutions are $(x,p)=(1,p),(2,2),(3,3)$.

We claim the solutions are $(1,p)$ for all $p$, $(2,2)$, and $(3,3)$. They can be checked to work. Furthermore, if $p=2$, then $x$ must be a divisor of $1^x + 1 = 2$, so $(1,2)$ and $(2,2)$ are the only solutions. Thus, from now on, we can assume $x > 1$ and $p \geq 3$. We know $x$ has a least prime factor; let that be $q$. Then, we have $$\begin{align*} (p-1)^x \equiv -1 \pmod{q} \\ (p-1)^{2x} \equiv 1 \pmod{q}. \end{align*}$$ Looking at the order of $(p-1)^2$, it must divide the GCD of $q-1$ and $x$. But $q$ being the least prime factor implies that GCD is $1$, so $(p-1)^2 \equiv 1 \pmod{q}$. This means $q \mid p(p-2)$. However, $q \mid p-2$ is impossible. To see why, notice that $(p-1)^x + 1 \equiv 1 + 1 \pmod{p-2}$, so $(p-1)^x + 1 \equiv 2 \pmod{q}$. Since $q$ is odd, this means that $(p-1)^x + 1$ is not divisible by $q$, contradicting the fact that $x^{p-1}$ divides $(p-1)^x + 1$. Thus, we must have $q = p$. Now, notice that since $x$ must be odd, we can use lifting the exponent: $$\nu_p((p-1)^x + 1) = 1 + \nu_p(x) \geq \nu_p(x^{p-1}) = (p-1)\nu_p(x).$$ This implies $$\frac{1}{p-2} \geq \nu_p(x) \geq 1,$$ so $p \leq 3$. We only need to consider the case where $p = 3$. However, the result of IMO 1990/3 tells us that $(1,3)$ and $(3,3)$ are the only solutions in this case, so we are done.

The answer is only $(3,3), (2,2)$ and $(1,p)$ for all primes $p$. It is easy to verify these work. Main idea is to consider the lowest prime divisor of $x$ (ignore $x =1$ as it always works, ignore $p < 4$ as it can be done manually), let it be $q$. Then take $\mathrm{ord}_q p - 1 \mid q - 1, \mathrm{ord}_q p - 1 \mid 2x$, so $\mathrm{ord}_q p -1 = 1,2$. In the first case, we have $q = p - 2$, so for $p > 3$ we can check that $x = q$ by size, so we can eliminate this case by just showing $q^{p - 1} > p^{q } + 1$, by mod $p$ they are clearly never equal so we can just show $q^{p - 1} > p^{q }$ which forces no sol, since $(q + 1)^{p- 1} = (p - 1)^{q + 1}$, it suffices to show that $(\frac{q}{q + 1})^{p - 1} \ge \frac{1}{p - 1}$, rewrite as $(1 - \frac{1}{c})^{c} \ge \frac 1c$, which is obvious for $c > 4$ since the left is increasing in $c$ and the right is decreasing , in the latter we have $q = p$, so we can use LTE, check $p = 2$ manually then LTE on odd case gives $\nu_p$ on the right is $2$, on left is $p - 1$, so we must have $p \le 3$, giving the only solution as $p = 3$.

Note that $(1,p)$ works for any prime $p$ and $(2,2)$ also works for any $x$. So let us assume $x>1$ and $p>2$. We have $x^{p-1}\mid (p-1)^{2x}-1$. Let $q$ be a prime such that $q\mid x$. Let $\alpha=\text{ord}_q({p-1})\leq q-1$ then $q\mid (p-1)^\alpha-1$ and $\alpha\mid 2x$. So by LTE $$\begin{align*} v_q\left((p-1)^{2x}-1\right)\geq v_q(x^{p-1}) & \Rightarrow v_q\left((p-1)^\alpha-1\right)+v_q(2x/\alpha) \geq (p-1)v_q(x) \\ & \Rightarrow v_q\left((p-1)^\alpha-1\right)\geq (p-2)v_q(x) \\ & \Rightarrow q^{p-2} \mid (p-1)^\alpha-1 \\ & \Rightarrow q^{p-2} <(p-1)^\alpha\leq (p-1)^{q-1}.\end{align*}$$ From this it's not very hard to show that $q\geq p$. So if $x=qk\leq 2p$ then either $k=2,q=p$ or $k=1$. If $x=2p$ then by mod 2 we get a contradiction. If $x=q$ then by FLT $$0\equiv (p-1)^q+1 \equiv (p-1)+1 \equiv p \pmod q,$$ so $q=p$. Using LTE again $$p-1\leq v_p\left((p-1)^p+1\right)=v_p(p-1+1)+v_p(p)=2,$$ so $p=3$. Checking we find that the other working pair is $(3,3)$.

$x = 1$ and any prime work, and if $p = 2$, then $x = 2$, so assume $x \neq 1$, and $p$ is odd. Clearly, $(p - 1)^x + 1$ is odd, so $x$ must be odd as well. Consider the smallest prime divisor, $q$ (which is odd), of $x$, then $q \mid (p - 1)^x + 1 \implies (p - 1)^{2x} \equiv 1\mod{q} \implies \text{ord}_q(p - 1) \mid \gcd(2x, q - 1) = 2$. Note that $\text{ord}_q(p - 1) \neq 1 \implies \text{ord}_q(p - 1) = 2 \implies q \mid p - 1 + 1 = p \implies q = p$. So, $p \mid x$. We have $(p - 1)v_p(x) \leq v_p((p - 1)^x + 1) = 1 + v_p(x)$, and since $v_p(x) = 1$, $p - 1 \leq 2 \implies p = 3$. Just checking gives only $x = 3$ works, so we are done.

The only answers are $(x, p) = (2, 2), (3, 3)$, and $(1, p)$ for any prime $p$. It's easy to verify all of these solutions work, so now we show they are the only ones. When $p = 2$, we have $x \mid 2$, so $x = 1$, or $x = 2$. When $p = 3$, by IMO 1990/3, the only answers are $(x, p) = (1, 3)$ and $(3, 3)$. When $p > 3$, if $x = 1$ then evidently $x^{p-1} \mid (p-1)^{x}+1$. If $x > 1$, suppose $q$ is the smallest prime factor of $x$. Note that $(p - 1)^x + 1$ is odd, so $q > 2$. Since $(p - 1)^x \equiv -1 \pmod p$, we find that $(p - 1)^{2x} \equiv 1 \pmod q$ so $\text{ord}_q(p - 1) \mid 2x$. Because $\text{ord}_q(p - 1) \le q - 1$, we must have $\text{ord}_q(p - 1) \in \{1, 2\}$. If $\text{ord}_q(p - 1) = 1$ then $p - 1 \equiv 1 \pmod q$. Thus $0 \equiv (p - 1)^x + 1 \equiv 2 \pmod q$, so $q = 2$, which is impossible. If $\text{ord}_q(p - 1) = 2$ then $p - 1 \equiv -1 \pmod q$, or $p \equiv 0 \pmod q$, so $p = q$. Then from LTE, we find that $$(p - 1)\nu_p(x) = \nu_p(x^{p - 1}) \le \nu_p((p - 1)^x + 1) = \nu_p(p) + \nu_p(x) = 1 + \nu_p(x).$$ However, because $p > 3$ and $\nu_p(x) > 1$, this is impossible. So, we are done.