matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Hochschulmathe
  Status Uni-Analysis
    Status Reelle Analysis
    Status UKomplx
    Status Uni-Kompl. Analysis
    Status Differentialgl.
    Status Maß/Integrat-Theorie
    Status Funktionalanalysis
    Status Transformationen
    Status UAnaSon
  Status Uni-Lin. Algebra
    Status Abbildungen
    Status ULinAGS
    Status Matrizen
    Status Determinanten
    Status Eigenwerte
    Status Skalarprodukte
    Status Moduln/Vektorraum
    Status Sonstiges
  Status Algebra+Zahlentheo.
    Status Algebra
    Status Zahlentheorie
  Status Diskrete Mathematik
    Status Diskrete Optimierung
    Status Graphentheorie
    Status Operations Research
    Status Relationen
  Status Fachdidaktik
  Status Finanz+Versicherung
    Status Uni-Finanzmathematik
    Status Uni-Versicherungsmat
  Status Logik+Mengenlehre
    Status Logik
    Status Mengenlehre
  Status Numerik
    Status Lin. Gleich.-systeme
    Status Nichtlineare Gleich.
    Status Interpol.+Approx.
    Status Integr.+Differenz.
    Status Eigenwertprobleme
    Status DGL
  Status Uni-Stochastik
    Status Kombinatorik
    Status math. Statistik
    Status Statistik (Anwend.)
    Status stoch. Analysis
    Status stoch. Prozesse
    Status Wahrscheinlichkeitstheorie
  Status Topologie+Geometrie
  Status Uni-Sonstiges

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieProdukt Teilerfremder Zahlen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Zahlentheorie" - Produkt Teilerfremder Zahlen
Produkt Teilerfremder Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Produkt Teilerfremder Zahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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.

        
Bezug
Produkt Teilerfremder Zahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 14:45 Sa 08.05.2010
Autor: schachuzipus

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

Bezug
                
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                        
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                                                
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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.

Bezug
                                                        
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                
Bezug
Produkt Teilerfremder Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.unimatheforum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]