Selection and Training Session

Answer: $\min p=F_4=2^{16}+1$. It is known that Fermat's number $F_4$ is prime. It is easy to verify that $\{\sqrt{F_4}\}<\frac{1}{501}$. Indeed, the latter inequality is equivalent to $\sqrt{2^{16}+1}-256<\frac{1}{501}$, i.e. $\frac{1}{\sqrt{256^2+1}+256}<\frac{1}{501}$ which follows from $\frac{1}{2\cdot 256}<\frac{1}{501}$. So, $F_4$ satisfies the condition of the problem.

Now let $p<F_4$; we prove that the inequality $$\{\sqrt{p}\}<\frac{1}{501}(\ast )$$ is impossible. Indeed, let $n^2<p<(n+1{)}^2$, then $p=n^2+a$ where $1\le a\le 2n$. Then $[\sqrt{p}]=n$, hence $$(\ast )\iff \sqrt{n^2+a}-n<\frac{1}{501}\iff n^2+a<n^2+\frac{2n}{501}+\frac{1}{501^2}\iff n>\frac{501}{2}a-\frac{1}{1002}.$$ If $a\ge 2$ then $n\ge 500\Rightarrow p>F_4$ — a contradiction. So, $a=1$ and $n\ge 251$, i.e. $p\ge 251^2+1$. Note that $251^2+1,251^2+3,251^2+5$ are even, so are not prime. Further, $252^2+1$ is composite, since it is divisible by 5. Finally, show that $254^2+1$ is divisible by 149. We have the following chain of congruences modulo 149: $$254^2+1\equiv (-44{)}^2+1\equiv \frac{132^2+9}{9}\equiv \frac{17^2+9}{9}\equiv \frac{298}{9}\equiv 0(\mathrm{mod}149).$$ Thus $254^2+1$ is composite, so $p=256^2+1$ is minimal possible.