| Autor |
Beitrag |
    
Tiffany (t_l)
Mitglied
Benutzername: t_l
Nummer des Beitrags: 19
Registriert: 01-2002
| | Veröffentlicht am Sonntag, den 19. Mai, 2002 - 18:38: | 
|
Man zeige: Für natürliche a, m, n mit m, n ³ 1 und a ³ 2 gilt:
ggT(an - 1,am - 1) = ad - 1, wobei d = ggT(n,m).
Tiffany |
Friedrich Laher (friedrichlaher)
Erfahrenes Mitglied
Benutzername: friedrichlaher
Nummer des Beitrags: 331
Registriert: 02-2002
| | Veröffentlicht am Montag, den 20. Mai, 2002 - 09:50: |
|
A^N = (a^d)^N, A^M = (a^d)^M,
ggt(N,M) = 1; o.B.d.A.: N > M;
führt man den Euklidischen Algorithmus für A^N-1,A^M-1 durch
(A^N-1) : (A^M-1) = A^(N-M), Rest A^(N-M)-1, ggt(M,N-M)=1
(A^M-1) : (A^(N-M)-1) = A^(2M-N) = Rest+1, ggt(N-M,2M-N)=1
....
so entspricht das, für die Exponenten, auch einem ( der "primitiveren" Form des)
Euklidischem Algorithmus.
Da
ggt(N,M)=1 wird die Letzte Division des Algorithmus. für A^N-1,A^M-1, mit natürlichem x > 0
zu
(A^x-1) : (A-1) = A^(x-1)+A^(x-2)..+A+1, Rest 0, ggt(A^N,A^M) also Letzter Divisor = A-1 = a^d-1
(Beitrag nachträglich am 20., Mai. 2002 von friedrichlaher editiert) |
|
