ევკლიდეს ალგორითმი

ევკლიდეს ალგორითმი — ორი მთელი რიცხვის ან ორი ერთცვლადიანი მრავალწევრის უდიდესი საერთო გამყოფის მოძებნის ხერხი. ევკლიდეს ალგორითმი გეომეტრიულად, როგორც ორი მონაკვეთის საერთო საზომის მოძებნის ხერხი, პირველად მოცემულია ევკლიდეს „საწყისებში“. დადებითი მთელი a და b რიცხვებისათვის ევკლიდეს ალგორითმი შემდეგში მდგომარეობს: მიმდევრობით შევასრულებთ გაყოფას: 

უკანასკნელი დადებითი , ნაშთი იქნება a და b რიცხვების უდიდესი საერთო გამყოფი. ასევე იქცევიან მრავალწევრების შემთხვევაშიც.

ლიტერატურა

კატეგორია:თეორიულ-რიცხვითი ალგორითმები