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) |
|