Polynome im Restklassenring < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | sei m [mm] \in [/mm] N . Bestimme die Anzahl a(m) der mod m inkongruenten Lösungen x der Kongruenz [mm] x^2 \equiv [/mm] x (mod m)
|
Also ich habe lang drüber nachgedacht um dann schlussendlich zu einem unglaublich trivialen Ergebniss zu kommen.
Die einzige Lösungsmenge die ich bennen konnte war
a(m)=m -#{n<m | [mm] m|(n^2-n) [/mm] }
aber wirklich konkret ist das nun auch nicht.
hat jemand vielleicht nen Tipp wie ich da weiter machen kann?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:16 Mo 03.12.2007 | | Autor: | felixf |
Hallo.
> sei m [mm]\in[/mm] N . Bestimme die Anzahl a(m) der mod m
> inkongruenten Lösungen x der Kongruenz [mm]x^2 \equiv[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
x (mod
> m)
>
> Also ich habe lang drüber nachgedacht um dann
> schlussendlich zu einem unglaublich trivialen Ergebniss zu
> kommen.
> Die einzige Lösungsmenge die ich bennen konnte war
>
> a(m)=m -#{n<m | [mm]m|(n^2-n)[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
>
> aber wirklich konkret ist das nun auch nicht.
Nein, das ist nur eine Umformulierung der Aufgabenstellung.
> hat jemand vielleicht nen Tipp wie ich da weiter machen
> kann?
Du benoetigst die Primfaktorzerlegung von $m$. Wenn du diese hast, benutzt du den Chinesischen Restsatz, um das Problem modulo $p^\ell$ zu betrachten, wobei $p$ eine Primzahl und $\ell \in \IN_{>0}$ ist.
Jetzt beachte, dass $x^2 \equiv x$ aequivalent zu $x (x - 1) \equiv 0$ ist. Und da $x$ und $x - 1$ immer teilerfremd sind, ist das genau dann durch $p^\ell$ teilbar, wenn schon $x$ oder $x - 1$ durch $p^\ell$ teilbar sind.
LG Felix
|
|
|
| |
|
hmmm... ungefähr soweit war ich heute auch schon nur leider macht es noch nicht klick. ich meine, dass ist alles verstädnlich und irgendwie auch klar.
aber wenn nun die [mm] p_{i}\alpha_{i} [/mm] alle x bzw. (x-1) teilen dann kann ich doch immernoch keine Anzahl an Lösungen dafür finden. Mann ich seh den Wald wohl vor lauter Bäumen nicht
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:42 Di 04.12.2007 | | Autor: | felixf |
Hallo
> hmmm... ungefähr soweit war ich heute auch schon nur leider
> macht es noch nicht klick. ich meine, dass ist alles
> verstädnlich und irgendwie auch klar.
> aber wenn nun die [mm]p_{i}\alpha_{i}[/mm] alle x bzw. (x-1) teilen
> dann kann ich doch immernoch keine Anzahl an Lösungen dafür
> finden. Mann ich seh den Wald wohl vor lauter Bäumen nicht
Na dann waehlen wir doch mal ein festes $p$ und ein festes [mm] $\alpha$. [/mm] Wieviele $x$ aus der Menge [mm] $\{ 0, 1, 2, \dots, p^\alpha - 1 \}$ [/mm] haben die Eigenschaft, dass entweder $x$ oder $x - 1$ durch [mm] $p^\alpha$ [/mm] geteilt wird?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:02 Mi 05.12.2007 | | Autor: | BobBoraxo |
Ja okay. Es sind 2 ! durch den chinesischen Restsatz hätten wir also jeweils 2 Lösungen pro Primfaktor, was alles in allem [mm] 2^n [/mm] verschiedene Möglichkeiten bei n verschiedenen Primfaktoren bedeutet , oder?!
Jedenfalls habe ich sowas rausbekommen als ich es mal auf etwas anderem wege probiert habe:
Sei [mm] m:=\produkt_{i=1}^{n} p_{i}^\alpha
[/mm]
dann finden wir zu jeder zerlegung
[mm] \produkt_{i=1}^{n-1} p_{i}^\alpha [/mm] und [mm] p_{n}^\alpha
[/mm]
x,y [mm] \in \IZ [/mm] so dass
[mm] x*(\produkt_{i=1}^{n-1} p_{i}^\alpha)+y*p_{n}^\alpha=1
[/mm]
[mm] x*(\produkt_{i=1}^{n-1} p_{i}^\alpha)-1=-y*p_{n}^\alpha
[/mm]
=> setze für [mm] X^2\equivX [/mm]
[mm] X=x*(\produkt_{i=1}^{n-1} p_{i}^\alpha)
[/mm]
mit X(X-1) [mm] \equiv [/mm] 0 mod(m)
=> [mm] x*(\produkt_{i=1}^{n-1} p_{i}^\alpha)*(-y*p_{n}^\alpha)\equiv [/mm] 0 (mod m)
und da es [mm] 2^n [/mm] verschiedene zerlegungen der n Primteiler gibt gibt es dementsprechend auch [mm] 2^n [/mm] verschiedene Lösungen.
Das einzige was mir noch ein wenig probleme bereitet ist zu zeigen, dass die x,y [mm] \in \IZ [/mm] paarweise verschieden sind
|
|
|
|
