Primfaktorzerlegung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:00 Do 12.08.2010 | | Autor: | duda |
| Aufgabe | Bestimme die Primfaktorzerlegung von:
- [mm] 2^{13} [/mm] - 1
- [mm] 5^{6} [/mm] + [mm] 5^{3} [/mm] + 1 |
hallo zusammen,
und zwar bin ich gerade auf diese übung gestoßen, die mir ziemliche kopfschmerzen bereitet!
bei pfz von einfachen zahlen habe ich überhaupt keine probleme, aber sowas?!?
kann mir da bitte jmd helfen?
hab mir auch schon überlegt, dass man vllt den kleinen fermat anwenden könnte, da die exponente und basis jeweils teilerfremd sind - aber auch da wüsste ich jetzt nicht wie ich das angehen sollte...
besten gruß,
duda.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:15 Do 12.08.2010 | | Autor: | duda |
also mit dem euler - fermat gehe ich wie folgt vor:
[mm] 2^{p-1} \equiv [/mm] 1 mod p
[mm] \Rightarrow [/mm] 13 | p-1 [mm] \gdw [/mm] p-1 = 13*x, x [mm] \in \IN.
[/mm]
[mm] \Rightarrow [/mm] p = 13*x + 1.
so, und wie gehe ich jetzt vor (sofern dieser weg stimmen sollte)?
und zum zweiten fällt mir leider nichts ein, wie ich das angehen sollte.
|
|
|
| |
|
Hallo duda, vorab und weils letzte Woche niemand gesagt hat:
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Ich sehe keinen Weg, hier über Euler oder sonstwen eine Primfaktorenzerlegung zu bestimmen. Manchmal gibt ja der Kontext (hier also: die umgebenden Übungsaufgaben) noch einen Hinweis, wie der Aufgabensteller vorzugehen gedachte, aber hier habe ich keine Idee.
Zur ersten Aufgabe: unter den Zahlen der Form [mm] 2^p-1 [/mm] gibt es überdurchschnittlich viele Primzahlen. Daher sind einzelne Tests entwickelt worden, die zerlegbare Zahlen mit einiger Wahrscheinlichkeit erkennen, so dass man sich die genauere Untersuchung einer sicher zerlegbaren Zahl dann weiter sparen kann. Das verkürzt Rechenzeiten, aber darum wird es hier wohl kaum gehen - es sei denn, Ihr hattet solche Testverfahren.
Im übrigen ist [mm] 2^{13}-1=8191 [/mm] prim.
Zur zweiten Aufgabe: das Polynom [mm] f(x)=x^6+x^3+1 [/mm] hat keine Nullstellen. Es ist aber in [mm] \IR [/mm] sicher zerlegbar. Aber auch hier gilt wohl: das ist doch gerade nicht euer Thema, oder?
[mm] 5^6+5^3+1=15751=19*829
[/mm]
Ich vermute, Du zerbrichst Dir also unnötig den Kopf.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:01 Do 12.08.2010 | | Autor: | duda |
erstmal danke dir für deinen willkommensgruß, sehr nett. :)
hmm, also das problem ist ja, dass wir keinen taschenrechner benutzen dürfen - weder in den übungen noch in der klausur! sonst wär das ja überhaupt kein problem...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:19 Do 12.08.2010 | | Autor: | PeterB |
Ich kann vielleicht noch ein paar Bemerkungen ergänzen:
Das Polynom [mm] $X^{13}-1$ [/mm] faktorisiert über [mm] $\mathbb [/mm] Q$ (oder [mm] $\mathbb [/mm] Z$) genau in [mm] $(X-1)(X^{12}+X^{11}+ [/mm] ...+X+1)$ wobei der lineare Faktor Dir nicht hilft (weil er den Wert 1 annimmt wenn man 2 einsetzt) und der Faktor vom Grad 12 das 12te Kreisteilungspolynom ist und daher irreduzibel. Weiterhin ist [mm] $X^6+X^3+1$ [/mm] das 9te Kreisteilungpolynom und daher auch irreduzibel und es teilt [mm] $X^9-1$.
[/mm]
Ganz ohne rechnen ist diese Aufgabe wohl nicht zu lösen, aber wir können im ersten Fall feststellen: Falls p eine Primzahl ist, die [mm] $2^{13}-1$ [/mm] teilt, dann ist die (multiplikative) Ordnung von 2 modulo p ein Teiler von 13. Da es aber keine Primzahl p mit [mm] $2^1\equiv [/mm] 1 [mm] \mod [/mm] p$ gibt, kann die Ordnung nicht 1 sein, sie ist also 13. Damit folgt: 13( die Ordnung von 2) Teilt die Ordnung der multiplikativen Gruppe mod p also p-1. Da p offensichtlich ungerade ist, folgt direkt: 26|p-1 . Jetz muss man also noch ausschließen, dass [mm] $2^{13}-1$ [/mm] durch eine kleinere Primzahl geteilt werden kann, es reicht also alle Primzahlen der Form $26k+1$ die kleiner als [mm] $\sqrt{2^{13}-1}<91$ [/mm] sind überprüfen. Die verbleibenden Fälle sind k=2,3 also die Primzahlen 53 und 79.
Bei der zweiten Aufgabe kann man analog Folgern, dass für jeden Primfaktor p gilt die Ordnung von 5 mod p ist 3 oder 9 und 3 kann man wohl mit weiteren Überlegungen ausschließen und dann analog folgern, dass p-1 von 18 geteilt wird. (Nachdem man 19 als Faktor gefunden hat ist die Zahl und deren Wurzel ja ziemlich klein.)
Hm, das ist alles nicht so schön, aber ich denke so kann man es mit einem Taschenrechner in überschaubarer Zeit schaffen.
Gruß
Peter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:09 Do 12.08.2010 | | Autor: | duda |
> Jetz muss man also
> noch ausschließen, dass [mm]2^{13}-1[/mm] durch eine kleinere
> Primzahl geteilt werden kann, es reicht also alle
> Primzahlen der Form [mm]26k+1[/mm] die kleiner als
> [mm]\sqrt{2^{13}-1}<91[/mm] sind überprüfen. Die verbleibenden
> Fälle sind k=2,3 also die Primzahlen 53 und 79.
>
kannst du mir bitte diesen schritt nochmal erklären, irgendwie ist der mir nicht einleuchtend... :S
> Bei der zweiten Aufgabe kann man analog Folgern, dass für
> jeden Primfaktor p gilt die Ordnung von 5 mod p ist 3 oder
> 9...
wie kommst du denn darauf? wär echt nett, wenn du mir auch dies erklären könntest...
leider dürfen wir ja keine taschenrechner benutzen, sonst wären mir diese grübelein echt erspart geblieben ;(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:38 Do 12.08.2010 | | Autor: | felixf |
Moin!
> > Jetz muss man also
> > noch ausschließen, dass [mm]2^{13}-1[/mm] durch eine kleinere
> > Primzahl geteilt werden kann, es reicht also alle
> > Primzahlen der Form [mm]26k+1[/mm] die kleiner als
> > [mm]\sqrt{2^{13}-1}<91[/mm] sind überprüfen. Die verbleibenden
> > Fälle sind k=2,3 also die Primzahlen 53 und 79.
>
> kannst du mir bitte diesen schritt nochmal erklären,
> irgendwie ist der mir nicht einleuchtend... :S
Bisher hatten wir: ist $p$ eine Primzahl, die [mm] $2^{13} [/mm] - 1$ teilt, so ist $p = 26 k + 1$ fuer ein $k [mm] \in \IN$.
[/mm]
Weiterhin: ist [mm] $2^{13} [/mm] - 1$ nicht prim, so gibt es mindestens einen Primteiler [mm] $\le \sqrt{2^{13} - 1} [/mm] < 91$.
Da $26 k + 1 [mm] \ge [/mm] 91$ ist fuer $k [mm] \ge [/mm] 4$, bleiben also die Moeglichkeiten $p = 27$ (ist keine Primzah), $p = 53$ und $p = 79$.
Um zu testen, ob 53 oder 79 Teiler von [mm] $2^{13} [/mm] - 1$ sind, musst du also [mm] $2^{13} \overset{?}{\equiv} [/mm] 1 [mm] \pmod{53}$ [/mm] und [mm] $2^{13} \overset{?}{\equiv} [/mm] 1 [mm] \pmod{79}$ [/mm] testen.
Das kannst du jetzt von Hand ausrechnen, wenn du willst. Beachte z.B.: [mm] $2^6 [/mm] = 64 [mm] \equiv [/mm] 11 [mm] \pmod{53}$, [/mm] womit [mm] $2^{12} \equiv 11^2 [/mm] = 121 [mm] \equiv [/mm] 15 [mm] \pmod{53}$ [/mm] ist, und somit [mm] $2^{13} \equiv [/mm] 2 [mm] \cdot [/mm] 15 = 30 [mm] \pmod{53}$ [/mm] ist, also nicht 1. Damit ist 53 kein Teiler von [mm] $2^{13} [/mm] - 1$.
Jetzt musst du noch 79 testen. Ist es ebenfalls kein Teiler von [mm] $2^{13} [/mm] - 1$, so ist [mm] $2^{13} [/mm] - 1$ prim.
> > Bei der zweiten Aufgabe kann man analog Folgern, dass für
> > jeden Primfaktor p gilt die Ordnung von 5 mod p ist 3 oder
> > 9...
> wie kommst du denn darauf? wär echt nett, wenn du mir
> auch dies erklären könntest...
Es wurde im Thread erwaehnt, dass [mm] $X^6 [/mm] + [mm] X^3 [/mm] + 1$ das 9-te Kreisteilungspolynom ist. Damit ist [mm] $X^9 [/mm] - 1 = [mm] (X^6 [/mm] + [mm] X^3 [/mm] + 1) [mm] (X^3 [/mm] - 1)$.
Eine Nullstelle [mm] $\alpha$ [/mm] von [mm] $X^6 [/mm] + [mm] X^3 [/mm] + 1$ ist also auch eine von [mm] $X^9 [/mm] - 1$, erfuellt also [mm] $\alpha^9 [/mm] = 1$. Das gilt auch modulo $p$.
Daraus folgt [mm] $5^9 \equiv [/mm] 1 [mm] \pmod{p}$. [/mm] Und da $9 = 3 [mm] \cdot [/mm] 3$ ist kann bereits [mm] $5^3 \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] sein, oder sogar [mm] $5^1 \equiv [/mm] 1 [mm] \pmod{p}$.
[/mm]
Die letzte Moeglichkeit kannst du ziemlich schnell ausschliessen. Die vorletzte kannst du auch recht einfach anschauen: dazu muss $p$ ein Teiler von [mm] $5^3 [/mm] - 1 = 124 = 4 [mm] \cdot [/mm] 31$ sein. Weiterhin muss $3$ ein Teiler von $p - 1$ sein. Damit musst du nur noch $p = 31$ testen.
Schliesslich hast du noch [mm] $5^9 \equiv [/mm] 1 [mm] \pmod{p}$; [/mm] dann weisst du auch, dass [mm] $5^3 \not\equiv [/mm] 1 [mm] \pmod{p}$ [/mm] ist, womit $9$ ein Teiler von $p - 1$ sein muss.
LG Felix
|
|
|
|
![[]](/images/popup.gif){kind=small}
Dario Alpern
