Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in $\LaTeX$. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

there seems to be one here who wants to solve it... i didn't really want to post the solution i found in oberwolfach because it's so long... but here it goes: Consider the 8 given points as the vertices of a $K_8$ and color an edge $AB$ in color 1 if $AB^2$ is not divisible by $p$, in color 2 if $AB^2$ is divisible by $p$, but not by $p^{n+1}$ and in color 3 if $AB^2$ is divisible by $p^{n+1}$. If the statement is wrong, there is no triangle of color (3,3,3). Let $A,B$ be two of the 8 points, let $O$ be the center of the circle and let $R=\frac{p^n}2$. We know by the cosine theorem that $AB^2=2R^2(1-\cos \gamma)$ where $\gamma=\sphericalangle AOB$. Therefore $\cos \gamma$ is a rational number which has at most $p^{2n}$ in the denominator. Now, add an additional point $C$ and let $\alpha=\sphericalangle BOC, \beta=\sphericalangle COA$. We know that $2\cos \alpha \cos \beta \cos \gamma=1-\cos ^2 \alpha - \cos ^2 \beta - \cos ^2 \gamma$. Therefore $v_p(\cos \alpha) + v_p(\cos \beta) + v_p(\cos \gamma) \geq 2\min \{ v_p(\cos \alpha), v_p(\cos \beta), v_p(\cos \gamma) \}$ (here $v_p(x)$ denotes the $p$-adic valuation; it is clear that $v_p(\cos \alpha) \leq 0$). Wlog assume that $v_p(\cos \alpha)$ is minimal. then we know that $v_p(\cos \beta) + v_p(\cos \gamma)\geq v_p(\cos \alpha)$; if $v_p(\cos \beta),v_p(\cos \gamma) > v_p(\cos \alpha)$ we even have equality. This shows that triangles of color (1,1,1), (1,1,2), (2,2,2) and (1,3,3) may not exist. If there were no triangles of color (1,1,3), every triangle would contain an edge of color 2 and an edge of color 1 or 3 - this is impossible as there has to be in conclusion a triangle consisting only of color 2 or only of color 1 or 3(this was true even in any 6-element subset of the 8 points); therefore we have a triangle $ABC$ of color (1,1,3). Then wlog we have $v_p(\cos \alpha)=v_p(\cos \beta)=-2n$; it follows that $v_p(\cos \gamma)=0$, therefore $\cos \gamma$ is an integer. it may not be 1; therefore it is 0 or -1; but 0 is not possible since in that case we had $AB^2=\frac{p^{2n}}2$ which is not an integer. Therefore $AB$ is a diameter; summing up, all triangles of color (1,1,3) include a diameter. From now on, fix a diameter $AB$ and $C$ such that $AC$ and $BC$ have color 1. If for all $D,E\neq A,B$ we had that $DE$ is of color 2 or 3, there would necessarily be a triangle of color (2,2,2) or color (3,3,3), contradiction. Therefore we have some $DE$ of color 1. If, say $D=C$, then $ACE$ is of color (1,1,*), therefore of color (1,1,3), which means that AE is a diameter and it follows that $E=B$, contradiction; analogously for $E=C$. To finish, consider the cyclic quadrilateral $ACDE$. By the ptolemaus theorem, we know that $\pm AC\cdot DE \pm AE\cdot CD \pm AD\cdot CE=0$ with suitably chosen signs. This implies $(- AC^2\cdot DE^2 + AE^2\cdot CD^2 + AD^2\cdot CE^2)^2=4AD^2\cdot AE^2\cdot CD^2\cdot CE^2$. Now, look at both sides $\mod p$ to get a contradiction(remember that we just showed that $v_p(CD^2)>0, v_p(CE^2)>0$; but we know that $v_p(AC^2\cdot DE^2)=0$ and $v_p(AD^2\cdot CD^2)>0$ as the triangle $ACD$ may not be of color (1,1,1)). QED

Sorry for possible nonsense.. Define $exp(a)$ be the biggest power of $p$ dividing the integer $a$ ($exp(0)=+\infty$). For rational $\frac ab$ define ${exp(\frac ab})=exp(a)-exp(b)$. It's obvious that ${exp(a+b)\geq min\{exp(a),exp(b)}$ and if $exp(a)\neq exp(b)$ then ${exp(a+b)=min\{exp(a),exp(b)}$. We say that $u|v$ if $u\neq 0$ and ${exp(\frac vu})\geq 0$. Now let's pass to the solution of the problem. Let the $8$ points be $A_1, \cdots, A_8$ have coordinates $u_i, v_i$ and let the center have rational coordinates $s,t$. Define $x_i=u_i-s, y_i=v_i-t$. Then $x_i^2+y_i^2=\frac {p^{2n}}{4}$. IF $exp(x_i)\geq n$ then we have $exp(y_i^2)=exp(\frac {p^{2n}}4-x_i^2)\geq 2n$ so $exp(y_i)\geq 2n$. However we cannot have three points with this property, because they would form then a desired triangle. Thus there are at most two points with this property and removing them there are at least $6$ points left with $exp(x_i)<n$. Let $r_i=exp(x_i)<n$. It's obvious that $exp(y_i)=r_i$. Now $A_iA_j^2=(x_i-x_j)^2+(y_i-y_j)^2=x_i^2+x_j^2+y_i^2+y_j^2-2(x_ix_j+y_iy_j)$ $=\frac {p^{2n}}2-2(x_ix_j+y_iy_j)$. In order $A_iA_j^2$ to be divisible by $p^{n+1}$ it's nesessary and sufficient to have $exp(x_ix_j+y_iy_j)\geq n+1$. Let's connect two points $A_i, A_j$ with an edge iff $p^{n+1}|A_iA_j^2$. We claim that from any three points, there is at least one edge connecting them. Let them be, WLOG $A_1,A_2,A_3$ and suppose this fails. Then $exp(x_1x_2+y_1y_2)\leq n$. However $\frac {(x_1x_2+y_1y_2)(x_1y_2+x_2y_1)}{y_1y_2}=\frac {(x_1^2+y_1^2)x_2y_2+(x_2^2+y_2^2)x_1y_1}{y_1y_2}=\frac {\frac \frac {p^{2n}}(x_1y_1+x_2y_2) }{4y_1y_2}$. Now we see that the greatest power of $p$ dividing this number is at least $2n+2 min\{r_1,r_2)-r_1-r_2=2n-|r_1-r_2|\geq n+1$ because $0\leq r_1,r_2\leq n-1$. Since $exp(x_1x_2+y_1y_2)\leq n$ it follows that $exp(\frac {x_1y_2+x_2y_1}{y_1y_2})\geq 1$ or $exp(\frac {x_1}{y_1}+\frac {x_2}{y_2})\geq 1$. Analogously we get $exp(\frac {x_1}{y_1}+\frac {x_3}{y_3})\geq 1$ and $exp(\frac {x_3}{y_3}+\frac {x_2}{y_2})\geq 1$. Now adding the first two relations, substracting the second and dividing by $2$ we get $exp(\frac {x_1}{y_1})\geq 1$ which is impossible since $exp(\frac {x_1}{y_1})=r_1-r_1=0$. This contradiction guarantees the claim. Now, by Ramsey's Theorem in our graph having at least $6$ vertices, we must have either a $K_3$, or a $\overline{K_3}$. The last is impossible due to the claim hence there is a triangle. QED

From IMO shortlist 2004 booklet.. Solution. A point with integer coordinates will be called an integer point. It is clear that if $A$ and~$B$ are integer points then $AB^{2}$ is a positive integer. The highest power of the given prime $p$ dividing $AB^{2}$ is denoted by $\alpha (AB)$ (i. e. ${\alpha (AB)=k}$ if $AB^{2}$ is divisible by $p^{k}$ but not by $p^{k+1}$). Note also that if $S$ is the area of a triangle with vertices at integer points, then $2S$ is an integer. The solution below is based on the following formulas involving the area $S$ of a triangle $ABC$ whose circumcircle has diameter $p^{n}$: \begin{align*} 2AB^{2}\cdot BC^{2}+2BC^{2}\cdot CA^{2}+2CA^{2}\cdot AB^{2}-AB^{4}-BC^{4}-CA^{4}=16S^{2}, \tag{1} \\ AB^{2}\cdot BC^{2}\cdot CA^{2}=(2S)^{2}p^{2n}. \tag{2} \end{align*} Lemma. Let $A,B$ and $C$ be integer points on a circle of diameter $p^{n}$. Then either at least one of ${\alpha (AB),\alpha (BC),\alpha (CA)}$ is greater than $n$, or ${\alpha (AB),\alpha (BC),\alpha (CA)}$ are the numbers $n,n,0$, taken in some order. Proof. Let ${m\!=\!\min \{\alpha (AB),\alpha (BC),\alpha (CA)\}}$. By (1), $p^{2m}$ divides $(2S)^{2}$, so $p^{m}$ divides $2S$. Combined with (2), this implies ${\alpha (AB)+\alpha (BC)+\alpha (CA)\geq 2m+2n}$. Let ${\alpha (AB)\leq n}$, ${\alpha (BC)\leq n}$, ${\alpha (CA)\leq n}$. Then ${\alpha (AB)+\alpha (BC)+\alpha (CA)\leq m+2n}$, and hence ${2m+2n\leq m+2n}$, which means that ${m=0}$. So one of ${\alpha (AB),\alpha (BC),\alpha (CA)}$ is 0, and it is clear that the other two are equal to $n$. Next, we prove that among every four integer points on a circle of diameter $p^{n}$ there exist two, $P$ and $Q$, such that ${\alpha (PQ)\geq n+1}$}. Assume that this is false for some points $A,B,C,D$ occurring on such a circle in this order. The lemma implies that $\alpha $ takes on value $0$ for two segments determined by $A,B,C,D$ without common endpoints, and value $n$ for the remaining 4 segments. So we may assume that there are positive integers $a,b,c,d,e,f$ not divisible by $p$ such that ${AB^{2}=a}$, ${CD^{2}=c}$, ${BC^{2}=bp^{n}}$, ${DA^{2}=dp^{n}}$, ${AC^{2}=ep^{n}}$, ${BD^{2}=fp^{n}}$. Then Ptolemy's theorem for the inscribed quadrilateral $ABCD$ yields ${\sqrt{ac}=p^{n}(\sqrt{ef}-\sqrt{bd})}$. Squaring both sides, we obtain ${ac=p^{2n}(\sqrt{ef}-\sqrt{bd})^{2}}$, so ${(\sqrt{ef}-\sqrt{bd})^{2}}$ is rational. However, ${(\sqrt{ef}-\sqrt{bd})^{2}=ef+bd-2\sqrt{bdef}}$, and this can be a rational number only if $\sqrt{bdef}$ is an integer. But then ${(\sqrt{ef}-\sqrt{bd})^{2}}$ itself is an integer, and ${ac=p^{2n}(\sqrt{ef}-\sqrt{bd})^{2}}$ implies that $p^{2n}$ divides $ac$, a contradiction. Now label the eight given points $A_1,A_2,\dots,A_8$, draw the line segments they determine, and color black all segments $A_iA_j$ such that ${\alpha(A_iA_j)\ge n+1}$. The number of black segments with endpoint $A_i$ will be called the degree of $A_i$. Case 1. There is a point of degree at most 1, say $A_8$. Then at least 6 of the remaining points are not connected to $A_8$ by a black segment. Let such points be $A_1,A_2,\dots,A_6$. It is a popular fact that if the line segments joining 6 points are colored in two colors then this coloring contains a triangle with sides of the same color. Here this implies that either some triangle with vertices among $A_1,A_2,\dots,A_6$ has three black sides, and the claim follows, or some triangle has three uncolored sides, say $A_1A_2A_3$. But in the latter case the four points $A_1,A_2,A_3,A_8$ do not determine any black segment, a contradiction. Case 2. All points have degree 2. Clearly, then the black segments partition into cycles. The proof is complete if there is a black cycle of length 3, so let all cycles have length at least 4. Then there are two possibilities: two 4-cycles, say $A_1A_2A_3A_4$ and $A_5A_6A_7A_8$, or one 8-cycle, $A_1A_2A_3A_4A_5A_6A_7A_8$. In both cases, the four points $A_1,A_3,A_5,A_7$ do not determine any black segment, a contradiction. Case 3. There is a point of degree at least 3, say $A_1$. Suppose that $A_1A_2$, $A_1A_3$ and $A_1A_4$ are black. We claim that at least one segment among~$A_2A_3$, $A_3A_4$, $A_4A_2$ is black, which will complete the solution. If not, by the lemma $\alpha(A_2A_3),\alpha(A_3A_4)\alpha(A_4A_1)$ are $n,n,0$, taken in some order. Assuming that ${\alpha(A_2A_3)=0}$, denote by $S $ the area of the triangle $A_1A_2A_3$ and look again at the formulas (1) and (2). By (1), $2S$ is not divisible by $p $. On the other hand, since ${\alpha(A_1A_2)\ge n+1}$ and ${\alpha(A_1A_3)\ge n+1}$, (2) shows that $2S$ is divisible by $p$, a contradiction. Comment by the proposer. Let $p$ be a prime of the form ${p=4k+1}$. Consider the circle with diameter $OA$, where $O(0,0)$ and $A(p^{n},0)$. For ${i=1,\dots ,n}$ there are integers $x_{i},y_{i}$ not divisible by $p$ such that ${p^{i}=x_{i}^{2}+y_{i}^{2}}$. It is easy to check that $(p^{n- i}x_{i}^{2},p^{n-i}x_{i}y_{i})$ is an integer point on the given circle, ${i=1,\dots ,n}$. Therefore eight points on a circle with diameter $p^{n}$ do exist for large $n$.

If this proof is correct, then it seems that the result actually holds when there are 7 points instead of 8. (This is essentially a strengthened version of iura's solution.)

Here's another proof for $m=7$ points (which I believe is optimal when $p\equiv1\pmod4$). Let the $m$ points be $(x_k,y_k)\in\mathbb{Z}^2$ ($1\le k\le m$), $d_{j,k}$ be the distance between $(x_j,y_j),(x_k,y_k)$, and the center of the circle be $(X,Y)$, so $(x_k-X)^2 + (y_k-Y)^2 = p^{2n}/4$ for every $k$. Since $m\ge3$, $X,Y$ must be rational. If $p\equiv 3\pmod4$, we must have $v_p(x_k-X),v_p(y_k-Y) \ge n$ for all $k$, so any three points will work (note that $2n\ge n+1$). Otherwise, if $p\equiv1\pmod4$, take integers $a,b$ with $p = a^2+b^2$. From now on, we work in $\mathbb{Q}[i]$; since $\mathbb{Z}[i]$ is a UFD, we can define, for any fixed prime $q\in\mathbb{Z}[i]$, a $q$-adic valuation $v_q$ on $\mathbb{Q}[i]$ satisfying $v_q(r/s) = v_q(r) - v_q(s)$ for any $r,s\in \mathbb{Z}[i]$ (where for $x\in \mathbb{Z}[i]$, $v_q(x)$ is the largest $t\ge0$ with $q^t\mid x$)---observe that each element of $\mathbb{Q}[i]$ can be written in the form $r/s$ for some $r\in\mathbb{Z}[i]$ and $s\in\mathbb{Z}$. Define $z_k = x_k + y_k i$, $Z = X+Yi$, and the primes $\alpha = a+bi$, $\beta = \overline{\alpha} = a-bi$. Then $p=\alpha\beta$, $(z_k-Z)(\overline{z_k-Z}) = p^{2n}/4$, and $v_\alpha(z_k-Z) = v_\beta(\overline{z_k-Z})$ by conjugation (the same holds with $\alpha,\beta$ swapped), so \[ v_\alpha(z_k-Z)+v_\beta(z_k-Z) = v_\beta(\overline{z_k-Z}) + v_\beta(z_k-Z) = v_\beta(p^{2n}/4) = 2n \]for each $k$. Now note that if $v_\alpha(z_k-Z)<0$ for some $k$, then $v_\alpha(z_j-Z) = v_\alpha((z_j-z_k)+(z_k-Z)) = v_\alpha(z_k-Z)$ for all $j\ne k$, since $z_j-z_k = (x_j-x_k)+(y_j-y_k)i\in\mathbb{Z}[i]$ implies $v_\alpha(z_j-z_k) \ge 0$. (Of course, the analogous statement for $\beta$ also holds.) Hence by pigeonhole, there must exist 3 indices $l_1,l_2,l_3$ with \[ v_\alpha(z_{l_1}-Z) \le v_\alpha(z_{l_2}-Z) \le v_\alpha(z_{l_3}-Z) < v_\alpha(z_{l_1}-Z)+n. \](The "nontrivial case" is when $0\le v_\alpha(z_k-Z) = 2n-v_\beta(z_k-Z)\le 2n$ for all $k$.) Then \[ v_\alpha(z_{l_j} - z_{l_k}) \ge \min(v_\alpha(z_{l_j}-Z),v_\alpha(z_{l_k}-Z)) \ge v_\alpha(z_{l_1}-Z)\]and similarly, \[ v_\beta(z_{l_j} - z_{l_k}) \ge v_\beta(z_{l_3}-Z) = 2n - v_\alpha(z_{l_3}-Z) \ge n+1-v_\alpha(z_{l_1}-Z).\]But $v_\beta(\overline{z_{l_j}-z_{l_k}}) = v_\alpha(z_{l_j} - z_{l_k})$ and $v_\alpha(\overline{z_{l_j}-z_{l_k}}) = v_\beta(z_{l_j} - z_{l_k})$ by conjugation, so \[ v_\alpha(d_{j,k}^2) = v_\alpha(z_{l_j}-z_{l_k}) + v_\alpha(\overline{z_{l_j}-z_{l_k}}) = v_\alpha(z_{l_j}-z_{l_k}) + v_\beta(z_{l_j} - z_{l_k}) \ge n+1. \]We similarly obtain $v_\beta(d_{j,k}^2) \ge n+1$, so because $d_{j,k}^2\in\mathbb{Z}\subset\mathbb{Z}[i]$, we must have $\alpha^{n+1},\beta^{n+1}\mid d_{j,k}^2$. Thus $p^{n+1} = \alpha^{n+1}\beta^{n+1}\mid d_{j,k}^2$ (as $\alpha,\beta$ are distinct primes and therefore coprime), and we're done. (More precisely, the rational number $d_{j,k}^2/p^{n+1}$ must be an algebraic integer and thus an integer itself.)

What a wonderful problem; here is a solution similar in spirit to the above. The $p \equiv 3\pmod 4$ case is trivial so assume henceforth that $p\equiv 1\pmod 4$. Note that the center $(c,d)$ is at half-integer coordinates, so a homothety centered at $0$ with ratio $2$ maps the circle to one centered at an integer and with radius $p^n$, then shift so that the center is $(0,0)$ and toss on the complex plane. Work in $\mathbb Z[i]$ with norm $N(z) = |z|^2$. Take Gaussian integer $s = x+yi$, $t = u+vi$ lying on the circle $N(z) = p^{2n}$. We see that $N(s-t) = N(s)+N(t) - 2 (xu+vy)$ by properties of the dot product, so since $p^{n+1}\mid N(s)+N(t)$, $p^{n+1}\mid N(s-t)$ if and only if $p^{n+1} \mid 2(xu+vy) = 2\Re(s\overline t) = s\overline t + t\overline s) = p^{2n} \left(\frac st + \frac ts\right)$. On the other hand, the last term is real and so is divisible by $p$ if and only if \[ p^{2-2n} \mid N\left(\frac st + \frac ts\right) = N(s^2+t^2)/N(st) \iff p^{2n+2}\mid N(s^2+t^2). \]Next, recall that $p = u^2+v^2$ by Christmas; so $(u+vi)(u-vi) = p$, and $r = u+vi$, $s = v+ui$ have prime norm, ergo they are also prime in $\mathbb Z[i]$. By unique factorization of $\mathbb Z[i]$ this means that $(u,v)$ is (up to permutation/negation) the only pair such that $u^2+v^2 = p$. We now show that if $N(s) = p^k$, then $s = r^\ell t^{k-\ell} u$ for some integer $\ell \in [0,k]$ and unit $u \in \{\pm 1, \pm i\}$. Indeed, it suffices to show that if $N(s) = p^k$, $k > 1$, then $s$ is not prime. Indeed, say $s = a+bi$ and suppose by contradiction that it is prime; then $a,b$ are both not divisible by $p$, or else $u+vi\mid p\mid s$, contradiction. Otherwise, we have that, modulo $p$, $ub = va$ or $vb = ua$. In the first case, $a/b = u/v = -v/u\pmod p$, so $p\mid au+vb$, and so if $c = (au+vb)/p$, $d = \frac{bu-av}{p}$, then $(u+vi)(c+di) = a+bi$. Similarly in the other case we can find $c,d$ with $(v+ui)(c+di) = a+bi$, so either way $s$ is not prime since $N(v+ui) = N(u+vi) = p$, and so $N(c+di) > 1$. Now, we note that if $a = r^{\ell}t^{2n-\ell}u$, $b = r^{m} t^{2n-m} v$ for units $u,v$ and $\ell \leq m$, then \[ N(a^2+b^2) = N\left(r^{2\ell} t^{4n-2\ell} + r^{2m} t^{4n-2m}\right) = N(r^{2\ell} t^{4n-2m})N(t^{2m-2\ell} + r^{2m-2\ell}) \geq (4n-2m+2\ell). \]This is at least $2n+2$ when $m \leq \ell+(n-1)$. Now, say that our points have $r$-exponent $r_1\leq \cdots \leq r_8$. If $r_{k+2} \leq r_k + (n-1)$ for any $n$ we are done. Otherwise, we would have $r_{k+2} \geq r_k + n$ for all $k$, but then $r_5 \geq r_1 + 2n \geq 2n$, so $r_5 = r_6 = r_7 = 2n$ and we are done again. (Note that we do not use $r_8$, which is as observed above.)

My solution (which holds for $7$ points too): First of all, we double the coordinates of each of the points, and the squares of distances of the newly changed points is $4$ times the square of the previous corresponding respective distance, so it is equivalent to the original problem if we find three points here. We break down the problem into two cases, proving each case with using at most $7$ of the $8$ vertices. Consider the centre of the circle $(a,b)$. $(a,b)$ is clearly rational. Suppose $c$ is the smallest number such that upon scaling the coordinates by $c$, the coordinates of the centre $(ac,bc)$ are integer coordinates. Case $1$: $v_p(c)>0$. Let $v_p(c)=t$. Note that this can happen only in the case $p=4s+1$ for some $s$, since if $p=4s+3$ and $x^2+y^2$ is a multiple of $p^{n}$ then $x^2,y^2$ are multiples of $p^n$ themselves. Thus, if we shift the points so that the centre of the circle is now $0,0$(it preserves distance between the points), any of the rescaled chosen points is of the form $k,l$ such that $k,l$ are integers with $k^2+l^2=c^2*p^{2n}$. So, we need to find a triangle of $3$ chosen vertices such that $p^{n+1+2t}$ divides all of the sides of the triangle. We claim that we can find $3$ such points among any $5$ points for this case. Sketch of proof: Using Pell equations one can show that there exists a unique unordered pair $(r,s)$ of co-prime integers for which $p^d=r^2+s^2$, for any positive integer $d$, and any prime of the form $p=4k+1$.Thus, one can show from here, that if two integers $k^2$ and $l^2$ satisfy that $p^d|k^2+l^2$ and $k,l$ are not multiples of $p$ then the ordered pair $(k,l)$ is either congruent to $(rq,sq)$ mod $p^d$ for some integer $q$, or it is congruent to $(sq,rq)$ for some integer $q$. Note that if $(k,l)$ is congruent to $(rq,sq)$ mod $p^d$ then it isn't congruent mod $p^d$ to any pair of the form $(sq,rq)$ which we can show by mod $p$ things.( We will call this as Lemma 1. This lemma is the key lemma which helps us to solve the problem.) Accordingly, we divide such pairs $(k,l)$ into either $rs$ type or $sr$ type, taking $d=2n+2t$ here. Since there are at least $5$ points, by PHP, three of the points are of the same type. Now by using definitions we can trivially see that the square of sides of the three triangles formed by three points of the same type, are all divisible by $p^{2n+2t}$, which proves this case. Case $2$: Now we come to case $2$, where $v_p(c)=0$. We again do the shifting of the centre $(ac,bc)$ to $0,0$ so any of the chosen rescaled shifted points satisfies that it is of the form $k,l$ for integers $k,l$ with $k^2+l^2=c^2p^{2n}$. We show that for this case we can make the suitable choice for the $3$ points from any $7$ of the given points. This case is again trivial for $p=4s+3$ due to the observation noted above, so we assume $p=4s+1$ for some $s$. Sketch of proof: If at least three of the $7$ points satisfy $min(v_p(k), v_p(l)) \geq \frac{n+1}{2}$ then we can choose those $3$ points and we are trivially done. So there are at most $2$ points satisfying that both $k,l$ are multiples of $p^{\lceil{\frac{n+1}{2}}\rceil}$. Now, suppose there are at least $5$ points satisfying $min(v_p(k),v_p(l)) \leq \frac{n}{2}$, then we can use the techniques used in Lemma $1$, take $d=n+1$, divide into types again and finish in a similar way as case $1$. Thus, we are done as there are at least $7$ chosen points. Proved. P.S.: The exponent $p^{n+1}$ can be strengthened to $p^{\lceil \frac{4n}{3} \rceil}$ for sufficiently large $n$ using the method in my proof and optimizing it, while still using only $7$ points.

Muriatic wrote: Note that the center $(c,d)$ is at half-integer coordinates Why so?

This is quite a nice problem. Let $A_1,A_2,A_3$ be three integer points on the circle, and let $O$ be the center of the circle. Let $d_{ij} = A_iA_j^2$. Claim. Suppose that $v_p(d_{12}) \le v_p(d_{13}) \le v_p(d_{23}) \le n$. Then $v_p(d_{12}) = 0$ and $v_p(d_{13}) = v_p(d_{23}) = n$. Proof. Let $\theta = \angle A_1OA_2$, and suppose $v_p(d_{12}) = k \le n$. Then we have $A_1A_2 = p^n \sin(\theta/2)$, so $d_{12} = p^{2n}\sin^2(\theta/2)$, which implies $2d_{12} = p^{2n}(1-\cos\theta)$. Thus $\cos\theta$ is a rational number, and $v_p(1-\cos\theta) = k-2n$, which is equivalent to $v_p(1+\cos\theta) = k-2n$. By law of cosines, \[d_{12}=d_{13}+d_{23}-2\sqrt{d_{13}d_{23}}\cos\angle A_1A_3A_2.\]Thus \[(d_{12}-d_{13}-d_{23})^2 = 4d_{13}d_{23}\cos^2(\theta/2) = 2d_{13}d_{23}(1+\cos\theta).\]Therefore, \[k-2n = v_p(1+\cos\theta) = 2v_p(d_{12}-d_{13}-d_{23})-v_p(d_{13})-v_p(d_{23}) \ge 2k - 2n\]which happens if and only if $k=0$ and $v_p(d_{13}) = v_p(d_{23}) = n$. $\square$ In the original problem, construct a graph $G$, in which we connect two lattice points $A_1,A_2$ on the circle with a red edge if $v_p(d_{12}) \ge n+1$, and otherwise connect them with a blue edge. Suppose for contradiction that there does not exist a red $K_3$. Lemma. There cannot exist a blue $K_4$. Proof. Suppose that there exist four lattice points $A_1,A_2,A_3,A_4$ on the circle such that $v_p(d_{ij})\le n$ for each $1\le i\ne j\le 4$. Applying the claim, we conclude that a pair of opposite edges (WLOG $d_{12}, d_{34}$) have $v_p$ equal to 0, and the other four edges all have $v_p$ equal to n. But by Ptolemy's theorem, \[(d_{12}d_{34} \pm d_{14}d_{23} \pm d_{13}d_{24})^2 = 4d_{14}d_{23}d_{13}d_{24},\]so taking $v_p$ of both sides gives $n=0$, contradiction. $\square$ Back to the original problem, we divide into cases based on $G$. CASE 1: All vertices are incident to at most 2 red edges. WLOG each vertex is incident to exactly 2 red edges, then the graph is the union of red cycles. Because no red $K_3$ exist, it can only be a cycle of length 8 or two cycles of length 4. Both cases gives a blue $K_4$, contradiction. CASE 2: Some vertex is incident to at least 3 red edges. Since there are no blue $K_4$ or red $K_3$, it is incident to exactly 3 red edges. Thus the $v_p$ of these edge lengths squared is as labeled below: [asy][asy] size(5cm); pair A = (0,0), B = (0,1), C = (1,1), D = (1,0); draw(A--B--C--D--cycle); draw(A--C); draw(B--D); label("$\ge n+1$", (B+C)/2, N); label("$\ge n+1$", (A+B)/2, W); label("$\ge n+1$", (2B+D)/3, N); label("$n$", (2A+C)/3, S); label("$n$", (A+D)/2, S); label("0", (D+C)/2, E); label("$A_1$", A, SW); label("$A_2$", B, NW); label("$A_3$", C, NE); label("$A_4$", D, SE); [/asy][/asy] Consider the triangle $A_2A_3A_4$. By law of cosines, \[(d_{34}-d_{23}-d_{24})^2 = 4d_{23}d_{24}\cos^2(\angle A_3A_2A_4/2) = 2d_{13}d_{23}(1+\cos\angle A_3OA_4).\]The left side has $v_p$ equal to zero. But we also know that $v_p(1+\cos\angle A_3OA_4) = -2n$, so the right side has $v_p$ at least 2, contradiction.

Suppose otherwise. Let the points be $A_1, A_2, \ldots, A_8$, the center of the circle be $O$, and $r = \frac{p^n}{2}$ (the radius of the circle). Note: When I say triangle I mean between three of the eight points. Clearly the square of the side length between any two points is an integer as all the points are lattice points. Notice that $(A_i A_j)^2 = 2r^2(1 - \cos \angle A_i O A_j)$, so $\nu_p(A_i A_j) = 2n + \nu_p(\cos \angle A_i O A_j)$ (for $(A_i A_j)^2$ to be an integer, $\cos \angle A_i O A_j$ is needed to be rational, and thus has a defined $\nu_p$). We see that $p^{n+1} \mid (A_i A_j)^2 $ iff $\nu_p(\cos \angle A_i O A_j ) \ge 1 - n$. Also, $\nu_p(\cos\angle A_i O A_j)) $ must be at least $-2n$ as otherwise $(A_i A_j)^2$ won't be an integer. Let $f(i,j) = \cos(A_i O A_j)$. Clearly $\nu_p(f(i,j)) \ge -2n$. Call a side length bad if its square isn't divisible by $p$ (so essentially $A_iA_j$ where $\nu_p(f(i,j)) = -2n$), ok if it is divisible by $p$ but not $p^{n+1}$, good if it is divisible by $p^{n+1}$ but not $p^{2n}$, and very good if it is divisible by $p^{2n}$. If you consider the triangle $A_i A_j A_k$, the three central angles defined by these points add up to $0$ modulo $2\pi$. Therefore $f(i,j)^2 + f(j,k)^2 + f(k,i)^2 = 2 f(i,j)f(j,k) f(k,i) + 1$. Hence\[2 \min( \nu_p(f(i,j)), \nu_p(f(j,k)), \nu_p(f(k,i))) \le \nu_p(2 f(i,j) f(j,k) f(k,i) + 1) \ \ \ \ \ \ \ \ \ \ \ (1)\]For ease write\[\nu_p(f(i,j)f(j,k)f(k,i)) = \nu_p(f(i,j)) + \nu_p(f(j,k)) + \nu_p(f(k,i)) = g(i,j,k)\]Note that if $g(i,j,k) < 0$, then $(1)$ becomes\[ 2 \min( \nu_p(f(i,j)), \nu_p(f(j,k)), \nu_p(f(k,i))) \le g(i,j,k)\]Claim: We cannot have $\nu_p(f(i,j)) = \nu_p(f(j,k)) = \nu_p(f(k,i)) = -2n$ (essentially we can't have a triangle with all bad sides). Proof: If you did, then the LHS of $(1)$ would be $-4n$ and the RHS of $(1)$ would be $-6n$, absurd. $\square$ Hence every triangle must have a side length that isn't bad. Additionally, by our assumption the problem isn't true, all triangles must have a side that is either bad or ok. Claim: If a triangle has two bad sides (say $A_iA_j$ and $A_jA_k$), then the other side ($A_k A_i$) must satisfy $\nu_p(f(k,i)) \ge 0$ (so it must be a very good side). Proof: Suppose otherwise. Then clearly $f(i,j), f(j,k), f(k,i) \le 0$, so $g(i,j,k) < 0$, so the LHS of $(1)$ is $-4n$ and the RHS of $(1)$ is $g(i,j,k) = -4n + f(k,i)$, so $f(k,i) \ge 0$ for $(1)$ to hold, as desired. $\square$ Claim: If there is only one bad side in a triangle, then there must be one ok side. Proof: Suppose a triangle $A_i A_j A_k$ had exactly one bad side and two sides that were good or very good. We have $\nu_p(f(i,j)^2 + f(j,k)^2 + f(k,i)^2)$ must equal $-4n$, so the RHS of $(1)$ must equal $-4n$. However, it is lower bounded by either $0$ or $(1-n) + (1-n) + (-2n) > -4n$, absurd. $\square$ Claim: No triangle has three ok sides. Proof: Suppose some triangle $A_i A_j A_k$ did. WLOG that $f(i,j)$ has the minimal $\nu_p$ of the three sides and that $\nu_p(f(i,j)) = a$. The LHS equals $2a$ and (since $g(i,j,k) < 0$) the RHS is at most $a + \nu_p(f(j,k)) + \nu_p(f(k,i)) \le a - 2n < 2a$, absurd. $\square$ Claim: No vertex can be part of more than two good sides. Proof: Suppose otherwise. WLOG that $A_1A_2, A_1A_3, A_1A_4$ are all good. Then since no triangle can have two good sides and one bad side or three good sides, $A_2 A_3, A_3A_4, A_2A_4$ are all ok, absurd since there can't be a triangle with all three sides ok. $\square$ Claim: If $A_i A_j$ is an ok side in a triangle that has sides ok, ok, and bad, then $\nu_p(f(i,j)) = -n$. Proof: Suppose otherwise. Let the triangle be $A_i A_j A_k$. Then $\nu_p(f(i,j)^2 + f(j,k)^2 + f(k,i)^2) = -4n$ and the RHS of $(1)$ is at most $-n + \nu_p(f(i,j)) - 2n < -4n$, absurd. $\square$ Claim: If $A_i A_j$ and $A_j A_k$ are ok sides of a triangle that has sides ok, ok, and good, then either $\nu_p(f(i,j)) \ne -n$ or $\nu_p(f(j,k)) =- n$. Proof: Suppose otherwise and $\nu_p(f(i,j)) = \nu_p(f(j,k)) = -n$. Then the LHS of $(1)$ is $-2n$ and the RHS of $(1)$ is at most $-2n - 1$, absurd. $\square$ Claim: No vertex can be part of more than two ok sides. Proof: Suppose $A_1A_2, A_1A_3, A_1A_4$ were all ok. If $A_2A_3$ was bad, then $\nu_p(f(1,2)) = \nu_p(f(1,3)) = -n$, so $A_2A_3, A_2A_4, A_3A_4$ are all bad, contradiction since there can't be a triangle with all sides bad. A similar contradiction arises when $A_3A_4$ or $A_2A_4$ is bad. However, none of $A_2A_3, A_3A_4, A_2A_4$ can be ok, meaning they are all good, absurd since we can't have a triangle with all good sides. $\square$ Now notice that $A_1$ can't be part of more than two ok or good sides, meaning it must be part of at least three bad sides. WLOG $A_1 A_2, A_1A_3, A_1A_4$ are bad. This means that $A_2A_3, A_3A_4, A_2A_4$ are very good, contradiction.