# Primes $p$ such that $p^2$ divides $x^2 + y^2 + 1$

Call a prime $p$ awesome if there exist positive integers $x$ and $y$ such that $p^2$ divides $x^2+y^2+1$.

Observation: $2$ is not awesome, because $x^2+y^2+1\not\equiv 0$ (mod $4$). But $3$ is awesome, because $9$ divides $27=5^{2}+1^{2}+1$. So my question is:

Are there infinitely many awesome primes? Can we find all awesome primes?

Motivation: It is true that for every prime $p$, there exists positive integer $x$ and $y$ such that $p$ divides $x^2+y^2+1$. The proof can be found here. (This is actually a nice result; for example, it is used in a proof of Lagrange's $4$-square theorem).

If this is too trivial, what can we say if $p^2$ is replaced by $p^{k}$? :)

-

Every odd prime has this property - even if you replace $p^2$ by $p^k$. (pretty awesome, huh)

Find a solution $(x_1,y_1)$ to $x_1^2+y_1^2+1\equiv0\pmod p$; without loss of generality, $p$ doesn't divide $x_1$. Consider the polynomial $x^2+(y_1^2+1)$. This polynomial has a root $x_0$ modulo $p$, and its derivative at that root is $2x_0\not\equiv0\pmod p$. Therefore, by Hensel's lemma, the polynomial $x^2+(y_1^2+1)$ has a root modulo $p^k$ for every $k$ - in fact, a unique root that is congruent modulo $p$ to $x_0$.

-
Thank you! I think I will start calling you awesome instead :) finally I see a fruitful application of Hensel's Lemma! – Prism Mar 9 '14 at 18:52

Well time factor here is probably only 3.

Written in the ideal equation: $X^2+Y^2+1=3Z^3$

Solutions can be written using the following equation Pell. $p^2-2(k^2+k+1)s^2=1$

Then the solutions are of the form:

$Y=2p^2+2(k+2)ps-1$

$X=2p^2+2(2k+1)ps-1$

$Z=2p^2+2(k+1)ps-1$

$k$ - what some integer.

-