### Representing a prime p=5n ± 1 as x^{2} + 3xy + y^{2}, where x > y ≥ 1

The underlying algorithm was published in
*New algorithms for modular inversion and representation by binary quadratic forms arising from structure in the Euclidean algorithm*, Christina Doran, Shen Lu and Barry R. Smith.
First find the solution v of the congruence v^{2} + v - 1 ≡ 0 (mod p), where v < p/2.

Then perform the Euclidean algorithm with p and v.

The length of the Euclidean algorithm is 2s + 1 and the sequence of quotients has the form

q_{1}, … , q_{s-1}, q_{s} + (-1)^{s+1}, 1, q_{s}, q_{s-1}, … , q_{1}.

Then r_{s+1} is the first remainder less than √(p/5) and r_{s-1} = r_{s} + r_{s+1}. Also
- p = x
^{2} + 3xy + y^{2}, where y = r_{s+1} and x = r_{s} or r_{s} – r_{s+1}, according as s is odd or even;
- p = x
^{2} + xy - y^{2}, where y = r_{s+1} and x = r_{s} or r_{s} + r_{s+1}, according as s is even or odd.

The representation in positive integers x and y with x > y, is unique.
This is a BCmath version of a BC program.

*Last modified 22nd May 2015*

Return to main page