x = 1/2 mod prim

27.03.2011, 14:26

Pascal95

Auf diesen Beitrag antworten »

x = 1/2 mod prim

Hallo,

wie soll man $\begin{eqnarray*} x \equiv \frac{1}{2} \mod 3,5,7,11,13,17,... \end{eqnarray*}$ ausrechnen?

Es heißt ja, dass $\begin{eqnarray*} a \end{eqnarray*}$ kongruent zu $\begin{eqnarray*} b \end{eqnarray*}$ bezüglich des Modulos $\begin{eqnarray*} m \end{eqnarray*}$ ist, wenn $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} b \end{eqnarray*}$ bei der Division durch $\begin{eqnarray*} m \end{eqnarray*}$ den gleichen Rest liefern.

Ich kann diese Definition aber nicht auf die o.g. Aufgabe übertragen.

Ich habe schon Themen wie "Modulo bei Brüchen" durchgelesen, allerdings keinen Erfolg gehabt.

Vielen Dank, wenn mich jemand in dieses Thema einführen kann.

Pascal

27.03.2011, 14:32

Mystic

Auf diesen Beitrag antworten »

RE: x = 1/2 mod prim
Du musst einfach die Kongruenz

$\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$

für alle angegebenen m lösen, was sonst?... verwirrt

verwirrt

27.03.2011, 14:33

Pascal95

Auf diesen Beitrag antworten »

RE: x = 1/2 mod prim
Kann man sich das wie eine Gleichung mit 2 Seiten vorstellen.
Du hast dann mal 2 gerechnet, um Brüche zu beseitigen?

27.03.2011, 14:35

Mystic

Auf diesen Beitrag antworten »

RE: x = 1/2 mod prim
Ja, das ist erlaubt, weil ja 2 invertierbar ist mod m, wenn m ungerade ist... Man könnte das also jederzeit wieder "rückgängig machen"...

27.03.2011, 14:37

Pascal95

Auf diesen Beitrag antworten »

RE: x = 1/2 mod prim

Zitat:

Original von Mystic
2 ist invertierbar mod m, wenn m ungerade ist

Wie kann man sich das vorstellen?

27.03.2011, 14:40

Mystic

Auf diesen Beitrag antworten »

RE: x = 1/2 mod prim
2 hat ein Inverses mod m, d.h. aber genau, dass die Kongruenz

$\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$

lösbar ist... Die mod m eindeutige Lösung ist ja gerade das Inverse von 2...

Anzeige

27.03.2011, 14:46

Pascal95

Auf diesen Beitrag antworten »

Ich muss ehrlich sagen, dass ich durch das Thema noch nicht ganz durchsteige.
$\begin{eqnarray*} \frac{1}{2} = 2^{-1} \end{eqnarray*}$ ist ja klar.

$\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$ könnte ich dann sogar vielleicht lösen.

27.03.2011, 14:50

Mystic

Auf diesen Beitrag antworten »

Und wo ist dann dein Problem? verwirrt

verwirrt

27.03.2011, 14:53

Pascal95

Auf diesen Beitrag antworten »

für $\begin{eqnarray*} m=3 \end{eqnarray*}$ :

Kann man dann schreiben? :

$\begin{eqnarray*} 2x-1=3a \end{eqnarray*}$
weil die Differenz ein Vielfaches von 3 ist ( $\begin{eqnarray*} a \in \mathbb N \end{eqnarray*}$ ).

Also:
$\begin{eqnarray*} 2x=3a+1 \end{eqnarray*}$
$\begin{eqnarray*} x = \frac {3a+1} {2} \end{eqnarray*}$ ?

27.03.2011, 15:00

Mystic

Auf diesen Beitrag antworten »

Nein sorry, so geht das nicht... Du musst in deinen Unterlagen nachsehen, was ihr über das Lösen von linearen Kongruenzen

$\begin{eqnarray*} ax \equiv b \mod m \end{eqnarray*}$

gelernt habt... Stichwort: Erweiterter Euklidischer Algorithmus...

27.03.2011, 15:10

Pascal95

Auf diesen Beitrag antworten »

Das haben wir so noch nicht gelernt.
Das ist ein Thema, das mein Physiklehrer angesprochen hat.
Ich befinde mich in der 9.ten Klasse eines Gymnasiums und habe aus Interesse mit meinem Physiklehrer darüber gesprochen.
Er meinte, das man so zeigen könnte, dass sogar
$\begin{eqnarray*} \frac{1}{2} \neq \frac{2}{4} \neq -\frac{3}{-6} \end{eqnarray*}$ gilt.

Was muss ich hierfür lernen?

27.03.2011, 15:19

Mystic

Auf diesen Beitrag antworten »

Ok, dann merk dir für den Moment nur ein paar Sachen, die wären

1. Ein "Bruch"

$\begin{eqnarray*} \frac uv \mod m \end{eqnarray*}$

macht genau dann Sinn, wenn ggT(v,m)=1 gilt...

2. Ist diese Bedingung erfüllt, so hat die Kongruenz $\begin{eqnarray*} vx \equiv u \mod m \end{eqnarray*}$ eine eindeutige Lösung mod m und diese ist eben der Wert des Bruchs im Restklassenring mod m...

3. Obige Kongruenz wird üblicherweise mit dem Erweiterten Euklidischen Algorithmus gelöst, wie ich oben schon sagte, für kleine Werte von m kannst du die Lösung aber auch leicht durch Probieren herausfinden...

Und das

Zitat:

Original von Pascal95
Er meinte, das man so zeigen könnte, dass sogar
$\begin{eqnarray*} \frac{1}{2} \neq \frac{2}{4} \neq -\frac{3}{-6} \end{eqnarray*}$ gilt.

ist natürlich blanker Unsinn, falls die Brüche überhaupt wohldefiniert sind in obigem Sinne... Schöne Grüße an deinen Lehrer (außer du hast da was falsch verstanden!)... Wink

Wink

27.03.2011, 15:24

Pascal95

Auf diesen Beitrag antworten »

Vielen Dank erstmal.
Deswegen macht es ja auch Sinn, dass nur $\begin{eqnarray*} \mod m \end{eqnarray*}$ für $\begin{eqnarray*} m \end{eqnarray*}$ prim gesucht wird und die 2 auch weggelassen wurde, weil $\begin{eqnarray*} ggT(2,2) \neq 1 \end{eqnarray*}$ .

Wie kann man sich aber einen Bruch modulo einer Zahl vorstellen, wenn man nur ganzzahlige Ergebnisse sucht?
Man muss dann, wie du beschrieben hast, umstellen und das x suchen.

Aber kann man die Lösung x dann auch in die Kongruenz am Anfang einsetzen und dann etwas überprüfen?

27.03.2011, 15:54

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Pascal95
Aber kann man die Lösung x dann auch in die Kongruenz am Anfang einsetzen und dann etwas überprüfen?

Ok, wenn ich dich richtig verstanden habe, geht deine Frage dahin, ob man mit diesenn "Brüchen" auch rechnen kann... Das geht natürlich... Setzen wir z.B. für das Folgenden fest m=5... Dann gibt es gewissermaßen nur die Zahlen 0,1,2,3,4 und wann immer du etwas anderers siehst, musst du solange 5 addieren oder subtrahieren, bis du in diesen Zahlenbereich kommst...

Dann ist z.B.

$\begin{eqnarray*} \frac 12 =3, \text{ wegen } 2 \cdot 3 \equiv 1 \mod 5 \end{eqnarray*}$
$\begin{eqnarray*} \frac 13 =2, \text{ wegen } 3 \cdot 2 \equiv 1 \mod 5 \end{eqnarray*}$

Nun rechnen wir mal

$\begin{eqnarray*} \frac 12+\frac 13 = \frac 56 =\frac 01 =0 \end{eqnarray*}$

und tatsächlich ist auch

$\begin{eqnarray*} 3+2 =5\equiv 0 \mod 5 \end{eqnarray*}$

Es hat also geklappt... Augenzwinkern

Augenzwinkern

27.03.2011, 17:07

Pascal95

Auf diesen Beitrag antworten »

Ok, es soll ja $\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$ gelten.

Für $\begin{eqnarray*} m=3 \end{eqnarray*}$ probiere ich dann:

Probieren:

2*1 mod 3 = 2
2*2 mod 3 = 1
2*3 mod 3 = 0
2*4 mod 3 = 2
2*5 mod 3 = 1
2*6 mod 3 = 0
2*7 mod 3 = 2
2*8 mod 3 = 1
2*9 mod 3 = 0

So kann man die Lösungen doch auch finden?!

x= {2;5;8;...}

Warum darf ich das dann nicht wie vorhin beschrieben lösen:

Zitat:

Original von Pascal95
für $\begin{eqnarray*} m=3 \end{eqnarray*}$ :

Kann man dann schreiben? :

$\begin{eqnarray*} 2x-1=3a \end{eqnarray*}$
weil die Differenz ein Vielfaches von 3 ist ( $\begin{eqnarray*} a \in \mathbb N \end{eqnarray*}$ ).

Also:
$\begin{eqnarray*} 2x=3a+1 \end{eqnarray*}$
$\begin{eqnarray*} x = \frac {3a+1} {2} \end{eqnarray*}$ ?

Dann teste ich für a=0,1,2,3,4,5,...:
a=0 => x=1/2
a=1 => x=2
a=2 => x=7/2
a=3 => x=5
a=4 => x=13/2
a=5 => x=8

Es interssieren mich nur ganzzahlige x, also x={2,5,8,..} und komme auf die selbe Lösung wie durch probieren.

27.03.2011, 17:25

Mystic

Auf diesen Beitrag antworten »

Naja, als ich sagte, du sollst es nicht so machen, wußte ich noch nicht, dass du mit dem erweiterten euklidischen Algorithmus - das wäre das professionelle Werkzeug hier - nichts anzufangen weisst... Immerhin hast du das hier in den Hochschulbereich gepostet... Wenn du aber von vornherein die Lösungen durch Probieren finden willst, kannst es natürlich auch auf deine Art machen...

Was ich allerdings nicht verstehe, sind die vielen Lösungen, welche du bekommst... Wie ich ja oben sehr deutlich gesagt habe, hat der Bruch

$\begin{eqnarray*} \frac uv \text{ für } ggT(v,m)=1 \end{eqnarray*}$

einen eindeutigen Wert mod m und du brauchst daher nur die Werte x in {0,1,2,..,m-1} durchprobieren, ob sie

$\begin{eqnarray*} vx \equiv u \mod m \end{eqnarray*}$

erfüllen und kannst sofort aufhören sobald du einen gefunden hast...

27.03.2011, 17:36

Pascal95

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Was ich allerdings nicht verstehe, sind die vielen Lösungen, welche du bekommst... Wie ich ja oben sehr deutlich gesagt habe, hat der Bruch

$\begin{eqnarray*} \frac uv \text{ für } ggT(v,m)=1 \end{eqnarray*}$

einen eindeutigen Wert mod m und du brauchst daher nur die Werte x in {0,1,2,..,m-1} durchprobieren, ob sie

$\begin{eqnarray*} vx \equiv u \mod m \end{eqnarray*}$

erfüllen und kannst sofort aufhören sobald du einen gefunden hast...

weil ich dann den Restklassenring 2x mod 3 = 1 aufstellen kann?

Also noch weitere Lösungen: 2x+3k mit k aus N
das wären dann ja noch: 2;5;8;11;14;...

Diese erfüllen doch auch die Gleichung, denn es bleibt 1 übrig.
2*2 mod 3 =1
2*5 mod 3 =1
2*8 mod 3 =1
...

27.03.2011, 20:09

Mystic

Auf diesen Beitrag antworten »

Nochmals: Der Restklassenring mod m hat nur m Elemente, wobei man als die Vertreter seiner Klassen üblicherweise die Elemente 0,1,2,..,m-1 wählt... Du machst also nur selbst das Leben schwer, wenn du auch andere Elemente betrachtest, obwohl es jetzt nicht gerade "verboten" ist... Es geht halt nur die "Eindeutigkeit" bei deiner Betrachtungsweise verloren, und die liegt halt den Mathematikern, wie man sich vorstellen kann, sehr am Herzen... Augenzwinkern

Augenzwinkern

27.03.2011, 20:33

Pascal95

Auf diesen Beitrag antworten »

Moin!
Ok, das akzeptiere ich so.

Also ist das Ergebnis für $\begin{eqnarray*} 2x \equiv 1 \mod 3 \end{eqnarray*}$ :
$\begin{eqnarray*} x=2 \end{eqnarray*}$ .

Es könnte ansonsten nur sein: $\begin{eqnarray*} 0,1,2 \end{eqnarray*}$ , weil $\begin{eqnarray*} m=3 \end{eqnarray*}$ .

Die Gleichung erfüllen allerdings noch andere Werte, wie z.B.: $\begin{eqnarray*} x=5,8,11,14,17,20,... \end{eqnarray*}$ und alle $\begin{eqnarray*} x = 2+3k \end{eqnarray*}$ mit $\begin{eqnarray*} k \in \mathbb Z \end{eqnarray*}$

Man dürfte zu $\begin{eqnarray*} 2x \equiv 1 \mod 3 \end{eqnarray*}$ auch sicherlich sagen:
$\begin{eqnarray*} 1 \mod 3 = 1 \end{eqnarray*}$ , also $\begin{eqnarray*} 2x \mod 3 =1 \end{eqnarray*}$ , weil sie ja den selben Rest bei der Division haben sollen.

Gegeben durch: $\begin{eqnarray*} 2x \mod 3 = 1 \end{eqnarray*}$ und $\begin{eqnarray*} 1 \mod 3 = 1 \end{eqnarray*}$ $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ $\begin{eqnarray*} 2x \equiv 1 \mod 3 \end{eqnarray*}$
Das wollte ich nur eben zeigen, dass man auch schreiben kann:

$\begin{eqnarray*} 2x \mod 3 =1 \end{eqnarray*}$ und das dann auflösen => x=2

Kannst du mir noch sagen, ob man so argumentieren kann.
Ich mag es immer gerne, wenn ich selber etwas erweitere, was dann auch noch richtig ist. So sehe ich, dass ich ein Thema verstanden habe.

Pascal

27.03.2011, 20:48

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Pascal95
Kannst du mir noch sagen, ob man so argumentieren kann.
Ich mag es immer gerne, wenn ich selber etwas erweitere, was dann auch noch richtig ist. So sehe ich, dass ich ein Thema verstanden habe.

Wenn es dir hilft, sage ich ja, zumindestens habe ich nicht Falsches dabei entdeckt... Allerdings weiß ich nicht genau, worauf du hinaus willst...

27.03.2011, 20:52

Pascal95

Auf diesen Beitrag antworten »

Ich kenne den (erweiterten) Euklidschen Algorithmus (noch) nicht.

Aber so gehe ich dann vor, wenn ich nur das verwende, was ich kann.
Mehr kann man ja auch nicht verwenden Augenzwinkern

Augenzwinkern

Ich habe hier noch was angehängt:

27.03.2011, 21:23

Mystic

Auf diesen Beitrag antworten »

Ja, das stimmt, (m+1)/2 ist das Inverse zu 2 mod m, wenn m ungerade ist... Freude

Freude

27.03.2011, 21:28

Pascal95

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Ja, das stimmt, (m+1)/2 ist das Inverse zu 2 mod m, wenn m ungerade ist... Freude

Freude

Oh, cool.

Was ist jetzt das Inverse und warum geht das nur, wenn m ungerade ist?
Und wie wärst du drauf gekommen und darf man so argumentieren wie ichs da im Bild gemacht habe?!

Edit: Algebraisch gesehen, kann man sagen, dass (m+1)/2 für ungerade m eine ganze Zahl liefert. Bringt das was?
So ähnlich kann man ja auch sagen: 2x dagegen liefert immer eine gerade Zahl.

27.03.2011, 21:36

Mystic

Auf diesen Beitrag antworten »

Naja, du hast es ja streng genommen nur für die 3 Werte m=3,5,7 bewiesen, aber deine Vermutung, dass (m+1)/2 das Inverse zu 2 mod m ist, stimmt tatsächlich...

Der Beweis geht dafür so: Da m ungerade ist (m+1)/2 schon mal eine ganze Zahl im Bereich {0,1,2,..,m-1} und wir müssen nur noch zeigen, dass sie auch Lösung von

$\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$

ist... Das sieht man aber sofort durch Einsetzen:

$\begin{eqnarray*} 2 \cdot \frac{m+1}2 = m+1 \equiv 1 \mod m \end{eqnarray*}$

Wie du also hier auch wieder sehr schön sehen kannst: Mit diesen Brüchen kann man (fast) genau so rechnen, wie man es von den "gewöhnlichen" Brüchen her gewohnt ist...

27.03.2011, 21:40

Pascal95

Auf diesen Beitrag antworten »

Tatsächlich!

Wie kann man sich nun aber die Inverse vorstellen?
Ich kenne den Begriffe nur aus

z.B. Addition:
$\begin{eqnarray*} a \end{eqnarray*}$ ist invers zu $\begin{eqnarray*} -a \end{eqnarray*}$ , denn $\begin{eqnarray*} a+(-1) \end{eqnarray*}$ ist das neutrale Element der Addition, nämlich die 0.

z.B. bei der Multiplikation:
$\begin{eqnarray*} a \cdot a^{-1}=1 \end{eqnarray*}$ . Beschreibung analog.

Ist die Inverse das, was man für x einsetzt? Was ist daran invers?

27.03.2011, 21:48

Mystic

Auf diesen Beitrag antworten »

Naja, das Produkt von 2 und x in

$\begin{eqnarray*} 2x \equiv 1 \mod m \end{eqnarray*}$

ergibt ja 1, zumindestens mod m, genau wie in

$\begin{eqnarray*} a \cdot a^{-1}=1 \end{eqnarray*}$

Also ist da eine klare Analogie...

27.03.2011, 21:53

Pascal95

Auf diesen Beitrag antworten »

Stimmt.

2•x = 1,
wenn man sich das System mit m-1 Zahlen vorstellt.

Da errinere ich mich an einen Ausschnitt aus "Fermats letzter Satz", Simon Singh:
Ein Zahlensystem wie eine Uhr (eigentlich kein Zahlensystem) indem man sich zum Beispiel 12 Zahlen hat und die 12 = 0. Dann ist 15=3 und 24=12=0, das basiert auf Modulorechnung. Jetzt verstehe ich auch das besser. Man kann sich das Buch auch mehr als einmal druchlesen Augenzwinkern

Augenzwinkern

Mein Lehrer, den ich ja noch auf 1/2 ungeleich 2/4 ansprechen muss, meinte ja auch, dass man dann im Studium nicht mehr kongruent sondern tatsächlich "=" schreibt:

2x = 1

Vielen Dank.

Wie kommt man jetzt aber auf die Inverse: (m+1)/2.
Durch Prüfen haben wirs ja gezeigt aber wie kommt man drauf?

27.03.2011, 21:58

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Pascal95
Wie kommt man jetzt aber auf die Inverse: (m+1)/2.
Durch Prüfen haben wirs ja gezeigt aber wie kommt man drauf?

Durch Herumprobieren, genau wie du es gemacht hast... So werden in der Mathematik ganz allgemeine Sachen entdeckt: Man probiert ein bißchen herum, kommt zu einer Vermutung und versucht dann diese zu beweisen... Manchmal gelingt es dann auch... Augenzwinkern

Augenzwinkern

27.03.2011, 22:00

Pascal95

Auf diesen Beitrag antworten »

Auch nicht schlecht Augenzwinkern

Augenzwinkern

Ich hab mir da grad was anderes ausgedacht, poste es gleich...

27.03.2011, 22:06

Pascal95

Auf diesen Beitrag antworten »

Im Falle $\begin{eqnarray*} a \equiv b \mod m \end{eqnarray*}$ argumentiere ich wie auch vorhin über die Differenz von $\begin{eqnarray*} a-b = m \end{eqnarray*}$ , also konkret siehe Anhang:

[attach]18820[/attach]

(ist schon irgendwie einfacher als latex Augenzwinkern

Augenzwinkern

)

27.03.2011, 22:15

Mystic

Auf diesen Beitrag antworten »

Irgendwie bedienst du dich da stellenweise einer Geheimsprache, wo ich jetzt nur erahnen kann, was du nun eigentlich damit meinst... Ich glaube auch, dass du meinst, man müsse irgendwie herleiten, dass (m+1)/2 ein Inverses mod m zu 2 ist... Tatsächlich ist es aber ganz egal, woher du diese Vermutung hast... Du must nur noch zeigen, dass es tatsächlich ein Inverses mod m zu 2 ist, eben so wie ich es oben gemacht habe, das ist dann der eigentliche Beweis...

Tut mir leid, wenn dich das vielleicht jetzt nicht voll befriedigt, aber so liegen die Dinge nun mal...

27.03.2011, 22:17

Pascal95

Auf diesen Beitrag antworten »

Ich habe aber doch gezeigt, warum das Inverse (m+1)/2 sein muss!
Willst du dir den Anhang denn nicht noch mal anschauen smile

smile

27.03.2011, 22:21

Mystic

Auf diesen Beitrag antworten »

Das habe ich auch gezeigt, und meine Bemerkungen bezogen sich ja gerade auf deinen Anhang... Der ist mir leider ein Buch mit sieben Siegeln... Ich weiss auch nicht, was dir an der einen Zeile

$\begin{eqnarray*} 2 \cdot \frac {m+1}2 =(m+1) \equiv 1 \mod m \end{eqnarray*}$

nicht gefällt, das ist jedenfalls der ganze Beweis, mehr braucht es hier nicht...

27.03.2011, 22:29

Pascal95

Auf diesen Beitrag antworten »

Ja, das ist mir klar.
Aber habe ich das denn richtig hergeleitet?

Ich gehe allgemein von 2x=1 mod m aus und erkläre dann, warum x=(m+1)/2 ist.

Ich gehe dabei über die Differenz. Es heißt ja, dass bei a=b mod m auch gilt, dass a-b=m, bzw ein Vielfaches von m.

Dann schreibe ich für a=2x und für b=1.

Es heißt: 2x-1=m und löse auf und habe das Ergebnis.
x=(m+1)/2

Das lässt sich ja wiederum, wie du schriebst, nachweisen:
2x=1
2•(m+1)/2 = m+1 = 1

Ok.

Kann man so immer auf die Lösung kommen?!

27.03.2011, 22:33

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Pascal95
Kann man so immer auf die Lösung kommen?!

Wenn du damit die allgemeinere Kongruenz

$\begin{eqnarray*} ax \equiv 1 \mod m \end{eqnarray*}$

meinst, wobei natürlich stets noch ggt(a,m)=1 vorausgesetzt werden muss, dann nein... Wenn du jetzt nur den Spezialfall a=2 meinst, um den es zuletzt hier gegangen ist, dann ja...

27.03.2011, 22:46

Pascal95

Auf diesen Beitrag antworten »

ok danke.

und wenn a>2 ?

27.03.2011, 22:56

Pascal95

Auf diesen Beitrag antworten »

Geht doch genauso:

27.03.2011, 23:00

tmo

Auf diesen Beitrag antworten »

Dummerweise ist $\begin{eqnarray*} \frac{m+1}{a} \end{eqnarray*}$ im Allgemeinen keine ganze Zahl.

Das hat ja bei $\begin{eqnarray*} a=2 \end{eqnarray*}$ nur so gut geklappt, weil aus ggT(2,m)=1 sofort folgt, dass m ungerade, also m+1 gerade ist.

Wie Mystic schon x-mal erwähnt hat:

Der erweiterte euklidische Algorithmus liefert zu a,m mit ggT(a,m)=1 Zahlen x,y mit:

$\begin{eqnarray*} ax+my=1 \end{eqnarray*}$

Reduzieren mod m führt dann zu:

$\begin{eqnarray*} ax \equiv 1 \pmod m \end{eqnarray*}$

27.03.2011, 23:04

Pascal95

Auf diesen Beitrag antworten »

Guten Tag,

Zitat:

Original von tmo
Der erweiterte euklidische Algorithmus liefert zu a,m mit ggT(a,m)=1 Zahlen x,y mit:
$\begin{eqnarray*} ax+my=1 \end{eqnarray*}$

Dann sind x und y aber Bruchzahlen ?!

27.03.2011, 23:07

tmo

Auf diesen Beitrag antworten »

Nein.

Beispiel a=3, m=7.

$\begin{eqnarray*} \frac{m+1}{a}=\frac{8}{3} \end{eqnarray*}$ ist keine ganze Zahl, aber:

$\begin{eqnarray*} 1=5\cdot 3 - 2 \cdot 7 \end{eqnarray*}$

Also: $\begin{eqnarray*} 5\cdot 3 \equiv 1 \mod 7 \end{eqnarray*}$

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »