IMO ShortList 1999, number theory problem 1

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Nov 13, 2004, 11:33 PM • 7 Y

Y by ahmedosama, Davi-8191, Adventure10, megarnie, HWenslawski, Mango247, cubres

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$ .

Attachments:

This post has been edited 2 times. Last edited by orl, Nov 14, 2004, 10:16 PM

Z K Y

The post below has been deleted. Click to close.

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

grobber

7849 posts

grobber

#2 h Nov 14, 2004, 1:36 AM • 11 Y

Y by feridverdiyev, alreva99, Adventure10, megarnie, ngocthinht1k10ltt, Vladimir_Djurica, Mai-san, Mango247, Stuffybear, cubres, and 1 other user

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)$ .

Z K Y

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#3 h Nov 14, 2004, 1:39 AM • 3 Y

Y by Adventure10, Mango247, cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

Davron

484 posts

Davron

#4 h Jun 12, 2006, 4:46 AM • 3 Y

Y by Adventure10, Mango247, cubres

@all : can you please explain

$q|[(p-1)^2x-1,(p-1)^{q-1}-1)=(p-1)^2-1$

Sincerely Davron

Z K Y

The post below has been deleted. Click to close.

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

marko avila

521 posts

marko avila

#5 h Oct 15, 2006, 2:36 AM • 5 Y

Y by Adventure10, Mango247, Mango247, Mango247, cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

Mathias_DK

1312 posts

Mathias_DK

#6 h Jun 17, 2009, 8:58 PM • 2 Y

Y by Adventure10, cubres

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

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

ropro01

62 posts

ropro01

#7 h Jun 29, 2012, 10:20 AM • 3 Y

Y by navi_09220114, Adventure10, cubres

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$

Z K Y

The post below has been deleted. Click to close.

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

trigonometry456103

349 posts

trigonometry456103

#8 h Jul 4, 2012, 5:05 PM • 3 Y

Y by Adventure10, Mango247, cubres

Here is my solution(not exactly written up in the most organized way):
Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

frill

316 posts

frill

#9 h Apr 26, 2014, 5:17 PM • 5 Y

Y by Minkowsi47, Adventure10, Mango247, endless_abyss, cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

sayantanchakraborty

505 posts

sayantanchakraborty

#10 h Apr 27, 2014, 4:30 PM • 3 Y

Y by Tellocan, Adventure10, cubres

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

Z K Y

The post below has been deleted. Click to close.

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

Blitzkrieg97

236 posts

Blitzkrieg97

#11 h Feb 12, 2015, 10:24 AM • 2 Y

Y by Adventure10, cubres

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

Z K Y

The post below has been deleted. Click to close.

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

Dukejukem

695 posts

Dukejukem

#12 h May 25, 2015, 4:15 AM • 3 Y

Y by Adventure10, Mango247, cubres

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.$

Z K Y

The post below has been deleted. Click to close.

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

Vfire

1354 posts

Vfire

#13 h Mar 25, 2018, 5:21 AM • 3 Y

Y by AIME12345, Adventure10, cubres

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$

Z K Y

The post below has been deleted. Click to close.

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

samoha

9 posts

samoha

#15 h Jul 8, 2018, 10:09 PM • 3 Y

Y by Adventure10, Mango247, cubres

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$

Z K Y

The post below has been deleted. Click to close.

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

math_pi_rate

1218 posts

math_pi_rate

#16 h Aug 23, 2018, 3:55 PM • 3 Y

Y by Adventure10, Mango247, cubres

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)$ .

This post has been edited 1 time. Last edited by math_pi_rate, Aug 23, 2018, 3:57 PM

Z K Y

The post below has been deleted. Click to close.

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

Shreyasharma

678 posts

Shreyasharma

#50 h Dec 28, 2023, 4:36 AM • 1 Y

Y by cubres

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)\}}$ .

This post has been edited 1 time. Last edited by Shreyasharma, Dec 28, 2023, 4:37 AM

Z K Y

The post below has been deleted. Click to close.

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

Cali.Math

128 posts

Cali.Math

#51 h Dec 28, 2023, 8:33 PM • 1 Y

Y by cubres

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

Z K Y

The post below has been deleted. Click to close.

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

lelouchvigeo

179 posts

lelouchvigeo

#52 h Jan 20, 2024, 5:13 AM • 1 Y

Y by cubres

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)}$

Z K Y

The post below has been deleted. Click to close.

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

AlanLG

241 posts

AlanLG

#53 h Feb 7, 2024, 12:59 AM • 1 Y

Y by cubres

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)}$

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2513 posts

joshualiu315

#54 h Feb 12, 2024, 8:33 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

793 posts

shendrew7

#55 h Mar 1, 2024, 9:55 PM • 1 Y

Y by cubres

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$

Z K Y

The post below has been deleted. Click to close.

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

SenorSloth

37 posts

SenorSloth

#56 h Jun 16, 2024, 2:32 AM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

de-Kirschbaum

193 posts

de-Kirschbaum

#57 h Jun 19, 2024, 8:41 PM • 1 Y

Y by cubres

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)$ .

Z K Y

The post below has been deleted. Click to close.

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

BestAOPS

707 posts

BestAOPS

#58 h Jul 6, 2024, 3:29 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1253 posts

ezpotd

#59 h Aug 23, 2024, 4:00 AM • 1 Y

Y by cubres

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$ .

Z K Y

The post below has been deleted. Click to close.

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

pie854

243 posts

pie854

#60 h Sep 28, 2024, 11:43 AM • 1 Y

Y by cubres

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)$ .

This post has been edited 3 times. Last edited by pie854, Sep 28, 2024, 1:20 PM

Z K Y

The post below has been deleted. Click to close.

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

alexanderhamilton124

388 posts

alexanderhamilton124

#61 h Oct 2, 2024, 12:22 PM • 2 Y

Y by ubermensch, cubres

$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.

Z K Y

The post below has been deleted. Click to close.

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

eibc

600 posts

eibc

#63 h Jan 2, 2025, 9:50 PM • 1 Y

Y by cubres

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.

Z K Y

The post below has been deleted. Click to close.

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

smileapple

1010 posts

smileapple

#64 h Feb 18, 2025, 3:29 AM • 1 Y

Y by cubres

If $p\ge3$ , note that $x$ must be odd. Then $\nu_p(x^{p-1})=(p-1)\nu_p(x)$ and $\nu_p((p-1)^x+1)=\nu_p(p)+\nu_p(x)=\nu_p(x)+1$ . Hence $(p-2)\nu_p(x)\le1$ , so that either $p=3$ or $\nu_p(x)=0$ . In the first case, by 90IMO3 the only solutions are $(x,p)=(1,3)$ and $(x,p)=(3,3)$ .

Otherwise, Let $q$ be the minimal prime divisor of $x$ . We have $(p-1)^{2x}\equiv1\pmod q$ and $(p-1)^{(q-1)}\equiv1\pmod q$ , so that $(p-1)^2\equiv(p-1)^{\gcd(2x,q-1)}\equiv1\pmod q$ , so that $p\equiv2\pmod q$ . But then $(p-1)^x+1\equiv2\pmod q$ and $x^{p-1}\equiv0\pmod q$ , which is a contradiction as $p$ is odd. Thus $q$ cannot exist, so that $x=1$ .

If $p=2$ then $x=1$ or $x=2$ both work.

Our solution set is thus $\boxed{\{(2,2),(3,3)\}\cup\{(1,p)\mid p\in\mathbb{P}\}}$ .

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

589 posts

cursed_tangent1434

#65 h Apr 6, 2025, 6:57 AM

Y by

We claim that the only pairs of solutions $(x,p)$ are $(1,p)$ for any prime $p$ , $(2,2)$ and $(3,3)$ . It is easy to check that all of these indeed work. We now show that they are the only ones.

First note that, if $p=2$ the resulting condition is $x \mid 2$ which is only possible if $x=1$ or $x=2$ . If $p$ is odd, the right hand side is clearly odd as well, so $x$ must be odd. Further, if $x=1$ then it is clear that $p$ can be an arbitrary prime. Thus, in what follows we assume that $x>1$ is even and that $p$ is an odd prime. We first show the following claim.

Claim : For all pairs of solutions $(x,p)$ we must have $p \mid x$ .

Proof : Let $q$ denote the smallest prime divisor of $x$ . Then,
$q\mid x^{p-1} \mid (p-1)^x +1$ implies $(p-1)^{2x} \equiv 1 \pmod{q}$ . Thus, $\text{ord}_{q}(p-1) \mid 2x$ . Also, $\text{ord}_{q}(p-1) \mid q-1$ . But then, if there exists an odd prime divisor $r \mid \text{ord}_q(p-1)$ then $r \mid 2x$ so $r\mid x$ and also $r \mid q-1$ . Thus, $r \le q-1 <q$ which contradicts the minimality of $q$ . Thus, $\text{ord}_{q}(p-1)$ is a perfect power of two. However, since $x$ is odd $\nu_2(2x)=1$ so $\text{ord}_{q}(p-1)=2$ . This means, $(p-1)^2 \equiv 1 \pmod{q}$ and thus,
$0 \equiv (p-1)^x +1 \equiv (p-1)+1 \equiv p \pmod{q}$ which is possible if and only if $p=q$ as desired.

Now note that by Lifting the Exponent Lemma we have,
$(p-1)\nu_p(x) = \nu_p(x^{p-1}) \le \nu_p((p-1)^x+1) =\nu_p(p)+\nu_p(x)=\nu_p(x)+1$ However, if $p>3$ ,
$(p-1)\nu_p(x) > 2\nu_p(x) \ge \nu_p(x)+1$ which is a clear contradiction. Thus, we must have $p=3$ which reduces the desired divisibility to
$x^2 \mid 2^x +1$ whose solutions are known to be $x=1$ and $x=3$ by IMO 1990/3 which finishes the proof.

Z K Y