Lösung der Kongruenz finden < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:01 Mo 20.10.2014 | | Autor: | evinda |
Hallo!!!
Wenn man die Kongruenz 2x [mm] \equiv [/mm] 1 [mm] \pmod {5^n} [/mm] hat, dann kann man die Lösung finden, indem man die Formel [mm] x=\frac{5^n+1}{2} [/mm] benutzt.
Wenn man die Kongruenz ax [mm] \equiv [/mm] b [mm] \pmod{ 5^n} [/mm] hat, kann man dann auch die Lösung von der Formel [mm] x=\frac{5^n+b}{a} [/mm] finden?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:35 Mo 20.10.2014 | | Autor: | Marcel |
Hallo,
> Hallo!!!
>
> Wenn man die Kongruenz 2x [mm]\equiv[/mm] 1 [mm]\pmod {5^n}[/mm] hat, dann
> kann man die Lösung finden, indem man die Formel
> [mm]x=\frac{5^n+1}{2}[/mm] benutzt.
das habe ich nicht nachgeprüft.
> Wenn man die Kongruenz ax [mm]\equiv[/mm] b [mm]\pmod{ 5^n}[/mm] hat, kann
> man dann auch die Lösung von der Formel [mm]x=\frac{5^n+b}{a}[/mm]
> finden?
Woher kommt denn dieser Ansatz? Ich kenne folgendes:
Sei die Kongruenz
$ax [mm] \equiv [/mm] b$ [mm] $\mod$ $n\,$
[/mm]
gegeben.
Diese ist dann und nur dann lösbar (in $x [mm] \in \IZ$), [/mm] wenn
[mm] $\ggT(a,n)\;|\;b$
[/mm]
gilt.
Sei nun [mm] $d:=ggT(a,n)=\red{y}*a+z*n$ [/mm] mit $y,z [mm] \in \IZ,$ [/mm] eine solche Darstellung erhält man etwa
mit dem erweiterten euklidischen Algorithmus. Dann ist, im Falle der Lösbarkeit,
obige Kongruenz äquivalent zu
$x [mm] \equiv \red{\,y\,}*\frac{b}{d}$ $\mod \frac{n}{d}\,.$
[/mm]
Hier sieht man schonmal direkt schön, dass etwa im Falle, dass [mm] $a=5\,$ [/mm] ist, sicher
diese Kongruenz gar keine Lösung hat (denn [mm] $|\ggT(5,5^n)| \ge [/mm] 5$ zeigt, dass [mm] $\ggT(5,5^n) \nmid 1\,$).
[/mm]
Bei der Kongruenz
$2x [mm] \equiv [/mm] 1 [mm] \mod 5^n$
[/mm]
sehe ich etwa:
Im Falle [mm] $n=1\,$ [/mm] ist [mm] $1=\red{\,-2\,}*2+1*5\,.$
[/mm]
Im Falle [mm] $n=2\,$ [/mm] ist [mm] $1=\red{\,-12\,}*2+1*5^2\,.$
[/mm]
Im Falle [mm] $n=3\,$ [/mm] ist [mm] $1=\red{\,-62\,}*2+1*5^3\,.$
[/mm]
Im Falle [mm] $n=4\,$ [/mm] ist [mm] $1=\red{\,-312\,}*2+1*5^4\,.$
[/mm]
Im Falle [mm] $n=5\,$ [/mm] ist [mm] $1=\red{\,-1562\,}*2+1*5^4\,.$
[/mm]
Also ist dort wohl
[mm] $y=y(n)=5*y(n-1)-2\,$ [/mm] mit [mm] $y(1)=-2\,,$
[/mm]
was sich wohl induktiv zeigen lassen wird.
Daher ist die Ausgangskongruenz äquivalent zu
$x [mm] \equiv y(n)*\frac{1}{1} \mod \frac{5^n}{1}\,.$
[/mm]
Um Deine Formel zu beweisen, sollte man nun
[mm] $\frac{5^n+1}{2} \equiv [/mm] y(n) [mm] \mod 5^n$
[/mm]
beweisen. Für [mm] $n=1\,$ [/mm] steht da
$3 [mm] \equiv [/mm] -2 [mm] \mod 5\,,$
[/mm]
passt also.
Für [mm] $n=2\,$ [/mm] steht da
$13 [mm] \equiv [/mm] -12 [mm] \mod 25\,.$
[/mm]
Für [mm] $n=3\,$ [/mm] steht da
[mm] $\frac{5^3+1}{2}=63 \equiv -62\mod 125\,.$
[/mm]
Eventuell kann man ja induktiv etwa
[mm] $5^n=\frac{5^n+1}{2}-y(n)$
[/mm]
beweisen.
Z.B. haben wir oben ja auch [mm] $y(5)=-1562\,$ [/mm] ausgerechnet, und in der Tat gilt
einerseits
[mm] $\frac{5^5+1}{2}+1562=3125\,,$
[/mm]
sowie andererseits
[mm] $5^5=3125\,.$
[/mm]
Nebenbei: Dass [mm] $2*\frac{5^n+1}{2} \equiv [/mm] 1 [mm] \mod 5^n$ [/mm] gilt, ist natürlich eine
Trivialität, weil [mm] $2*\frac{5^n+1}{2}=5^n+1\,.$ [/mm] Es fehlt aber durchaus noch eine
Begründung, warum man mit [mm] $\IL=\left[\frac{5^n+1}{2}\right]_5$ [/mm] auch die ganze
Lösungsmenge von
$2x [mm] \equiv [/mm] 1 [mm] \mod 5^n$
[/mm]
gefunden hat. Mit obigem Satz folgt das, wenn Du die angesprochene
Kongruenz
[mm] $\frac{5^n+1}{2} \equiv [/mm] y(n) [mm] \mod 5^n$
[/mm]
beweist - und natürlich zuvor die Formel für [mm] $y(n)\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:39 Mo 20.10.2014 | | Autor: | Marcel |
Hallo,
> Hallo!!!
>
> Wenn man die Kongruenz 2x [mm]\equiv[/mm] 1 [mm]\pmod {5^n}[/mm] hat, dann
> kann man die Lösung finden, indem man die Formel
> [mm]x=\frac{5^n+1}{2}[/mm] benutzt.
>
> Wenn man die Kongruenz ax [mm]\equiv[/mm] b [mm]\pmod{ 5^n}[/mm] hat, kann
> man dann auch die Lösung von der Formel [mm]x=\frac{5^n+b}{a}[/mm]
> finden?
nochmal in einem etwas wacheren Zustand von mir:
Für
$ax [mm] \equiv [/mm] b [mm] \mod 5^n$
[/mm]
ist natürlich
[mm] $x=\frac{5^n+b}{a}$
[/mm]
jedenfalls dann eine Lösung, wenn [mm] $\frac{5^n+b}{a} \in \IZ\,.$
[/mm]
Das folgt ja sofort durch einsetzen.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:39 Di 21.10.2014 | | Autor: | evinda |
Also wenn man die Kongruenz 8x [mm] \equiv [/mm] 3 [mm] \pmod {5^2} [/mm] lösen will, weiß man dass die Lösung die folgende ist?
[mm] x=\frac{5^2+3}{8}=\frac{28}{8} \notin \mathbb{Z}
[/mm]
Falls ja, heißt das,dass die Kongruenz keine Lösung hat?
|
|
|
| |
|
> Also wenn man die Kongruenz 8x [mm]\equiv[/mm] 3 [mm]\pmod {5^2}[/mm] lösen
> will, weiß man dass die Lösung die folgende ist?
>
> [mm]x=\frac{5^2+3}{8}=\frac{28}{8} \notin \mathbb{Z}[/mm]
>
> Falls ja, heißt das,dass die Kongruenz keine Lösung hat?
Hallo,
nein, das heißt es nicht.
Mit dem erweiterten euklidischen Algorithmus findest Du ganze Zahlen a und b so, daß 1=a*8+b*25.
Es ist 1=-3*8+1*25
Wir haben also 1=-3*8 (mod 25),
also ist 3=-9*8 (mod 25),
damit haben wir: alle ganzen Zahlen x mit
[mm] x\equiv [/mm] -9=16 (mod 25) lösen die Gleichung.
LG Angela
>
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:09 Di 21.10.2014 | | Autor: | Marcel |
Hallo,
> Also wenn man die Kongruenz 8x [mm]\equiv[/mm] 3 [mm]\pmod {5^2}[/mm] lösen
> will, weiß man dass die Lösung die folgende ist?
>
> [mm]x=\frac{5^2+3}{8}=\frac{28}{8} \notin \mathbb{Z}[/mm]
>
> Falls ja, heißt das,dass die Kongruenz keine Lösung hat?
wie Angela schon sagte: Nö.
Schau' in den von mir erwähnten Satz:
Weil [mm] $\ggT(8,3)=1\,$ [/mm] ein Teiler von [mm] $25\,$ [/mm] ist, ist diese Kongruenz lösbar...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:35 Mi 22.10.2014 | | Autor: | Marcel |
Hallo,
nur nochmal nebenbei:
> Also wenn man die Kongruenz 8x [mm]\equiv[/mm] 3 [mm]\pmod {5^2}[/mm] lösen
> will, weiß man dass die Lösung die folgende ist?
>
> [mm]x=\frac{5^2+3}{8}=\frac{28}{8} \notin \mathbb{Z}[/mm]
>
> Falls ja, heißt das,dass die Kongruenz keine Lösung hat?
ich hatte gesagt:
> Für
> $ ax [mm] \equiv [/mm] b [mm] \mod 5^n [/mm] $
> ist natürlich
> $ [mm] x=\frac{5^n+b}{a} [/mm] $
> eine Lösung, falls [mm] $\frac{5^n+b}{a} \in \IZ\,.$
[/mm]
D.h.:
[mm] $x_0:=\frac{5^n+b}{a} \in \IZ$
[/mm]
[mm] $\Rightarrow$ $x_0$ [/mm] ist Lösung von $ax [mm] \equiv [/mm] b [mm] \mod 5^n\,.$
[/mm]
Wenn eine Folgerung
$A [mm] \Rightarrow [/mm] B$
gilt, dann gilt natürlich keineswegs zugleich
[mm] $\neg [/mm] A [mm] \Rightarrow \neg B\,,$
[/mm]
sondern nur (in äquivalenter Weise)
[mm] $\neg [/mm] B [mm] \Rightarrow \neg A\,.$
[/mm]
(Kontraposition!)
Anders gesagt: Ich hätte oben in gleichwertiger Weise nur sagen können:
Wenn gilt, dass
[mm] $x_0=\frac{5^2+3}{8}$ [/mm] keine Lösung von $8x [mm] \equiv [/mm] 3 [mm] \mod [/mm] 25$
ist, dann gilt auch
[mm] $x_0=\frac{5^2+3}{8}\red{\,\notin\;\IZ}\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:52 Mi 22.10.2014 | | Autor: | leduart |
Hallo
durch 8 (oder eine andere Zahl zu dividieren macht in mod Rechnungen keinen Sinn, es sei denn, du interpretierst als 1/8 das multiplikative Inverse zu 8 und das ist -3 oder 22.
also steht da [mm] (5^2+3)*22 [/mm] oder *(-3)
Gruß leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:38 Mi 22.10.2014 | | Autor: | Marcel |
Hallo,
> Hallo
> durch 8 (oder eine andere Zahl zu dividieren macht in mod
> Rechnungen keinen Sinn, es sei denn, du interpretierst als
> 1/8 das multiplikative Inverse zu 8 und das ist -3 oder
> 22.
ne, da war sicher mit
[mm] $\frac{5^n+b}{a}$
[/mm]
der Bruch in [mm] $\IR$ [/mm] gemeint. Und das macht bedingt durchaus Sinn. Falls
dieser Bruch auch in [mm] $\IZ$ [/mm] ist, kennen wir eine Lösung (in [mm] $\IZ$), [/mm] und dann können
wir gucken, zu welcher Äquivalenzklasse mod [mm] $5^n$ [/mm] diese gehört.
Für [mm] $a=2\,$ [/mm] und [mm] $b=1\,$ [/mm] habe ich das doch
hier (klick!)
gemacht.
Aber Deine Andeutung ist auch gut, denn damit kann man sich vielleicht
auf anderem Wege erklären, wann
$ax [mm] \equiv [/mm] b$ [mm] $\mod [/mm] n$
lösbar ist und wann nicht (Existenz eines "multiplikativ inversen" von ... in [mm] $\IZ/n\IZ$...)
[/mm]
Gruß,
Marcel
|
|
|
|
