# Integer solutions of $p^2 + xp - 6y = \pm1$

Given a prime $p$, how can we find positive integer solutions $(x,y)$ of the equation:

$$p^2 + xp - 6y = \pm1$$

-

Certainly if $p=2$ or $p=3$ you cannot find such $x$ and $y$. For the others, note that ny prime $\gt 3$ is of the form $6k\pm 1$.

Suppose that $p=6k+1$. Then $p^2=6l+1$ for some $l$.

To find $x$ and $y$ such that $p^2+xp=6y+1$ is now very easy: let $x$ be any positive multiple of $6$. Then $p^2+xp\equiv 1\pmod{6}$.

To find $x$ and $y$ such that $p^2+xp=6y-1$, let $x$ be any positive number congruent to $-2$ modulo $6$. Then $p^2+xp\equiv 1+(-2)(1)\equiv -1\pmod{6}$.

Exactly the same sort of idea works for primes $p$ of the form $6k-1$.

-
Thank you for your answer. Can you explain this part please: "Any positive number congruent to −2 modulo 6"? –  Khaled Sep 3 '12 at 6:51
@Khaled: Sorry, because of the tags I thought congruences would be familiar to you. It means any positive integer of the form $6u-2$, like $4$, $10$, $16$, $20$, and so on. –  André Nicolas Sep 3 '12 at 8:54

If $p=2$ or $p=3$, you can't.

Otherwise, the extended Euclid algorithm produces a solution $(x_0,y_0)$ of $x_0 p - 6 y_0 = \pm 1$ (in fact, one for $+1$ and one for $-1$). Then $x=x_0+6k-p$ and $y=y_0+pk$ is a solution of $p^2+xp-6y=\pm 1$. Since both $x$ and $y$ grow with $k$, we find infinitely many positive solutions, one for eack $k\ge\max\{\lfloor {p-x_0\over6}\rfloor, \lfloor {-y_0\over p}\rfloor\}+1$.

-
Off topic: In English, it's Euclid. –  user2468 Sep 2 '12 at 20:45
Thanks. - And I just noted that André gave $(x_0,y_0)$ explicitly, thus avoiding the name Euκlid altogether :) –  Hagen von Eitzen Sep 2 '12 at 20:58