Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Kongruenzen lösen

Kongruenzen lösen

Universität / Fachhochschule

Elementare Zahlentheorie

Teilbarkeit

Tags: Elementare Zahlentheorie, Teilbarkeit

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
Mathedenker

Mathedenker aktiv_icon

16:10 Uhr, 20.12.2012

Antworten
Hallo Leute,
ich mal wieder mit einer Frage bzgl. Kongruenzen.

ich habe x23141mod210 und x96456mod1001

Wie soll ich solche Dinger lösen?
In der Uni hatten wir eine Methode, die sowas hätte lösen können, wenn ggT(141,210) =1 gewesen wäre ... aber da dies nicht der Fall ist, weiß ich ν nimmer wie ich weirte vorgehen soll ...

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."
Online-Nachhilfe in Mathematik
Antwort
michaL

michaL aktiv_icon

16:13 Uhr, 20.12.2012

Antworten
Hallo,

sollen die Kongruenzen simultan gelöst werden oder unabhängig voneinander?

Mfg Michael
Mathedenker

Mathedenker aktiv_icon

16:51 Uhr, 20.12.2012

Antworten
Nee das sind schon zwei verschiedene Aufgaben, hab nur beide mal erwähnt, da ich doch mein, dass beide auf gleicher Art und Weise gelöst werden.
Antwort
michaL

michaL aktiv_icon

17:19 Uhr, 20.12.2012

Antworten
Hallo,

ahnte ich schon.

Also wenden wir und zunächst einmal der Aufgabe x23141 mod 210 zu.

Leider ist das auch schon ein Sonderfall, da 141 und 210 nicht teilerfremd sind (beide durch 3 teilbar), wie du ja auch schon selbst schreibst.
Da versucht man herauszufinden, bei welcher Potenz von 141 Identität auftritt (wenn das geht).
Hierbei haben wir Glück, da 1412141 mod 210 gilt. Damit ist x=141 eine Lösung. Ich weiß allerdings im Moment nicht, ob noch weitere auftreten.

Die zweite Aufgabe ist wegen ggT(1001,456)=1 einfacher. Du sprichst selbst an, dass ihr das an der Uni zu lösen gelernt habt.

Mfg Michael
Mathedenker

Mathedenker aktiv_icon

17:29 Uhr, 20.12.2012

Antworten
Hey cool, danke erstmal.
Aber was hat es mit der Identitätsregel auf sich?
Leider kenne ich diese nicht - zu mindest ist mir keine bewusst - kannst du mir dies also vielleicht noch näher erläutern?
Antwort
michaL

michaL aktiv_icon

17:55 Uhr, 20.12.2012

Antworten
Hallo,

war eher ein Zufallstreffer.
Muss darüber noch nachdenken. Bin aber nicht ganz fit, daher begnüge ich mich im Moment einfach mit der Erkenntnis.

Mfg Michael
Antwort
Bummerang

Bummerang

09:58 Uhr, 21.12.2012

Antworten
Hallo,

zur ersten Aufgabe:

210=2357

Ganz offensichtlich gilt hier:

x231mod2

x230mod3

x231mod5

x231mod7

Ganz offensichtlich folgt daraus:

x1mod2

x0mod3

Für die 5 kann man mittels eines Taschenrechners ermitteln:

123=11mod5
223=83886083mod5
323(-2)23mod5-3mod52mod5
423(-1)23mod5-1mod54mod5

Damit muß auch gelten:

x1mod5

Für die 7 kann man mittels eines Taschenrechners ermitteln:

123=11mod7
223=83886084mod7    ;    608-388+8=228=210+14+4
323=941431788275mod7    ;    827-178+143-94=698=700-7+5
423(-3)23mod7-5mod72mod7
523(-2)23mod7-4mod73mod7
623(-1)23mod7-1mod76mod7

Damit gilt auch:

x1mod7

Zu lösen ist demzufolge das folgende System von Kongruenzen:

x1mod2

x0mod3

x1mod5

x1mod7

Aus der letzten Kongruenz ergibt sich der Startwert x=1. Da dieser nicht die vorletzte Kongruenz erfüllt, muß 75=35 addiert werden, ergibt 1+35=36. Diese Zahl erfüllt auch schon die Kongruenz modulo 3 aber leider nicht die Kongruenz modulo 2. Deshalb wird nunmehr 753=105 addiert, ergibt 141. Damit sind alle 4 Kongruenzen erfüllt und x=141+k210,k ist die einzige Lösung.
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.