$p$ is a prime or not??

........

Ali3085 wrote: $p$ is a prime or not?? $p$ is a prime number and $0<b<c<\sqrt{p}$.

Dadgarnia wrote: Ali3085 wrote: $p$ is a prime or not?? $p$ is a prime number and $0<b<c<\sqrt{p}$. Thanks. Fixed.

Sadly,this "boring problem"becomes the only one I can not work out in the Day 1 exam.(however I do this at home)Could anyone help me out?

Is there a collection of Iranian RMM TST 2020？Thanks

ummm what is RMM?

@above and @2above https://artofproblemsolving.com/community/c3238_romanian_masters_in_mathematics

thanks very much!

Well probably this gives some clue. https://artofproblemsolving.com/community/c6h1493244p8775392

@above As far as I'm concerned,even showing there exists such triples is much harder than P2and P3.I did also try to prove this,but only found the complex method Maybe we should find an elegant way to prove the existence of the number triples .

https://mp.weixin.qq.com/s/2I-mGoYQkLwz9rDQFUZ0UQ

-Well its the second year of Iran attending RMM and I don't have the last year's tst problems I will ask my teachers if you are interested. -I will post a solution soon.

Problem and solution by Navid Safaie

Attachments:

the further conclution comes from?

@above It is a famous trick. Consider all $ku+v$ where $0 \le u,v \le \lfloor \sqrt{p} \rfloor$, among the $( \lfloor \sqrt{p} \rfloor+1)^2 >p$ numbers there must be two being congruent modulo $p$. Substracting them to get either $k$ or $-k$ lies in $f(R_p)$.

I see。good solution 。

https://artofproblemsolving.com/community/c6h2014075_best_counting_pro exactly=this problem

I hope that someone could have a solution using quadratic residues

Great problem, but I believe that it's heavily misplaced for P1. Let $N$ denote the number of such triples. We will prove a more general fact that $N$ is odd when $p\equiv 1,3\pmod 8$ and is even when $p\equiv 5,7\pmod 8$ (assume that $p>10$). Claim: Let $T$ denote the number of quadruples $(a,b,c,d)$ of integers such that $0<a,b,c,d<\sqrt{p}$ and $p=ad+bc$. Then If $p\equiv 1\pmod 4$, then $T\equiv 4N+2\pmod 8$. If $p\equiv 3\pmod 4$, then $T\equiv 4N\pmod 8$. Proof: We split into four cases. If $a=d, b=c$, then $p=a^2+b^2$. It's well known that there are two such quadruples when $p\equiv 1\pmod 4$, and none at all when $p\equiv 3\pmod 4$. If $a=d$, $b\ne c$, then we have $p=a^2+bc$ so $2N$ quadruples. Similarly, if $a\ne d$, $b=c$, then we have $2N$ quadruples. Finally, if $a\ne d$, $b\ne c$, then we can permute the quadruples in eight ways: $$\begin{array}{c}(a,b,c,d), (d,b,c,a), (a,c,b,d), (d,c,b,a) \\[4pt] (b,a,d,c), (c,a,d,b), (b,d,a,c), (c,d,a,b). \end{array}$$Each such permutations are distinct due to $p$ being prime. Thus the number of quadruples in this case is always a multiple of $8$. Combining all four cases gives the desired result. $\blacksquare$ Hence we are interested in $T\pmod 8$. In fact, we can provide the explicit formula of $T$. Claim: $T=4(\varphi(1)+\varphi(2)+\hdots+\varphi(\lfloor\sqrt{p}\rfloor))-p-1$. Proof: Define the set $$S = \{(a,b)\in\mathbb{Z}^2 : 0<a,b<\sqrt{p}, \gcd(a,b)=1\}$$so that $$|S| = 2(\varphi(1)+\varphi(2)+\hdots+\varphi(\lfloor\sqrt{p}\rfloor))-1.$$For each $(a,b)\in S$, we assign $f(a,b) = ab^{-1}\pmod p$. We need the following facts on $f$. $f$ is injective; this is because if $f(a,b)=f(c,d)$, then $p\mid ad-bc$. Thus, either $ad=bc$ (impossible due to gcd), or $\max\{ad,bc\}\geq p$ (impossible due to size). For any nonzero residue $k\pmod p$, either $k$ or $-k$ is in the image of $f$. This is the famous Thue's lemma, which can be proven easily by Pigeonhole. For any $k$, define $a_k$ to be $1$ if $k$ is in the image of $f$ and $0$ otherwise. We can see that $p\mid ad+bc$ iff $f(a,b) = -f(c,d)$, thus \begin{align*}T &= a_1a_{p-1} + a_2a_{p-2} + \hdots + a_{p-1}a_1 \\ &= \sum_{k=1}^{p-1} (a_k + a_{p-k} - 1) \\ &= 2|S| - (p-1)\end{align*}which implies the claim. $\blacksquare$ Both claims clearly imply the problem; observe that $\varphi(n)$ is even for $n>2$, hence $T\equiv -(p+1)\pmod 8$, and the first claim finishes.