Opgave 5
Euklids algoritme
Primtallene er byggeklodserne i systemet af hele tal. Ethvert helt tal kan nemlig faktoriseres i et produkt af primtal - endda på en entydig måde. Ved hjælp af primtalsfaktorisering kan man for eksempel i princippet bestemme den største fælles divisor for to tal a og b, som betegnes sfd(a,b ).
1. |
Faktoriser 294 og 60, og angiv den største fælles divisor |
I praksis er det ikke muligt at finde største fælles divisor for meget store tal på denne måde, da der er ikke nogen kendt effektiv måde at faktorisere på. Vi vil nu se på Euklids algoritme, der i et overkommeligt antal trin finder den største fælles divisor for to tal. Algoritmen bygger på følgende:
sfd(a,b ) = sfd(b,rest(a,b )) |
(9) |
Eksempel:
Når a = 294 og b = 60 giver Euklids algoritme:
294 = 4 · 60 + 54
60 = 1 · 54 + 6
54 = 9 · 6 + 0
|
Største fælles divisor for 6 og 54 er altså 6 (da 6 går op i 54), og 6 er derfor også største fælles divisor for 294 og 60.
Vi ser nu på to tal a og b, for hvilke den største fælles divisor er 1. Vi skal se, hvordan man kan bestemme hele tal x og y, således at
eller med andre ord: så a ·x har resten 1 ved division med b. Metoden, der går ud på først at opskrive Euklids algoritme, og dernæst i en vis forstand regne baglæns, illustreres med følgende eksempel:
Når a = 7 og b = 23 giver Euklids algoritme:
23 = 3 · 7 + 2
7 = 3 · 2 + 1
I hver af ligningerne isoleres det sidste led:
2 = 23 - 3 · 7
1 = 7 - 3 · 2
I den nederste ligning erstattes 2 med højresiden i den ovenstående:
1 = 7 - 3 · (23 - 3 · 7) = - 3 · 23 + 10 · 7
Der gælder altså at 1 = x · 7 + y · 23 for x =10 og y = -3.
|
2. |
Bestem et tal x, således at 11 · x har resten 1 ved division med 62. |
3. |
Bestem hele tal x og y, således at 1000 = 7x + 11y |
Reference:
Johan P. Hansen og Henrik Spalk: Algebra og talteori , Gyldendal(2002)
|
|