Matroids Matheplanet Forum Index
Moderiert von Wauzi
Teilbarkeit » Kongruenzen » Lösen einer Gleichung in Z/99Z
Druckversion
Druckversion
Autor
Universität/Hochschule J Lösen einer Gleichung in Z/99Z
Bura
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 31.05.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-05-31


Hallo, ich komme bei der folgenden Aufgabe nicht weiter.

und zwar soll ich die Lösung der Gleichung 59 * x = 5 in ℤ/99ℤ berechnen.

Mit meinem naiven Ansatz komme ich leider nicht weiter, so dass bei x = 10 immer noch keine 5 rauskommt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-05-31

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Hallo,

weißt du, wie man die Gleichung $59y \equiv 1 \pmod{99}$ löst? Stichwort: Euklidischer Algorithmus.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bura
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 31.05.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-05-31


Das Verfahren zum Berechnen des ggTs ist mir bekannt, jedoch wie es das umstelle, bzw. hier anwende nicht.

Edit, habe grad etwas dazu gefunden 'Ax ≡ b mod m', damit müsste ich weiterkommen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-05-31

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Mit dem (erweiterten) Euklidischen Algorithmus kannst du Zahlen $y,z\in \IZ$ bestimmen, so dass $59y+99z=1$ gilt. Insbesondere ist dann $59y\equiv 1 \pmod{99}$.
Siehst du, wie man damit dann deine Gleichung lösen kann?
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
JonyGo
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 31.05.2020
Mitteilungen: 21
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-05-31


Aus $59x\equiv 5\ (99)$ folgt $5x\equiv 5\ (9)$ und $4x\equiv 5\ (11)$. Also $x\equiv 1\ (9)$ und $x\equiv 4\ (11)$. Dieses wird von $x\equiv 37\ (99)$ gelöst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bura
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 31.05.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2020-05-31


ich habe jetzt 59y ≡ 1 mod 99 berechnet, sehe aber immer noch nicht den Zusammenhang.

@JonyGo wo kann man diese Regeln nachlesen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2159
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-05-31

\(\begingroup\)\(\newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\tr}{\operatorname{tr}}\)
Wenn man in $\IQ$ die Gleichung $59x=5$ sieht, dann will man ja eigentlich beide Seiten mit $\frac 1{59}$ multiplizieren um nach $x$ aufzulösen. Das funktioniert, weil $59 \cdot \frac 1{59} = 1$ ist.

In $\IZ/99$ geht das nicht so leicht, weil $\frac 1{59}$ kein Element von $\IZ/99$ ist. Um die Gleichung $59x \equiv 5 \pmod{99}$ trotzdem zu lösen, könnten wir aber die Gleichung auf beiden Seiten mit einem $y\in \IZ/99$ multiplizieren, für dass $y\cdot 59 \equiv 1\pmod{99}$ gilt.

 
Wenn du den chinesischen Restsatz kennst, ist JonyGos Ansatz natürlich einfacher als der mit dem Euklidischen Algorithmus.

\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1454
Aus: Thüringen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-05-31


Ich löse sowas so:

59x-5=99y -> Normierung 59x+1=99y

59x+1=99y
59x+1=40y
19x+1=40y
19x+1=2y
x+1=2y

x=1,y=1

Rückführung:

19*1+1=2y,y=10
19x+1=40*10,x=21
59*21+1=40y,y=31
59*x+1=99*31,x=52

Zielführung für die -5

x=(-5*52) MOD 99 = 37

Somit 59*37 MOD 99 = 5


-----------------
Pech in der Liebe , Glück im Verlieren !!!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bura
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 31.05.2020
Mitteilungen: 8
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-06-02


Vielen Dank, hab es endlich verstanden!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bura hat die Antworten auf ihre/seine Frage gesehen.
Das Thema wurde von einem Senior oder Moderator abgehakt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]