# $p-x^2$ divides $p-y^2$

$$p$$ is a prime with $$p>5$$, and let $$S = \{p − n^2 : n \in\mathbb Z, n^2 < p\}$$. Prove that $$S$$ contains two elements $$a, b$$ such that $$1 < a < b$$ and $$a$$ divides $$b$$.

Let $$a = p-x^2$$ and $$b = p-y^2$$

Because $$x$$ and $$y$$ are both less than or equal to $$\sqrt p$$, I was reminded of Thue's lemma and I tried it, but it doesn't seem to work. I thought of using the Chinese Remainder Theorem, but if I use that, I have no idea how to make sure the solution is less than or equal to $$\sqrt p$$. I can't think of anything else, at least not thus far.

• Where do x, y come in in the body of your post. You define p, S, n, a, b. No x, y. What are x and y? Please do not depend on the title to express part of your question. The question body should be all inclusive. Also how do a, b relate to your title or the rest of the information in the body of your question. Did you mean x, y such that $1\lt x \lt y$ and $x\mid y$? Commented Oct 9, 2020 at 17:31
• sorry, I changed variables partway through and didn't notice
– user705713
Commented Oct 9, 2020 at 17:41
• Thanks for editing! Commented Oct 9, 2020 at 17:43

If not a very sophisticated proof is needed only a simple one, then let $$c \in\mathbb Z$$, for which $$c(p-x^2) = p-y^2$$
$$(c - 1)(p-x^2) = (x + y)(x - y) \Rightarrow x > y$$.
We can set either $$p-x^2 = x + y \Rightarrow y = p - x^2 - x$$,
or $$p-x^2 = x - y \Rightarrow y = x - (p - x^2)$$,
in both cases we can show that there exist $$(x, y, c)$$ so that all the initial conditions apply.