OOps.. Thanks:)

$r$ is an odd number.

I only found that: Lets assume $p^p=1(mod(pr+1))$ Then we take minimum $d$ such that $p^d=1(mod(pr+1))$ => $d|p$ => $d=p$ . => $d=p|\phi(pr+1)$ => there exist a prime $q$ such that $p|q-1$ , $q|pr+1$ so let $q=pk+1$ where $k$ is even positive integer. Then we have $pk+1|pr+1$ => $pk+1|r-k$ Could someone help?

Could someone help?

for each prime divisor q of pr+1 we have 2p|q-1 so also must be 2p|(pr+1)-1=pr.

rightways wrote: for each prime divisor q of pr+1 we have 2p|q-1 so also must be 2p|(pr+1)-1=pr. What you are saying is like, $a|b-1,b|c$ so $a|c-1$ which is not necessarily true.

Let $q$ is a prime divisor of $pr+1$ => $p^p=1(modq)$ => $q|p-1$ or $p|q-1$. let us call former ones $bad$ and latter ones $good$. If all of the divisors of $pr+1$ is $good$ then our proof is finished because $q=ap+1$, $a$ even => $pr+1=(a_1p+1)...(a_tp+1)=p.2k+1$ but this is a contradiction. But i cant solve the part if $pr+1$ has a $bad$ divisor.

Let $ S $ be the set of odd numbers $ r $ such that $ pr+1 \mid p^p - 1 $ and for the sake of contradiction, suppose that $ S $ is non-empty. Choose the minimal element $ r_0 $ of $ S $ and let the order of $ p $ modulo $ pr_0 + 1 $ be $ d $. Then, $ d \mid p \implies d=p $. Also, $ p^{ \phi (pr_0 + 1)} \equiv 1 \bmod ( pr_0 +1 ) $ and so $ p \mid \phi (pr_0 + 1) $. Therefore, if the prime factorisation of $ pr_0+1 $ is $ pr_0 + 1 = q_1^{a_1} \cdots q_k^{a_k} $, with $ a_i > 0 $, there exists a $ q_i $ such that $ p \mid q_i - 1 \implies q_i = mp+1 $. Then, this guarantees $ k \ge 2 $ and $ q_i^ {a_i} $ is also of the form $ Mp+1 $ with $ M $ even. Therefore, the number $ q_2^{a_2} \cdots q_k^{a_k} $ is also of the form $ r_1p+1 $ and we have $ r_1Mp + M + r_1 = r_0 $ and $ M $ even implies that $ r_1 $ is odd, and $ r_1p+1 \mid r_0p+1 \mid p^p-1 $, contradicting the minimality of $ r_0 $. Thus, $ S $ is empty.

My solution: Assume the opposite that there exists some $p,r$ such that $pr+1|p^p-1$ $pr+1|pr+1$$\implies$ $pr+1|p(p^(p-1)+r)$ and because $(p,pr+1)=1$ $\implies$ $pr+1|p^(p-1)+r$$\implies$ $pr+1|p^(p-1)-r-pr^2+r$$\implies$ $pr+1|p(p^(p-2)-r^2)$ $\implies$ $pr+1|p^(p-2)-r^2$ and it's obvious that $pr+1|p^(p-i)+((-1)^(i+1))r$ $\implies$ $pr+1|p-r^(p-1)$$\implies$$pr+1|pr-r^p$$\implies$ $pr+1|r^p-1$$\implies$ $pr+1|r^p-1+p^p-1$ $and$$ pr+1|(r^p-1)(p^p-1)=r^pp^p-r^p-p^p+1=((pr)^p+1)-r^p-p^p$ $\implies$ $pr+1|r^p+p^p$$\implies$ $pr+1|2$ which is contradiction.

Let $d \in \mathbb{N}$ be a divisor of $p^p - 1$ with $d \equiv 1 \pmod{p}.$ Let $S$ be the set of all prime divisors of $d$ that also divide $p - 1.$ We will show that $S$ is empty. Suppose otherwise, and note that by LTE, we have $v_q(p^p - 1) = v_q(p - 1)$ for all $q \in S.$ Consequently, \[1 < \prod\limits_{q \in S} q^{v_q(d)} \le \prod\limits_{q \in S} q^{v_q(p^p - 1)} \le \prod_{\substack{q \mid p - 1 \\ q \; \text{prime}}} q^{v_q(p - 1)} = p - 1.\] Now, let $T$ be the set of all prime divisors of $d$ that do not divide $p - 1.$ Then for any $q \in T$, we have $q \mid p^p - 1 \implies \text{ord}_q(p) \mid p \implies \text{ord}_q(p) \in \{1, p\}.$ However, $\text{ord}_q(p) \ne 1$ by assumption. Therefore, by Fermat's Little Theorem, we obtain $p = \text{ord}_q(p) \mid q - 1 \implies q \equiv 1 \pmod{p}.$ It follows that \[1 \equiv d = \left(\prod\limits_{q \in S} q^{v_q(d)}\right)\left(\prod\limits_{q \in T} q^{v_q(d)}\right) \equiv \prod\limits_{q \in S} q^{v_q(d)} \not\equiv 1 \pmod{p},\] a contradiction. Consequently, $S$ is empty. It follows that \[d \mid \frac{p^p - 1}{p - 1} = 1 + p + \cdots + p^{p - 1},\] which is odd. Consequently, $d$ is odd as well. Therefore, if we write $d = pr + 1$, it follows that $r$ cannot be odd. $\square$

Mathematicalx wrote: Could someone help?

TO AHKR...

AHKR wrote: \begin{align*}p^p \equiv 1\ mod(pr+1)\end{align*} why should it be \begin{align*}p \mid \phi(pr+1)? \end{align*}shouldn't it be \begin{align*} ORDpr+1(p) \mid p? \end{align*}

What is order of p modulo....... Can anyone please help...........

Number $d$ is an order of $a$ modulo a prime $p$ if and only if $a^d-1$ is divisible by $p$ but $(a-1)(a^2-1)...(a^{d-1}-1)$ is not divisible by $p$.

i tried another proof by contradiction.suppose that $p^p-1=0$ for mod(pr+1), than $p^p-1=-(pr+1)$ $p^p=-pr$ $p^{p-1}=-r$ $p^{2p-2}=r^2$ cuz $gcd(p, pr+1) =1$,cuz if $p|pr+1$ then $p|1$ $(pr+1)^2=(pr)^2+2pr+1=(pr)^2+pr=0$ $p^2r^2 = p^{2p}=-pr$ $p^{2p-1}=-r$ and $p^{p-1}=-r$ we got that $\phi(pr+1)|p$, but for any $n>2$ the $\phi(n)$ function will be divisible by 2, but that implies that $2|p$, so we are done.

......... Ignore

Infinite descent! .

Very well-known

Wolowizard wrote: My solution: Assume the opposite that there exists some $p,r$ such that $pr+1|p^p-1$ $pr+1|pr+1$$\implies$ $pr+1|p(p^(p-1)+r)$ and because $(p,pr+1)=1$ $\implies$ $pr+1|p^(p-1)+r$$\implies$ $pr+1|p^(p-1)-r-pr^2+r$$\implies$ $pr+1|p(p^(p-2)-r^2)$ $\implies$ $pr+1|p^(p-2)-r^2$ and it's obvious that $pr+1|p^(p-i)+((-1)^(i+1))r$ $\implies$ $pr+1|p-r^(p-1)$$\implies$$pr+1|pr-r^p$$\implies$ $pr+1|r^p-1$$\implies$ $pr+1|r^p-1+p^p-1$ $and$$ pr+1|(r^p-1)(p^p-1)=r^pp^p-r^p-p^p+1=((pr)^p+1)-r^p-p^p$ $\implies$ $pr+1|r^p+p^p$$\implies$ $pr+1|2$ which is contradiction. Brilliant solution

ThirdTimeLucky wrote: Let $ S $ be the set of odd numbers $ r $ such that $ pr+1 \mid p^p - 1 $ and for the sake of contradiction, suppose that $ S $ is non-empty. Choose the minimal element $ r_0 $ of $ S $ and let the order of $ p $ modulo $ pr_0 + 1 $ be $ d $. Then, $ d \mid p \implies d=p $. Also, $ p^{ \phi (pr_0 + 1)} \equiv 1 \bmod ( pr_0 +1 ) $ and so $ p \mid \phi (pr_0 + 1) $. Therefore, if the prime factorisation of $ pr_0+1 $ is $ pr_0 + 1 = q_1^{a_1} \cdots q_k^{a_k} $, with $ a_i > 0 $, there exists a $ q_i $ such that $ p \mid q_i - 1 \implies q_i = mp+1 $. Then, this guarantees $ k \ge 2 $ and $ q_i^ {a_i} $ is also of the form $ Mp+1 $ with $ M $ even. Therefore, the number $ q_2^{a_2} \cdots q_k^{a_k} $ is also of the form $ r_1p+1 $ and we have $ r_1Mp + M + r_1 = r_0 $ and $ M $ even implies that $ r_1 $ is odd, and $ r_1p+1 \mid r_0p+1 \mid p^p-1 $, contradicting the minimality of $ r_0 $. Thus, $ S $ is empty. How did you deduce p*r+1 divides p-r^(p-1)

We have $\phi(pr+1)|ord_{pr+1}{p}=p$ or $ord_{pr+1}{p}|\phi(pr+1)$ Clearly,the first one is absurd(unless $r=1$ and it is easy to verify this doesn't work) so we must need $ord_{pr+1}{p}|\phi(pr+1)=>p|\phi(pr+1)=pr+1 \cdot \prod \frac{p_i-1}{p_i}$ so over here one of the $p_i-1=p$ implying $p_i=p+1$ where $p_i$ is a prime which is impossible, implying the result.

Firstly note that $\gcd(pr+1,p-1)=\gcd(p(r+1),p-1)=\gcd(r+1,p-1)>1$. Let us consider following divisibility, $$pr+1\mid (p-1)\cdot \left(\frac{p^p-1}{p-1}\right).$$ Claim. Any divisor of $\dfrac{p^p-1}{p-1}$ is $\equiv 1\pmod p$. Proof. If $q\mid \dfrac{p^p-1}{p-1}$, then $p^p\equiv 1\pmod q$, so $\text{ord}_q(p)=1$ or $\text{ord}_q(p)=p$. If $\text{ord}_q(p)=1$, then $p\equiv 1\pmod q$ and hence $\dfrac{p^p-1}{p-1}=p^{p-1}+\ldots +p+1\equiv p\mod{q}$ and this implies $q=p$, which is impossible. Therefore $\text{ord}_q(p)=p$ and hence $p\mid q-1$ by Fermat's Little Theorem. Hence $pr+1=\frac{p-1}{a}\cdot k$, where $k\mid \frac{p^p-1}{p-1}$ and $a<p-1$ by the gcd condition. By the claim, $k\equiv 1\pmod{p}$, hence $$1\equiv pr+1=\frac{p-1}{a}\cdot k\equiv \frac{-1}{a}\pmod p\implies a\equiv -1\pmod p,$$which is impossible as $a<p-1$.

there's a mistake here it should be plus not - helppp please guys

helloooo

2014 IMOTC T1P1 wrote: Let $p$ be an odd prime and $r$ an odd natural number. Prove that: $pr+1$ does not divide $p^p-1.$ Assume that there is $(p,r)$ that meets the given condition $\Rightarrow pr+1|(p-1)(p^{p-1}+p^{p-2}+...+p+1)$ Let $d=\gcd(p-1,p^{p-1}+p^{p-2}+...+p+1)\Rightarrow p\equiv 1(\bmod d)\Rightarrow 0\equiv p^{p-1}+p^{p-2}+...+p+1\equiv p(\bmod d)$ Note that $d|p-1\Rightarrow d\ne p\Rightarrow d=1 \Rightarrow \left[ \begin{array}{l} pr + 1|p - 1\Rightarrow pr+1\le p-1(!)\\ pr + 1|p^{p-1}+p^{p-2}+...+p+1 \end{array} \right.$ Now we have a lemma: Given $A=p^{p-1}+p^{p-2}+...+p+1,$ with $p$ is a prime number. Let $q$ be a prime divisor of $A.$

Also note that $A$ is an odd interger, so $A$ doesn't have any even divisors. Applying the lemma above gives us: any prime divisor $s_1$ of $A$ is congruent to $1 (\bmod p)\Rightarrow s_1=pl_1+1\Rightarrow l_1$ is even. Let $s_2=pl_2+1$ be another prime divisor of $A\Rightarrow l_2$ is even. Then $s_1s_2=(pl_1+1)(pl_2+1)=p(pl_1l_2+l_1+l_2)+1,$ with $pl_1l_2+l_1+l_2$ is an even number. From that we can conclude: any divisor of $A$ is in the form of $pl+1,$ with $l$ is even, that leads to the contradiction. Conclusion: $pr+1$ does not divide $p^p-1,$ with $p$ is an odd prime and $r$ is an odd natural number.

FTSOC assume $pr+1\mid p^p-1\implies \text{ord}_{pr+1}(p)=p$ and let $r$ be minimal. So, $\text{ord}_{pr+1}(p)\mid \phi(pr+1)$, this lets us write $pr+1=\prod_{i=1}{q_i}^{a_i}$ where $q_i$ is a prime. Because $p\big| (pr+1) \prod_{i=1}\left(1-\tfrac{1}{q_i}\right)$ and $\gcd(p,pr+1)=1$ there is at least one $q_i$ such that $p\mid q_i-1$. So, $q_i=ps+1\mid pr+1 \implies pr+1=(ps+1)(pt+1) $ for some $t$, where $pt+1$ is even thus contradicting the minimality of $r$.