We have $p - 1 \in X$ and $p - \lfloor \sqrt{p} \rfloor^2 \in X$. I believe $(p - \lfloor \sqrt{p} \rfloor^2 ) \mid p - 1$, for any $p$ prime (but I don't have any proof for the moment). EDIT: And in fact for $p>5$ we have $(p - \lfloor \sqrt{p} \rfloor^2 )>1$, so the given numbers would meet the condition.

cyberjoe wrote: I believe $(p-\lfloor\sqrt{p}\rfloor^2)|(p-1)$, for any $p$ prime. Unfortunately, this result is not true. The least counter-example is $p=23$, for which $(p-\lfloor\sqrt{p}\rfloor^2)=23-4^2=7\not|22$. I'll chance offering my own proof. Let $p=n^2+k$. Clearly $0<k<2n$, and $k\ne n$. Let $q=|n-k|$. Clearly $0<q<n$, and $p-q^2=n^2-(n-k)^2+k=k(2n-k+1)$, so $p-q^2$ is a multiple of $p-n^2=k$, and $q<n$ means the two must be distinct.

Do you have solution Duirmuid?

BTW, isn't that the source of the problem : Math. Magazine, Problem 1438, Proposed by David M. Bloom ? (And thanks Diarmuid, I strugled for some time trying to find a proof )

The source was another. After the solution I will tell it to you

Actually, just after I posted my attempt, I came across the source. The solution given was the same as mine (up to notation), except that it took care of the case where $k=1$, which I forgot. This is the link: http://www.kalva.demon.co.uk/balkan/bsoln/bsol962.html

My solution. Let $1\in X$, so $p-n^2=1 \Longleftrightarrow p=n^2+1 $ with $n$ even number. Now $ p-(n-1)^2=n^2+1-(n-1)^2=2n$ so the numbers $ y=p-(n-1)^2=2n $ and $x=p-1^2$ satisfy the conditions required. Let $1\notin X$ and $n=[\sqrt p]$. Now $ n^2+1<p<(n+1)^2$. If we put $x=p-n^2 $ we have $ p<n^2+2n $ and $p \neq n^2+n$. So $ x-n\neq0 $ and $ 0<x<2n $; in other words, $ 0<\left|x-n\right|<n$. Now we choose $ y=p-(x-n)^2\in X $, and we will have that $y=p-n^2+2nx-x^2=x(1+2n-x)$. So $x$ divides $y$.

Let $p=r^2+q$ which $r=[\sqrt p], 1\le q\le2r-1$ if q=1 then r is even we have $p-(r-1)^2|p-1$ which equals to $2r|r^2$ In other case, we prove that $q|r^2+q-s^2$ holds for some s between 1 and r-1. that's equal to $q|(r+s)(r-s)$ which can be easily made by letting one of the factors be q.

Also, this should be moved to the Number Theory Unsolved Problems forum because it's from a contest.

The idea is pretty simple. If $1\in X$ (i.e. $p=n^2+1$), take $x=p-(n-1)^2$ and $y=p-1^2$. If $1 \not \in X$, then let $p=n^2+k$. Now take $x=p-n^2$ and $y=p-(k-n)^2$. (Since $p$ is a prime, so $0<k<2n\implies -n<k-n<n\implies y\in X$.) And if the condition $n^2<p$ is removed, for every $x\in X$ we can find an appropriate $y$ such that $x|y$. (Using the same idea; for $x=p-m^2$, take $y=p-(p-m^2\pm m)^2$ )

What was the motivation?

Motivation can be from trying out small values. Solution: Let $k^2<p<(k+1)^2$ 1. If $p-k^2 = 1$. Choose $x = p-(k-1)^2 = 2k$ and $y = p -1 = k^2$. It's obvious $2k|k^2$ since $k$ is even. 2. If $p-k^2 > 1$. Choose $ x = p-k^2$ and $y =p-(k-x)^2$. It's obvious $x|y$. It's enough to show that $y$ lies on $X$ (and $\neq x$) which happens if 1 $\leq (k-x)^2 < k^2$. The leftmost inequality, $1\leq (k-x)^2$, is true since if $k=x \implies p=x(x+1)$ would be a contradiction. The right most inequality is equivalent to $(k-x)^2 < k^2 \iff 2k> x>0$. Now if $x \ge 2k$, we have $(k+1)^2 > p=k^2+x \ge k^2+2k \implies p= (k+1)^2 -1 = k(k+2)$, contradiction.

You should think twice before plagiarizing problems for an AoPS mock (if you know you know) Delete any elements of $X$ that are equal to $1$, and let $p=a^2+b$ where $2 \leq b \leq 2a+2$, so $b=p-a^2$ is the smallest element of $X$. We want to find $y<a$ such that $p-a^2 \mid p-y^2 \iff p-a^2 \mid a^2-y^2=(a-y)(a+y)$. We now consider these cases: If $2 \leq b<a$, then let $y=a-b>0$. If $b=a$, then $p=a^2+a$, but since $a \geq 2$ as $p\geq 7$, $a \mid p$ while $a<p$, so $p$ is not prime. Hence we discard this case. If $a<b<2a$, then let $y=b-a>0$. If $b=2a$, we again have $a \mid p$ and $2\leq a<p$, so we discard this case. If $b=2a+1$, we have $p=(a+1)^2$ which is absurd, so we discard this case. If $b=2a+2$, then $p=a^2+2a+2$, hence $a$ is odd. Then take $y=1$, so $2 \mid a-y \implies 2(a+1) \mid (a-1)(a+1)$. This covers all cases, so we're done. $\blacksquare$