Nice problem...are there any ideas? bump

if $p\equiv 2\pmod{3},p>5$,then $\frac{p-3}{2}\cdot \frac{p-2}{3}\equiv 1\pmod{p}$,contradiction

MathLover_ZJ wrote: if $p\equiv 2\pmod{3},p>5$,then $\frac{p-3}{2}\cdot \frac{p-2}{3}\equiv 1\pmod{p}$,contradiction $p+1=2m$where $m$ is a prime, otherwise $p+1=2mn$ then$(2m)(n)\equiv 1$and $2m,n<\frac{p}{2}$?

amitsom wrote: MathLover_ZJ wrote: if $p\equiv 2\pmod{3},p>5$,then $\frac{p-3}{2}\cdot \frac{p-2}{3}\equiv 1\pmod{p}$,contradiction $p+1=2m$where $m$ is a prime, otherwise $p+1=2mn$ then$(2m)(n)\equiv 1$and $2m,n<\frac{p}{2}$? That's not the final one.when $p=37$,we have $7\times 16\equiv 1\pmod{37}$

I've just run a C++ program and it says $p=3,5,7,13$

We can consider that $p>10$, small primes could be easily checked. Some facts: 1) $p-2$ is prime otherwise $p-2=s\cdot t$ with $s,t>1$, so $\frac{p-s}{2}\cdot \frac{p-2}{s}\equiv 1\pmod{p}$. 2) $\frac{p+1}{2}$ is prime otherwise $p+1=2\cdot s\cdot t$ with $s,t>1$, so $\frac{p+1}{2s}\cdot \frac{p+1}{2t} \equiv 1\pmod{p}$. Also I can prove that $p$ is equal to $2^{s+1}+1$ or $3\cdot 2^{s+1}+1$ with positive integer $s$.

pavel kozlov wrote: Also I can prove that $p$ is equal to $2^{s+1}+1$ or $3\cdot 2^{s+1}+1$ with positive integer $s$. Can you post its proof?

MathLover_ZJ wrote: pavel kozlov wrote: Also I can prove that $p$ is equal to $2^{s+1}+1$ or $3\cdot 2^{s+1}+1$ with positive integer $s$. Can you post its proof? Let $p=2^mu+1$ with $u$ odd and $m\geq 1$ (if $p>2$). We then have $2^{m+1}\frac{p-u}{2}\equiv -2^mu\equiv 1\pmod{p}$. The only case left are those when one of the two factors is $>p/2$. The second factor is always an integer (because $p\equiv u\equiv 1\pmod{2}$) and is $p/2$. The first factor is $>p/2$ iff $2^{m+2}>2^mu+1\iff (4-u)2^m>1$. Clearly, this can be true only if $u<4$. So we basically have three cases left: -$p=3\cdot 2^m+1$ -$p=2\cdot 2^m+1$, which can be reconduced to $2^m+1$ -$p=2^m+1$ In the third case, as in post #8, $\frac{p+1}{2}=2^{m-1}+1$ has to be prime as well. However , since both are Fermat primes, we must have at both $m$ and $m-1$ are powers of $2$, meaning they must be $1$ and $2$. This leads us to $p=2^2+1=5$, which indeed works (but is anyway $<10$ so we would have counted it anyway) and no other prime. Thus the only case remaining is $p=3\cdot 2^m+1$. This also leads to $q=3\cdot 2^{m-1}+1$ and $r=3\cdot 2^m-1$ being prime by #8, but I don't yet know how to finish from here.

cadaeibf wrote: In the third case, as in post #8, $\frac{p+1}{2}=2^{m-1}+1$ has to be prime as well. However , since both are Fermat primes, we must have at both $m$ and $m-1$ are powers of $2$, meaning they must be $1$ and $2$. This leads us to $p=2^2+1=5$, which indeed works (but is anyway $<10$ so we would have counted it anyway) and no other prime. Good job! One can try to finish the case $p=3\cdot 2^{s+1}+1$ modulo $7$. Let us consider 3 cases: 1) If $2^s\equiv 1 \pmod 7$, then $p\equiv 3\cdot 2 +1 \equiv 0 \pmod 7$, so $p=7$. 2) If $2^s\equiv 2 \pmod 7$, then $q\equiv 3\cdot 2 +1 \equiv 0 \pmod 7$, so $q=7$ and $p=13$. 3) If $2^s\equiv 4 \pmod 7$, then $p\equiv 3\cdot 8 +1 \equiv 4 \pmod 7$, so $5p+1$ is divisible by $7$ and by $3$ too, so if $p>42$ then $21\cdot \frac{5p+1}{21} \equiv 1$ gives us a counterexample. But $25$ is the only number of kind $3\cdot 2^{3t} +1$ that less than $42$, it is not prime.

Obviously the function $f: \{1, 2, \dots, p-1\}\to \{1, 2, \dots, p-1\}$ defined by $x\to \frac{1}{x}\pmod p$ is a bijection. We kill $p>80$ as follows: notice that $2\cdot \frac{p+1}{2}=\frac{p-1}{2}\cdot p-2 \equiv 1 \pmod p$, so $|n-f(n)|\neq 1, 2$ (this is actually for $p>7$). This is because the only way that $|n-f(n)|=1, 2$ involves $n$ or $f(n)$ being $\frac{p-1}{2}$ or $\frac{p+1}{2}$, but we just checked that this cannot happen. We hence have the following to results. Claim 1: $p\equiv 2, 3 \pmod 5$ Pf: The equation $$x(x+1)\equiv 1\pmod p\Longleftrightarrow (2x+1)^2\equiv 5 \pmod p$$has no solution, so by quadratic reciprocity $$-1=\left(\frac{5}{p}\right)=(-1)^{\frac{5-1}{2}\cdot\frac{p-1}{2}}\left(\frac{p}{5}\right)=\left(\frac{p}{5}\right)\implies p\equiv 2, 3\pmod 5$$$\blacksquare$ Claim 2: $p\equiv 3, 5 \pmod 8$ Pf: The equation $$x(x+2)\equiv 1\pmod 8 \Longleftrightarrow (x+1)^2\equiv 2\pmod 8$$has no solution, so $\left(\frac{2}{p}\right)=-1$. By the second supplement law of quadratic reciprocity, the claim follows. $\blacksquare$ - If $p\equiv 2\pmod 5$, then $5\vert 2p+1$, so $f(5)=\frac{2p+1}{5}$, a contradiction since $5, \frac{2p+1}{5}<\frac{p}{2}$. - If $p\equiv 3\pmod 5$ and $p\equiv 3\pmod 8$, $40\vert 13p+1$ so $f(40)=\frac{13p+1}{40}$, a contradiction since $40, \frac{13p+1}{40}<\frac{p}{2}$ - If $p\equiv 3\pmod 5$ and $p\equiv 5\pmod 8$, $40\vert 3p+1$ so $f(40)=\frac{3p+1}{40}$, a contradcition since $40, \frac{3p+1}{40}<\frac{p}{2}$. We must now check for finitely many $p$, namely $$p\in\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79\}$$ The solution set ends up being $p\in\{5, 7, 13\}$. $\square$ Remark: The process of checking these edge cases can be agilized by noticing that $\frac{p+1}{2}$ has to be prime. We then just have to disgard $37, 61$ and $73$. $37$ fails because $37\vert 7\cdot 16-1$, $61$ fails because of claim 1 and $73$ because of claim 2.

Ru83n05 wrote: Obviously the function $f: \{1, 2, \dots, p-1\}\to \{1, 2, \dots, p-1\}$ defined by $x\to \frac{1}{x}\pmod p$ is a bijection. We kill $p>80$ as follows: notice that $2\cdot \frac{p+1}{2}=\frac{p-1}{2}\cdot p-2 \equiv 1 \pmod p$, so $|n-f(n)|\geq 3$ (this is actually for $p>7$). Could you please clarify this case.

[anyway, to all of the above posts $p=2,3$ also vacuously work, since the condition are satisfied for all possible $a$ (of which there are none]

pavel kozlov wrote: Ru83n05 wrote: Obviously the function $f: \{1, 2, \dots, p-1\}\to \{1, 2, \dots, p-1\}$ defined by $x\to \frac{1}{x}\pmod p$ is a bijection. We kill $p>80$ as follows: notice that $2\cdot \frac{p+1}{2}=\frac{p-1}{2}\cdot p-2 \equiv 1 \pmod p$, so $|n-f(n)|\geq 3$ (this is actually for $p>7$). Could you please clarify this case. Ok I should change it to $|n-f(n)|\neq 1, 2$, sorry :v. The only way that $|n-f(n)|=1, 2$ involves $n$ being $\frac{p-1}{2}$ or $\frac{p+1}{2}$, but we just checked that this cannot happen.

Ru83n05 wrote: Ok I should change it to $|n-f(n)|\neq 1, 2$, sorry :v. What do you do in the case it never happens?

pavel kozlov wrote: Ru83n05 wrote: Ok I should change it to $|n-f(n)|\neq 1, 2$, sorry :v. What do you do in the case it never happens? $|n-f(n)|\neq 1$ means you can't for example have $f(n)=n+1$ which would imply $n(n+1)\equiv 1$, and similarly for $|n-f(n)|\neq 2$.

cadaeibf wrote: pavel kozlov wrote: Ru83n05 wrote: Ok I should change it to $|n-f(n)|\neq 1, 2$, sorry :v. What do you do in the case it never happens? $|n-f(n)|\neq 1$ means you can't for example have $f(n)=n+1$ which would imply $n(n+1)\equiv 1$, and similarly for $|n-f(n)|\neq 2$. I see, but how it solves the problem for $p>80$?

old komal problem

Can you give source? laikhanhhoang_3011 wrote: old komal problem

If p <23 ,only p=5,7,13 are satisfied the condition. Then we consider ${p \geq 23}$ First ,$ {p \equiv 1 (mod 3)} $ .Otherwise ${p\equiv 2(mod 3) \Rightarrow \frac{p+1}{3} \cdot 3 \equiv 1 (mod p)}$ contradiction! Second ,${p \equiv 1 (mod 5)}$ .Otherwise ${p \equiv 2,3,4 (mod 5)}$ .If ${p \equiv 2 (mod 5) \Rightarrow \frac {2p+1}{5} \cdot 5 \equiv 1 (mod p)}$ contradition! . If ${p \equiv 4 (mod 5) \Rightarrow \frac {p+1}{5} \cdot 5 \equiv 1 (mod p)}$ contradition! . If ${p \equiv 3 (mod 5) \Rightarrow p \equiv 3 (mod 10) \Rightarrow \frac {3p+1}{10} \cdot 10 \equiv 1 (mod p)}$ contradiction ! Third , let ${2^t \leq \frac {p-1}{2} <2^{t+1} }$ ,then we prove that ${p \equiv 1 (mod 2^t) }$ by conduction. It is easy to find ${p \equiv 1 (mod 2)}$ , assuming that ${p \equiv 1 (mod 2^s) (s<t)}$, then we prove ${p \equiv 1 (mod 2^{s+1}) }$. Otherwise ${p \equiv 2^s+1 (mod 2^{s+1}) \because 2^{s+1} \cdot x \equiv 1 (mod p) \Rightarrow x= \frac {kp+1}{2^{s+1}} ,(k >2^s)}$ let ${k=2^s+r (1 \leq r \geq 2^s-1) \Rightarrow kp+1 \equiv (2^s+r)(2^s+1)+1 \equiv (r+1)(2^s+1) \not= 0 (mod 2^{s+1})}$ contradiction! ${\Rightarrow p \equiv 1 (mod 2^t \cdot 3 \cdot 5) \Rightarrow p \geq 2^t \cdot 3 \cdot 5 +1 >2^{t+1} \cdot 3 >p }$ contradiction! So ,only p=5,7,13 are satisfied the condition.

I wonder how could it be a problem from Kazakhstan junior olympiad?!

I wonder that too...maybe there's an easy solution?

Assume that $p>20$ ıf $p\equiv 2 \pmod5$ $\frac{p-5}{2}.\frac{p-2}{5} \equiv 1 $ if $p\equiv 1 \pmod5$ $\frac{p-5}{2}.\frac{2p-2}{5} \equiv 1 $ if $p\equiv 4 \pmod5$ $10.\frac{p+1}{10}\equiv 1$ if $p\equiv 3 \pmod5$ $10\frac{3p+1}{10}\equiv 1 $ so we are done.