Euklids algoritme er en regneforskrift til bestemmelse af største fælles divisor (sfd) for to hele tal, dvs. det største tal, der går op i begge tal.

Faktaboks

Etymologi
Algoritmen har navn efter den græske matematiker Euklid fra Alexandria.

Fx har tallene \(497\) og \(322\) \(\text{sfd} = 7\); dette bestemmes ved Euklids algoritme ved en række divisioner med rest \(497 = 1\cdot 322 + 175\), \(322 = 1\cdot 175 + 147\), \(175 = 1\cdot 147 + 28\), \(147 = 5\cdot 28 + 7\) og \(28 = 4\cdot 7 (+ 0)\).

Man dividerer altså det største af de to tal med det mindste og får en rest. Denne rest divideres op i det mindste tal, og der fås en ny rest, som så divideres op i den forrige rest.

Der fortsættes, indtil resten bliver \(0\). Den sidste rest forskellig fra \(0\) er da den største fælles divisor.

Euklids algoritme anses for at være en af verdens ældste regneforskrifter.

Læs mere i Den Store Danske

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig