Representation of an Integer by a Quadratic Form through the Cornacchia Algorithm

Abstract

Cornachia’s algorithm can be adapted to the case of the equation x 2 + d y 2 = n and even to the case of a x 2 + b x y + c y 2 = n . For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x 2 + y 2 = n ). Starting from a quadratic form with two variables f ( x , y ) = a x 2 + b x y + c y 2 and n an integer. We have shown that a primitive positive solution ( u , v ) of the equation f ( x , y ) = n is admissible if it is obtained in the following way: we take α modulo n such that f ( α , 1 ) ≡ 0 mod n , u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4 c n / | D | ) (possibly α itself) and the equation f ( x , y ) = n . has an integer solution u in y . At the end of our work, it also appears that the Cornacchia algorithm is good for the form n = a x 2 + b x y + c y 2 if all the primitive positive integer solutions of the equation f ( x , y ) = n are admissible, i.e. computable by the algorithmic process.