Produkt Teilerfremder Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:26 Sa 08.05.2010 | | Autor: | Wizard |
| Aufgabe | Ist ggT(a,m) = 1 und ggT(r,m) = 1, so ist ggT(ar,m) = 1.
mit Beweis (ohne Rückgriff auf die Primfaktorzerlegung)
|
Steht im Zusammenhang mit einen Beweis zum(Euler'scher Satz)
Für alle teilerfremden a,m∈N gilt:
a^(φ(m)) ≡1 (mod m)
Beweis:
Zu gegebenen m∈N gibt es φ(m) natürliche Zahlen n mit 1≤n≤m die zu m teilerfremd sind. Es seien dies die Zahlen [mm] r_1,r_2,…,r_φ(m) [/mm] . Ist a zu m teilerfremd, so sind auch die Zahlen [mm] 〖a*r〗_1,a*r_2,…,a*r_φ(m) [/mm] als Produkt zweier zu m teilerfremder Zahlen zu m teilerfremd und paarweise inkongruent mod m. Aus a*r_(i [mm] )≡a*r_j [/mm] (mod m) mit 1≤i,j≤φ(m) folgt nämlich nach Division durch a (vgl. Satz 5a) , dass r_(i [mm] )≡r_j [/mm] (mod m) ,also i=j. ....
Dafür muss ich oben genanntes Beweisen. Wenn ich mir die Teilermengen anschaue ist dies eigentlich klar, aber komme auf keine allgemeine Form.Habe im Internet nichts entsprechendes gefunden.
Vielen Dank für die Mühe
Wizard
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
ohne alles im Detail durchgesehen zu haben, gilt doch:
$a \ [mm] \equiv [/mm] \ b \ [mm] \operatorname{mod}(m) [/mm] \ [mm] \Rightarrow a\cdot{}c [/mm] \ [mm] \equiv b\cdot{}c [/mm] \ [mm] \operatorname{mod}(m)$
[/mm]
Kannst du das nicht benutzen?
Mit
(1) [mm] $a^{\varphi(m)} [/mm] \ [mm] \equiv [/mm] \ 1 \ [mm] \operatorname{mod}(m)$ [/mm] und
(2) [mm] $r^{\varphi(m)} [/mm] \ [mm] \equiv [/mm] \ 1 \ [mm] \operatorname{mod}(m)$
[/mm]
ist doch mit der eingangs erwähnten Rechenregel
[mm] $a^{\varphi(m)} [/mm] \ [mm] \equiv [/mm] \ 1 \ [mm] \operatorname{mod}(m) \Rightarrow a^{\varphi(m)}\cdot{}r^{\varphi(m)} [/mm] \ [mm] \equiv [/mm] \ [mm] 1\cdot{}r^{\varphi(m)} [/mm] \ [mm] \operatorname{mod}(m)$
[/mm]
Also [mm] $(a\cdot{}r)^{\varphi(m)} [/mm] \ [mm] \equiv r^{\varphi(m)} \stackrel{(2)}{\equiv} [/mm] \ 1 \ [mm] \operatorname{mod}(m)$
[/mm]
Also [mm] $\operatorname{ggT}(ar,m)=1$
[/mm]
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:53 Sa 08.05.2010 | | Autor: | Wizard |
Erst einmal vielen dank für die schnelle Antwort.
Kann ich soweit auch nachvollziehen. Nur will ich gerade
$ [mm] a^{\varphi(m)} [/mm] \ [mm] \equiv [/mm] \ 1 \ [mm] \operatorname{mod}(m) [/mm] $ mittels der oberen Fragestellung beweisen.
Anders ausgedrückt, ich kann ja nicht die zu Behauptung des eulerischen Satzes dazu verwenden um einen Teil des Beweies zu beweisen.
Deshalb wäre mir eine andere Lösungsmöglichkeit lieb.
mfg
Wizard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:44 Sa 08.05.2010 | | Autor: | felixf |
Hallo!
> Erst einmal vielen dank für die schnelle Antwort.
> Kann ich soweit auch nachvollziehen. Nur will ich gerade
> [mm]a^{\varphi(m)} \ \equiv \ 1 \ \operatorname{mod}(m)[/mm] mittels
> der oberen Fragestellung beweisen.
> Anders ausgedrückt, ich kann ja nicht die zu Behauptung
> des eulerischen Satzes dazu verwenden um einen Teil des
> Beweies zu beweisen.
> Deshalb wäre mir eine andere Lösungsmöglichkeit lieb.
Kennt ihr folgendes: $ggT(a, b) = 0 [mm] \Leftrightarrow \exists [/mm] x, y [mm] \in \IZ [/mm] : 1 = a x + b y$?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:01 Sa 08.05.2010 | | Autor: | Wizard |
Es geht im übrigen um einen Seminarvortrag in Elementarer Zahlentheorie, welches sich auf das Buch "Elementare Zalentheorie" von Fridhelm Padberg stützt. Daraus entstammt auch der Ausszug des Beweises.
Ich habe darin folgendes gefunden was dem oben gefragten entsprechen könnte (bin in dem Themengebiet nicht richtig drin^^)
Satz 8 Kap V
Für alle a,b [mm] \in \IN [/mm] gibt es x,y [mm] \in \IZ [/mm] mit ggT(a,b)=x*a+y*b
Dies darf ich mit Sicherheit verwenden. Dieser Satz steh ja auch im zusammenhang mit lineare diophantische Gleichungen, was auch schon Vortragsthema war.
Ich hoffe, diese Auskunft war aufschlussreich und ermöglicht einen möglist kurzen Beweis zur Ausgangfrage.
lg
Wizard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:08 So 09.05.2010 | | Autor: | felixf |
Hallo Wizard!
> Es geht im übrigen um einen Seminarvortrag in Elementarer
> Zahlentheorie, welches sich auf das Buch "Elementare
> Zalentheorie" von Fridhelm Padberg stützt. Daraus
> entstammt auch der Ausszug des Beweises.
> Ich habe darin folgendes gefunden was dem oben gefragten
> entsprechen könnte (bin in dem Themengebiet nicht richtig
> drin^^)
> Satz 8 Kap V
> Für alle a,b [mm]\in \IN[/mm] gibt es x,y [mm]\in \IZ[/mm] mit
> ggT(a,b)=x*a+y*b
>
> Dies darf ich mit Sicherheit verwenden. Dieser Satz steh ja
> auch im zusammenhang mit lineare diophantische Gleichungen,
> was auch schon Vortragsthema war.
> Ich hoffe, diese Auskunft war aufschlussreich und
> ermöglicht einen möglist kurzen Beweis zur Ausgangfrage.
Ja, damit geht es super :)
Schreibe $1 = [mm] x_1 [/mm] a + [mm] y_1 [/mm] m$ und $1 = [mm] x_2 [/mm] r + [mm] y_2 [/mm] m$ mit [mm] $x_i, y_i \in \IZ$. [/mm] Dann ist $1 = [mm] (x_1 [/mm] a + [mm] y_1 [/mm] m) [mm] \cdot (x_2 [/mm] r + [mm] y_2 [/mm] m) = [mm] (x_1 x_2) [/mm] a r + (...) m$, wobei $(...) [mm] \in \IZ$ [/mm] ist (das $(...)$ zu bestimmen ist nun deine Aufgabe  ).
So. Jetzt sei $d = ggT(a r, m)$. Dann ist $d$ sowohl ein Teiler von $a r$ wie auch von $m$, und somit... Das jetzt fertigzuschreiben ist deine Aufgabe 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:25 So 09.05.2010 | | Autor: | Wizard |
ok vielen dank. Wenn ich das so umforme erhalte ich :
ar*x1x2 + mr*y1x2 + am y2x1 + m²y2*x2 (habe zur Sicherheit mit CAS nach a*r entwickeln lassen)
bzw. den hinteren teil nach m entwickelt:
ar*x1x2 + m(r*y1x2+a*y2x1+m*y2x2)
Jetzt sei d = ggT(a r, m). Dann ist d sowohl ein Teiler von a r wie auch von m, und somit...ist d=1,da a und r teilerfremd zu m sind bzw. ggt(a,m)=1 und ggt(r,m)=1.
Das würde ich am liebsten hin schreiben, aber das macht ja keinen Sinn. ar und m dürfen ja nur 1 als ggT, woher weiß ich das die nun keinen weiteren Teiler haben, denn wenn sie mehr hätten wäre ja die Aussage falsch....
Trotzdem vielen Dank soweit.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:42 So 09.05.2010 | | Autor: | felixf |
Moin!
> ok vielen dank. Wenn ich das so umforme erhalte ich :
> ar*x1x2 + mr*y1x2 + am y2x1 + m²y2*x2 (habe zur
> Sicherheit mit CAS nach a*r entwickeln lassen)
> bzw. den hinteren teil nach m entwickelt:
> ar*x1x2 + m(r*y1x2+a*y2x1+m*y2x2)
>
> Jetzt sei d = ggT(a r, m). Dann ist d sowohl ein Teiler von
> a r wie auch von m, und somit...ist d=1,da a und r
> teilerfremd zu m sind bzw. ggt(a,m)=1 und ggt(r,m)=1.
> Das würde ich am liebsten hin schreiben, aber das macht
> ja keinen Sinn. ar und m dürfen ja nur 1 als ggT, woher
> weiß ich das die nun keinen weiteren Teiler haben, denn
> wenn sie mehr hätten wäre ja die Aussage falsch....
> Trotzdem vielen Dank soweit.
Argumentiere doch so: $d$ ist ein Teiler von $ar$, also auch von [mm] $ar*x_1x_2$. [/mm] Weiterhin ist es ein Teiler von $m$, also auch von [mm] $m(r*y_1x_2+a*y_2x_1+m*y_2x_2)$. [/mm] Und damit ist es auch ein Teier von [mm] $ar*x_1x_2 [/mm] + [mm] m(r*y_1x_2+a*y_2x_1+m*y_2x_2) [/mm] = ...$?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:42 Sa 08.05.2010 | | Autor: | felixf |
Hallo!
> Also [mm](a\cdot{}r)^{\varphi(m)} \ \equiv r^{\varphi(m)} \stackrel{(2)}{\equiv} \ 1 \ \operatorname{mod}(m)[/mm]
>
> Also [mm]\operatorname{ggT}(ar,m)=1[/mm]
Dass dies aus $(a [mm] r)^{\varphi(m)} \equiv [/mm] 1 [mm] \pmod{m}$ [/mm] folgt ist erstmal beweiswuerdig, es koennte sei dass der OP das noch nicht weiss.
Dazu zeigt man, dass die Einheiten in [mm] $\IZ/m\IZ$ [/mm] gerade [mm] $\{ r + m\IZ \mid ggT(r, m) = 1 \}$ [/mm] sind.
LG Felix
|
|
|
|
