Representing a prime p=5n ± 1 as x2 + 3xy + y2, 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 v2 + 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
q1, … , qs-1, qs + (-1)s+1, 1, qs, qs-1, … , q1.
Then rs+1 is the first remainder less than √(p/5) and rs-1 = rs + rs+1. Also
The representation in positive integers x and y with x > y, is unique.
- p = x2 + 3xy + y2, where y = rs+1 and x = rs or rs – rs+1, according as s is odd or even;
- p = x2 + xy - y2, where y = rs+1 and x = rs or rs + rs+1, according as s is even or odd.
This is a BCmath version of a BC program.
Last modified 22nd May 2015
Return to main page