Lösung der Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeigen Sie: Zwar besitzt die Gleichung 21xy - 7x -3y +1 = 0 keine Lösungen in [mm] \IZ [/mm] x [mm] \IZ, [/mm] aber die Kongruenz 21 xy -7x -3y +1 [mm] \equiv [/mm] 0 mod m ist lösbar für jedes natürliche m>1 |
Hallo, ich bins schon wieder!
Für den ersten Teil der Aufgabe habe ich die obige Gleichung schon zu (7x-1)*(3y-1) = 0 umgestellt und kam somit zu den Lösungen x = 1/7 [mm] \not\in \IZ [/mm] und y = 1/3 [mm] \not\in \IZ. [/mm]
Beim zweiten Teil weiß ich leider nicht mehr weiter. Es muss ja 7x [mm] \equiv [/mm] 1 mod m und 3y [mm] \equiv [/mm] 1 mod m erfüllt werden, aber wie geht es jetzt weiter?
Wäre toll, wenn mir jemand helfen könnte!
Grüße,
Maren
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:16 Di 06.02.2007 | | Autor: | unknown |
Hallo Maren,
Der erste Teil sieht ja schonmal recht gut aus.
> Beim zweiten Teil weiß ich leider nicht mehr weiter. Es
> muss ja 7x [mm]\equiv[/mm] 1 mod m und 3y [mm]\equiv[/mm] 1 mod m erfüllt
> werden, aber wie geht es jetzt weiter?
Jein, $7x [mm] \equiv [/mm] 1 [mm] \pmod{m}$ [/mm] oder (nicht "und") $3y [mm] \equiv [/mm] 1 [mm] \pmod{m}$ [/mm] sind hier im Allgemeinen nur hinreichende aber keine notwendigen Bedingungen, da der Ring [mm] $\IZ_m$ [/mm] je nach $m$ Nullteiler enthalten kann. Zum Beispiel ist $x = 1 = y$ eine Lösung für $m = 4$, obwohl $7 [mm] \equiv [/mm] 3 [mm] \not\equiv [/mm] 1 [mm] \pmod{m}$ [/mm] gilt.
Du kannst natürlich trotzdem versuchen, so vorzugehen. Falls $m$ kein Vielfaches von $21$ ist, kann man (warum?) immer $x$ oder $y$ finden mit $7x [mm] \equiv [/mm] 1 [mm] \pmod{m}$ [/mm] oder $3y [mm] \equiv [/mm] 1 [mm] \pmod{m}$. [/mm] Bei den Vielfachen von $21$ muß sich allerdings etwas anderes überlegen. Versuch doch mal Folgendes: Sei $m = [mm] 3^j 7^k [/mm] z$ mit $3 [mm] \;\not|\; [/mm] z$ und $7 [mm] \;\not|\; [/mm] z$ sowie $j [mm] \geq [/mm] 1$ und $k [mm] \geq [/mm] 1$. In der ursprünglichen Gleichung $21xy - 7x - 3y + 1 [mm] \equiv [/mm] 0 [mm] \pmod{m}$ [/mm] könnte man etwa $x = [mm] 7^{k-1} \tilde{x}$ [/mm] und $y = [mm] 3^{j-1} [/mm] z [mm] \tilde{y}$ [/mm] setzen. Dann muß man die Kongruenz $1 [mm] \equiv 7^k\tilde{x} [/mm] + [mm] (3^j [/mm] z) [mm] \tilde{y} \pmod{m}$ [/mm] lösen. Ich behaupte einfach mal, daß das jetzt etwas einfacher geworden ist: Man kann $1 = [mm] 7^{k}\tilde{x} [/mm] + [mm] (3^{j} [/mm] z) [mm] \tilde{y}$ [/mm] sogar schon in [mm] $\IZ$ [/mm] lösen.
> Wäre toll, wenn mir jemand helfen könnte!
Hoffe, das konnte ich.
|
|
|
| |
|
Hallo unknown!
> Jein, [mm]7x \equiv 1 \pmod{m}[/mm] oder (nicht "und") [mm]3y \equiv 1 \pmod{m}[/mm]
> sind hier im Allgemeinen nur hinreichende aber keine
> notwendigen Bedingungen, da der Ring [mm]\IZ_m[/mm] je nach [mm]m[/mm]
> Nullteiler enthalten kann. Zum Beispiel ist [mm]x = 1 = y[/mm] eine
> Lösung für [mm]m = 4[/mm], obwohl [mm]7 \equiv 3 \not\equiv 1 \pmod{m}[/mm]
> gilt.
Habe ich verstanden, klar.
> Du kannst natürlich trotzdem versuchen, so vorzugehen.
> Falls [mm]m[/mm] kein Vielfaches von [mm]21[/mm] ist, kann man (warum?) immer
> [mm]x[/mm] oder [mm]y[/mm] finden mit [mm]7x \equiv 1 \pmod{m}[/mm] oder [mm]3y \equiv 1 \pmod{m}[/mm].
Weil somit (7,m)=1 bzw. (3,m)=1 und es dann ein Inverses gibt?
Ab hier verstehe ich leider fast gar nichts mehr...
> Bei den Vielfachen von [mm]21[/mm] muß sich allerdings etwas anderes
> überlegen. Versuch doch mal Folgendes: Sei [mm]m = 3^j 7^k z[/mm]
> mit [mm]3 \;\not|\; z[/mm] und [mm]7 \;\not|\; z[/mm] sowie [mm]j \geq 1[/mm] und [mm]k \geq 1[/mm].
> In der ursprünglichen Gleichung [mm]21xy - 7x - 3y + 1 \equiv 0 \pmod{m}[/mm]
> könnte man etwa [mm]x = 7^{k-1} \tilde{x}[/mm] und [mm]y = 3^{j-1} z \tilde{y}[/mm]
> setzen. Dann muß man die Kongruenz [mm]1 \equiv 7^k\tilde{x} + (3^j z) \tilde{y} \pmod{m}[/mm]
> lösen.
Wie kommst du darauf?
> Ich behaupte einfach mal, daß das jetzt etwas
> einfacher geworden ist: Man kann [mm]1 = 7^{k}\tilde{x} + (3^{j} z) \tilde{y}[/mm]
> sogar schon in [mm]\IZ[/mm] lösen.
Leider nicht, ich bin jetzt total durcheinander...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:48 Di 06.02.2007 | | Autor: | unknown |
Hallo nochmal!
Schön, daß wir uns im ersten Teil schonmal einig sind. Die Aussage mit dem ggT ist genau das, was ich meinte.
> Ab hier verstehe ich leider fast gar nichts mehr...
Wollen mal sehen, ob wir das ändern können.
> > Bei den Vielfachen von [mm]21[/mm] muß sich allerdings etwas
> anderes
> > überlegen. Versuch doch mal Folgendes: Sei [mm]m = 3^j 7^k z[/mm]
> > mit [mm]3 \;\not|\; z[/mm] und [mm]7 \;\not|\; z[/mm] sowie [mm]j \geq 1[/mm] und [mm]k \geq 1[/mm].
> > In der ursprünglichen Gleichung [mm]21xy - 7x - 3y + 1 \equiv 0 \pmod{m}[/mm]
> > könnte man etwa [mm]x = 7^{k-1} \tilde{x}[/mm] und [mm]y = 3^{j-1} z \tilde{y}[/mm]
> > setzen. Dann muß man die Kongruenz [mm]1 \equiv 7^k\tilde{x} + (3^j z) \tilde{y} \pmod{m}[/mm]
> > lösen.
> Wie kommst du darauf?
Naja, wenn ich [mm] $\tilde{x}$ [/mm] und [mm] $\tilde{y}$ [/mm] finden kann, die $1 [mm] \equiv 7^k\tilde{x} [/mm] + [mm] (3^j [/mm] z) [mm] \tilde{y} \pmod{m}$ [/mm] lösen, dann lösen $x = [mm] 7^{k-1}\tilde{x}$ [/mm] und $y = [mm] 3^{j-1} [/mm] z [mm] \tilde{y}$ [/mm] doch die ursprüngliche Gleichung:
[mm] $\begin{matrix}
21xy - 7x - 3y + 1
&=& (3\cdot7) 7^{k-1} \tilde{x} 3^{j-1} z \tilde{y} - 7\cdot7^{k-1}\tilde{x} - 3\cdot3^{j-1}z\tilde{y} + 1 \\
&=& \underbrace{3^j 7^k z}_{= m} \tilde{x}\tilde{y} - 7^k \tilde{x} - (3^j z) \tilde{y} + 1 \\
&\equiv& 1 - 7^k\tilde{x} - (3^j z) \tilde{y} &\equiv& 0 \pmod{m}.
\end{matrix}$
[/mm]
> > Ich behaupte einfach mal, daß das jetzt etwas
> > einfacher geworden ist: Man kann [mm]1 = 7^{k}\tilde{x} + (3^{j} z) \tilde{y}[/mm]
> > sogar schon in [mm]\IZ[/mm] lösen.
>
> Leider nicht, ich bin jetzt total durcheinander...
Der Trick hierbei ist [mm] $(7^k, 3^j [/mm] z) = 1$, da $7 [mm] \not|\; [/mm] z$. Jetzt gibt es einen Satz über den ggT in Hauptidealbereichen (alternativ der erweiterte Euklidische Algorithmus), der etwas über die Lösbarkeit der Gleichung [mm] $7^k \tilde{x} [/mm] + [mm] (3^j [/mm] z) [mm] \tilde{y} [/mm] = 1$ aussagt.
Vielleicht kommst Du jetzt weiter.
|
|
|
| |
|
Hallo auch von mir nochmal!
> Naja, wenn ich [mm]\tilde{x}[/mm] und [mm]\tilde{y}[/mm] finden kann, die [mm]1 \equiv 7^k\tilde{x} + (3^j z) \tilde{y} \pmod{m}[/mm]
> lösen, dann lösen [mm]x = 7^{k-1}\tilde{x}[/mm] und [mm]y = 3^{j-1} z \tilde{y}[/mm]
> doch die ursprüngliche Gleichung:
>
> [mm]$\begin{matrix}
21xy - 7x - 3y + 1
&=& (3\cdot7) 7^{k-1} \tilde{x} 3^{j-1} z \tilde{y} - 7\cdot7^{k-1}\tilde{x} - 3\cdot3^{j-1}z\tilde{y} + 1 \\
&=& \underbrace{3^j 7^k z}_{= m} \tilde{x}\tilde{y} - 7^k \tilde{x} - (3^j z) \tilde{y} + 1 \\
&\equiv& 1 - 7^k\tilde{x} - (3^j z) \tilde{y} &\equiv& 0 \pmod{m}.
\end{matrix}$[/mm]
Ok, das habe ich jetzt auch verstanden.
> Der Trick hierbei ist [mm](7^k, 3^j z) = 1[/mm], da [mm]7 \not|\; z[/mm].
> Jetzt gibt es einen Satz über den ggT in
> Hauptidealbereichen (alternativ der erweiterte Euklidische
> Algorithmus), der etwas über die Lösbarkeit der Gleichung
> [mm]7^k \tilde{x} + (3^j z) \tilde{y} = 1[/mm] aussagt.
Naja, leider habe ich immer noch nicht so den Durchblick. Ich weiss nur, dass es aufgrund [mm](7^k, 3^j z) = 1[/mm] nun eindeutig bestimmte Lösungen für [mm]\tilde {x} [/mm] und [mm] \tilde {y} [/mm] gibt. Ich kann aber irgendwie nicht mit den Zahlen [mm]7^k [/mm] und [mm] 3^j z [/mm] umgehen...
Trotzdem schon mal Danke für die ganzen vorherigen Tips!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:55 Mi 07.02.2007 | | Autor: | unknown |
Moin,
> > Der Trick hierbei ist [mm](7^k, 3^j z) = 1[/mm], da [mm]7 \not|\; z[/mm].
> > Jetzt gibt es einen Satz über den ggT in
> > Hauptidealbereichen (alternativ der erweiterte Euklidische
> > Algorithmus), der etwas über die Lösbarkeit der Gleichung
> > [mm]7^k \tilde{x} + (3^j z) \tilde{y} = 1[/mm] aussagt.
>
> Naja, leider habe ich immer noch nicht so den Durchblick.
> Ich weiss nur, dass es aufgrund [mm](7^k, 3^j z) = 1[/mm] nun
> eindeutig bestimmte Lösungen für [mm]\tilde {x}[/mm] und [mm]\tilde {y}[/mm]
> gibt. Ich kann aber irgendwie nicht mit den Zahlen [mm]7^k[/mm] und
> [mm]3^j z[/mm] umgehen...
Ich verstehe Dein Problem nicht. Wenn Du weißt, daß es [mm] $\tilde{x}$ [/mm] und [mm] $\tilde{y}$ [/mm] gibt, die die Gleichung [mm] $7^k \tilde{x} [/mm] + [mm] (3^j [/mm] z) [mm] \tilde{y} [/mm] = 1$ lösen, dann gilt doch insbesondere auch $1 - [mm] 7^k \tilde{x} [/mm] - [mm] (3^j [/mm] z) [mm] \tilde{y} \equiv [/mm] 0 [mm] \pmod{m}$. [/mm] Naja, und mit der Rechnung weiter oben ist dann $x = [mm] 7^{k-1}\tilde{x}$ [/mm] und $y = [mm] 3^{j-1}z\tilde{y}$ [/mm] eine Lösung der ursprünglichen Kongruenz $21xy - 7x - 3y + 1 [mm] \equiv [/mm] 0 [mm] \pmod{m}$. [/mm] Und mehr war doch gar nicht verlangt, oder?
> Trotzdem schon mal Danke für die ganzen vorherigen Tips!
Freut mich, daß ich helfen konnte.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:44 Do 08.02.2007 | | Autor: | frustriert |
Ach jetzt... 
Ich habe die ganze Zeit geglaubt, ich müsste eine "spezielle Zahl" als Lösung angeben, dabei sollte ich ja nur zeigen, dass die Kongruenz mod m lösbar ist...
Danke nochmal!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:58 Di 06.02.2007 | | Autor: | blascowitz |
Guten Abend. Ich wollte mal meine Idee zu der Aufgabe 21xy-3x-7y+1 [mm] \equiv [/mm] 0 mod m anbieten.
Also ich würde zwei Fälle unterscheiden
Fall 1 [mm] m\in \mathcal{P}. [/mm]
(7x-1)*(3y-1) ist niemals eine Primzahl, da x,y [mm] \in \IZ [/mm] und die Zahl immer mindestens zwei Teiler von 1 verschieden hat. Da das so ist ist die Konkruenz hier bewiesen aufgrund der Eindeutigkeit der Primfaktorenzerlegung.
Ist m keine Primzahl, lässt sich m in Primfaktoren zerlegen, für die dann (7x-1)*(3y-1= [mm] \equiv [/mm] 0 mod allen Primteilern von m. Da das nun wieder Primteiler sind und (7x-1)*(3y-1) niemals eine Primzahl wird sind die kongruenzen auch hier aufgrund der Eindeutigkeit der Primfaktorenzerlegung gegeben. Ist (7x-1)*(3y-1) durch alle Primfaktoren teilbar, so ist es auch teilbar durch das Produkt der Primfaktoren. q.e.d.
Ich hoffe ich liege nicht ganz falsch
|
|
|
|
