An efficient algorithmic solution of the Diophantine equation 𝑢²+5𝑣²=𝑚

Wilker, Peter

doi:10.1090/S0025-5718-1980-0583512-5

An efficient algorithmic solution of the Diophantine equation $u\sp{2}+5v\sp{2}=m$

Author: Peter Wilker
Journal: Math. Comp. 35 (1980), 1347-1352
MSC: Primary 10B05; Secondary 10-04, 10A25
DOI: https://doi.org/10.1090/S0025-5718-1980-0583512-5
MathSciNet review: 583512
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The determination of irreducible elements of the domain $Z[\sqrt { - 5} ]$ requires the solution of the Diophantine equation ${u^2} + 5{v^2} = m$ , where m represents certain primes or products of two primes. An algorithm of order $\log m$ is given for the solution of the equation.

[1] J. BRILLHART, "Note on representing a prime as a sum of two squares," Math. Comp., v. 26, 1972, pp. 1011-1013. MR 0314745 (47:3297)
[2] D. H. LEHMER, "Computer technology applied to the theory of numbers," Studies in Number Theory, Math. Assoc. Amer. (distributed by Prentice-Hall, Englewood Cliffs, N. J.), 1969, pp. 117-151. MR 0246815 (40:84)
[3] L. J. MORDELL, Diophantine Equations, Academic Press, New York, 1969. MR 0249355 (40:2600)
[4] H. M. STARK, "On complex quadratic fields with class number two," Math. Comp., v. 29, 1975, pp. 289-302. MR 0369313 (51:5548)