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.

This is a BCmath version of a BC program.

Enter p (a prime of the form 5n + 1 or 5n – 1):

Last modified 22nd May 2015
Return to main page