Kongruent modulo

21.03.2013, 16:58

taddel123

Kongruent modulo

Meine Frage:
Hey,

Nach der ersten Vorlesung in Mathe2 hatte ich leider nicht sofort alles verstanden. Wir rechneten Aufgaben vom Typ: x*225780+y*1135380 = 60, man solle eine ganzzahlige Lösung angeben. Über den erweiterten euklidschen Algorithmus habe ich das dann zumindest hinbekommen.

Der Aufgabentyp der mir noch Probleme bereitet ist:
$\begin{eqnarray*} 435x \equiv 1 mod 75151 \end{eqnarray*}$

Man solle x im Repräsentantensystem (also positiv) bestimmen.

Meine Ideen:
Habe das einfach mal analog zur oberen Aufgabe versucht zu lösen, kam dann aber nur auf 46*75151 - 7947*435 = 1, was mir ja glaube ich nicht sonderlich viel bringt.

Hoffe mir kann hier jmd helfen,
Liebe Grüße

21.03.2013, 17:20

weisbrot

Auf diesen Beitrag antworten »

RE: Kongruent modulo

Zitat:

Habe das einfach mal analog zur oberen Aufgabe versucht zu lösen, kam dann aber nur auf 46*75151 - 7947*435 = 1, was mir ja glaube ich nicht sonderlich viel bringt.

doch! betrachte die gleichung dann mod 75151 und du bist so gut wie fertig.
lg

21.03.2013, 17:36

taddel123

Auf diesen Beitrag antworten »

Mh, ich stehe glaube ich "leicht" auf dem Schlauch. Mir fällt nur auf, dass bei 7947*435 mod 75151 75150 ist bzw 7947*435 - 1mod 75151 75149.

Fehlen also irgendwie 2 Augenzwinkern

Hatte vorher eig nie viel mit Kongruenz usw zutun vllt habe ich da noch die falsche Sicht.

21.03.2013, 17:43

weisbrot

Auf diesen Beitrag antworten »

Zitat:

Mir fällt nur auf, dass bei 7947*435 mod 75151 75150 ist bzw 7947*435 - 1mod 75151 75149.

äh.. wie meinen? verwirrt

$\begin{eqnarray*} a\equiv 0\quad\mod a \end{eqnarray*}$
und dann auch
$\begin{eqnarray*} b\cdot a\equiv 0\quad\mod a \end{eqnarray*}$
-das einfach benutzen!
lg

21.03.2013, 17:45

taddel123

Auf diesen Beitrag antworten »

Mh, 75151 - 7947 = 67204; 67204 * 435 = 29233740 ; 29233740 mod 75151 = 1

Nur absolut keine Ahnung warum Big Laugh

21.03.2013, 17:53

weisbrot

Auf diesen Beitrag antworten »

ja dann geh halt einfach mal auf das ein, was ich in meinen antworten zuvor an tips gegeben hab, und dann weißt du warum!

21.03.2013, 18:04

taddel123

Auf diesen Beitrag antworten »

Sorry, als ich die Antwort schrieb war deine noch nicht zu sehen Big Laugh

. Kann aber leider trotzdem wenig mit anfangen :/. Klar wenn ich 46*75151 als a*b sehe kann ich die 46 bezüglich des modulos wohl vernachlässigen, aber warum ich das bei so einer Gleichung machen kann, ergibt für mich im Moment echt absolut keinen Sinn.

21.03.2013, 18:39

taddel123

Auf diesen Beitrag antworten »

Also, wenn ich die Regeln jetzt mal ganz stumpf anwende komme ich auf:

46*75151 - 7947* 435 = 1 damit komme ich auf

$\begin{eqnarray*} 46*75151 - 7947*435 \equiv 1 mod 75151 \end{eqnarray*}$

wenn ich jetzt anhand der Regel

$\begin{eqnarray*} a*b \equiv 1 mod a = a \equiv 1 mod a \end{eqnarray*}$ umforme:

$\begin{eqnarray*} 75151 - 7947*435 \equiv1 mod 75151 \end{eqnarray*}$

Also keine Ahnung wie ich durch die Regeln auf das gewünschte 75151 - 7947 komme.

Liebe Grüße

21.03.2013, 18:53

HAL 9000

Auf diesen Beitrag antworten »

Vermutlich hast du zu lange, viel zu lange draufgeschaut...

Lass den ersten Summanden, der durch das Modul 75151 teilbar ist, doch ganz weg!!! D.h., aus

46*75151 - 7947* 435 = 1

folgt sofort

$\begin{eqnarray*} - 7947 \cdot 435 \equiv 1 \bmod 75151 \end{eqnarray*}$ ,

d.h. $\begin{eqnarray*} x\equiv -7957\bmod 75151 \end{eqnarray*}$ ist die Inverse zu 435 und damit Lösung deiner Kongruenz.

Zitat:

Original von taddel123
Man solle x im Repräsentantensystem (also positiv) bestimmen.

Sollte dann auch kein Problem sein, einfach einmal den Modul hinzuaddieren $\begin{eqnarray*} -7957+75151 \end{eqnarray*}$ , schon hast du deinen positiven Repräsentanten.

21.03.2013, 19:42

taddel123

Auf diesen Beitrag antworten »

Hey,

Deine erste Gleichung versteh ich nicht ganz, -7947*435 ist ja nicht mit Rest 1 durch 75151 teilbar oder? OH GOTT, genau das hatte ich vorhin sehr sehr oft gerechnet und mein Taschenrechner zeigte eben -45,9999... an und hab mich immer gewundert..

Ist wohl nen blöder Rundungsfehler und ich habe heute eindeutig zuviel drüber nachgedacht. Inverse höre ich in dem Bezug leider zum ersten mal, war wiegesagt auch erst eine Vorlesung zu dem Thema.

21.03.2013, 19:46

taddel123

Auf diesen Beitrag antworten »

Bzw nein

. Ich klinke mich glaub ich für heute mal aus. Genau diese Zeile stimmt ja eben nicht oder? Hat nämlich nicht Rest 1, so war es gemeint Augenzwinkern

21.03.2013, 22:47

HAL 9000

Auf diesen Beitrag antworten »

Wieder mal dieser Trugschluss?
Ich kann dir nur insoweit folgen, dass du dich allem Anschein nach von der in vielen TR bzw. Programmiersprachen implementierten Funktion $\begin{eqnarray*} a\bmod m \end{eqnarray*}$ aufs Glatteis führen lässt:

Für negative Argumente $\begin{eqnarray*} a \end{eqnarray*}$ liefern diese Funktionen nämlich i.d.R. als Rest NICHT den kleinsten positiven Repräsentanten, sondern $\begin{eqnarray*} -(|a| \bmod m) \end{eqnarray*}$ .

In diesem Fall hier also -75150, was modulo 75151 aber doch der 1 entspricht!!!

22.03.2013, 07:10

taddel123

Auf diesen Beitrag antworten »

Genauso war es Augenzwinkern

. Kam ich gestern auch noch dahinter. Vielen Dank für eure Hilfe!

Neue Frage »

Antworten »

Kongruent modulo

Verwandte Themen