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] John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013. MR 0314745, https://doi.org/10.1090/S0025-5718-1972-0314745-6
[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
[3] L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, Vol. 30, Academic Press, London-New York, 1969. MR 0249355
[4] H. M. Stark, On complex quadratic fields wth class-number two, Math. Comp. 29 (1975), 289–302. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR 0369313, https://doi.org/10.1090/S0025-5718-1975-0369313-X