1
$\begingroup$

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

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

2 Answers 2

3

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$.

  • 1
    @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.2012-09-03
2

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$.

  • 0
    Thanks. - And I just noted that André gave $(x_0,y_0)$ explicitly, thus avoiding the name Euκlid altogether :)2012-09-02