Mersenne Zahlen & andere zahlentheoretische Fragen

19.11.2006, 21:51

piloan

Mersenne Zahlen & andere zahlentheoretische Fragen

Hi jungs
habe folgende Aufgabe...

$\begin{eqnarray*} M_n:=2^n-1 \end{eqnarray*}$ sind die Mersenne Zahlen.

ZZ:
1.)Ist $\begin{eqnarray*} M_n:=2^n-1 \end{eqnarray*}$ eine Primzahl so ist n eine Primzahl

2.)Gibt es Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ fuer die $\begin{eqnarray*} M_p \end{eqnarray*}$ keine Primzahl ist.Diskutiere die Fälle p=2,3,5,7,11,13 Hinweis : Fuer einen moeglichen Primteiler q von a gilt $\begin{eqnarray*} q \leq \sqrt{a} \end{eqnarray*}$

3.) $\begin{eqnarray*} 47|M_{23} \end{eqnarray*}$ durch Berechnung $\begin{eqnarray*} 2^{23}=((32)^2)^2 *2^3 mod 47 \end{eqnarray*}$

ok zu
1.) Denke das geht so:
n ist keine Primzahl laesst sich somit als n=ab darstellen a,b>1 ( klar)

nun folgt
$\begin{eqnarray*} 2^n-1=2^{ab}-1=((2^a)^{b}) -1 = (2^a-1)(((2^{a})^{b-1})+...2^a+1) \end{eqnarray*}$ nun hab ich einen Teiler von M gefunden : $\begin{eqnarray*} (2^a-1) \end{eqnarray*}$ .Daraus folgt,dass n eine Primzahl sein muss damit das gleiche fuer $\begin{eqnarray*} M_n:=2^n-1 \end{eqnarray*}$

zu 2.)
fuer p=2 ,3 ,4 ,5 gilt .....wuerd ich jetzt einfach hinschreiben und ausrechnen ..weiss nicht ob das damit gemeint ist ....und dann seh ich bei p=11 $\begin{eqnarray*} M_11:=2^{11}-1=23*89 \end{eqnarray*}$ damit gibt es Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ fuer die $\begin{eqnarray*} M_p \end{eqnarray*}$ keine Primzahl ist.
Den Hinweis kann ich noch nicht so richtig einordnen ....soll ich dazu noch was beweisen ?

zu3.)

$\begin{eqnarray*} 2^{23}=((32)^2)^2 *2^3 mod 47 \end{eqnarray*}$ und das ist äquivalent zu

$\begin{eqnarray*} 2^{23}=2^{23} mod 47 \end{eqnarray*}$ $\begin{eqnarray*} 0=47y \end{eqnarray*}$ gilt fuer alle y aber richtig weiter hilfts noch net, weil ich will ja eigentlich

$\begin{eqnarray*} 2^{23}=1 mod 47 \end{eqnarray*}$ haben

mehr weiss ich momentan noch net...
aber schon mal danke

edit:falsches forum ...wollte Sonstiges Hochschule LOL Hammer

19.11.2006, 22:05

Auf diesen Beitrag antworten »

1) ist Ok, 2) auch. aber eigentlich erübrigt sich ja 2), wenn man zuerst 3) löst - dann hat man ja so ein Beispiel auch!

Und bei 3) musst du doch nur durchhalten in der Berechnung!

19.11.2006, 22:20

piloan

Auf diesen Beitrag antworten »

momentan echt ka warum er das so ausgeklammert hat... unglücklich

19.11.2006, 22:25

Auf diesen Beitrag antworten »

Musst dich ja nicht drum kümmern. Rechne doch $\begin{eqnarray*} 2^{23} \mod 47 \end{eqnarray*}$ einfach so aus, wie es dir am besten liegt.

19.11.2006, 23:05

piloan

Auf diesen Beitrag antworten »

ja ...ich liebe kongruenzen....nun hab ich keine variabel drin ....siehe letztes mal ...und nu weiss ich acuh nicht was ich machen soll

20.11.2006, 00:55

Auf diesen Beitrag antworten »

Verstehe ich dich richtig? Also, übertragen auf reelle Zahlen bedeutet deine Aussage:

"Ich kann zwar Gleichungen wie 5x-7=38 auflösen, aber ich beherrsche nicht das Einmaleins wie 3*7."

Genau das hast du gerade gesagt, nur eben in Bezug auf Modulrechnung. Du sollst doch nur die Restklasse modulo 47 rauskriegen,
in der $\begin{eqnarray*} 2^{23} \end{eqnarray*}$ liegt, und das geht auf vielerlei Arten, z.B.

$\begin{eqnarray*} 2^1 \equiv 2\mod 47 \end{eqnarray*}$
...
$\begin{eqnarray*} 2^5 \equiv 32\mod 47 \end{eqnarray*}$
$\begin{eqnarray*} 2^6 \equiv 64\equiv 17\mod 47 \end{eqnarray*}$
$\begin{eqnarray*} 2^7 \equiv 2\cdot 17 = 34\mod 47 \end{eqnarray*}$
$\begin{eqnarray*} 2^8 \equiv 2\cdot 34 = 68\equiv 21\mod 47 \end{eqnarray*}$

usw.

Oder unter Ausnutzung der Potenzgesetze eben kürzer:

$\begin{eqnarray*} 2^{23} &=& 2^{5\cdot 4+3} = (2^5)^4\cdot 2^3 = (32^2)^2\cdot 8\equiv ((-15)^2)^2\cdot 8\\ &=& 225^2\cdot 8\equiv (-10)^2\cdot 8 \equiv 6\cdot 8\equiv 1\mod 47 \end{eqnarray*}$

Sag bloß, sowas hast du nie gemacht - dafür aber vorher Kongruenzgleichungen??? Man sollte doch erstmal laufen lernen, bevor man aufs Rad steigt! unglücklich

P.S.: Ich würde es eher so machen

$\begin{eqnarray*} 2^{23} \equiv 49^{23} = 7^{46} \equiv 1\mod 47 \end{eqnarray*}$

direkt nach dem kleinen Fermat - aber muss ja nicht sein, es geht auch konventionell wie oben. Augenzwinkern

20.11.2006, 01:00

Mathespezialschüler

Auf diesen Beitrag antworten »

Verschoben

20.11.2006, 08:47

piloan

Auf diesen Beitrag antworten »

hmhm ....da hab ich mir wohl zu viel bei gedacht ....dachte das waer alles komplizierter Augenzwinkern

falls noch einer was mit dem hinweis fuer aufg 2 anfangen kann dann bin ich dankbar...denn ich denke es reicht nicht zu sagen
ich hab mit dem taschenrechner rausbekommen,dass fuer p=11 ich einen teiler gefunden habe und damit gibt es ein p usw ...das gibt bestimmt böse

20.11.2006, 09:21

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
denn ich denke es reicht nicht zu sagen ich hab mit dem taschenrechner rausbekommen,dass fuer p=11 ich einen teiler gefunden habe und damit gibt es ein p usw

Wieso nicht? $\begin{eqnarray*} 2^{11}-1=23\cdot 89 \end{eqnarray*}$ ist aussagekräftig genug...

20.11.2006, 09:32

piloan

Auf diesen Beitrag antworten »

20.11.2006, 09:47

Auf diesen Beitrag antworten »

Wenn du willst, kannst du auch (ähnlich wie oben bei mod 47)

$\begin{eqnarray*} 2^{11} \equiv 25^{11} = 5^{22} \equiv 1\mod 23 \end{eqnarray*}$

gemäß kleinem Fermat rechnen, aber aussagekräftiger als die Produktdarstellung ist das auch nicht. Augenzwinkern

20.11.2006, 18:49

piloan

Auf diesen Beitrag antworten »

hi hab noch ein problem bei einem beweis...
soll zeigen, dass man die Fermat Zahlen rekursiv darstellen kann...

quasi ist $\begin{eqnarray*} F_0 *F_1*...F_n=F_{n+1}-2 \end{eqnarray*}$ wobei $\begin{eqnarray*} F_n=2^{2^n}+1 \end{eqnarray*}$

habs mal fuer bestimmte zahlen nachgerechnet und passt ja...

hatte gedacht mit Induktion ...IA nachrechnen,dann direkt den Schritt

$\begin{eqnarray*} F_0 *F_1*...F_{n+1}=F_0 *F_1*...*F_n*F_{n+1}=((F_{n+1}-2)*F_{n+1}=(F_{n+1})^2-2F_{n+1} \end{eqnarray*}$

$\begin{eqnarray*} (2^{2^{n+1}}+1)^2-2*(2^{2^{n+1}}+1)=2^{2^{n+2}}+2*2^{2^{n+1}}+1-(2*2^{2^{n+1}}+2)=2^{2^{n+2}}+1-2=F_{n+2}-2 \end{eqnarray*}$

wollte mal anfragen ob du damit einverstanden bist Augenzwinkern

gruß

20.11.2006, 19:16

Auf diesen Beitrag antworten »

Ab und zu hab ich mal nichts zu meckern. Freude

Selten, aber es kommt vor. Augenzwinkern

20.11.2006, 20:52

piloan

Auf diesen Beitrag antworten »

und nu noch so ne tolle kongruenz.

berechne $\begin{eqnarray*} 2^{32} mod 641 \end{eqnarray*}$ hinweis: $\begin{eqnarray*} 5*2^7 \equiv -1 \end{eqnarray*}$ und $\begin{eqnarray*} 5^4\equiv -2^4 mod 641 \end{eqnarray*}$

schließe daraus das F_5 keine Primzahl ist....

habe versucht 2^32 umzuformen und bin noch nicht weiter gekommen

20.11.2006, 20:57

Auf diesen Beitrag antworten »

Ganz offenbar ist das Ziel der Geschichte

$\begin{eqnarray*} 2^{32} \equiv -1 \mod 641 \end{eqnarray*}$

Musst mal schauen, wie du da die Hinweise geschickt einsetzen kannst.

20.11.2006, 22:32

piloan

Auf diesen Beitrag antworten »

irgendwie verrenne ich mich nur Hammer

20.11.2006, 22:51

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 2^{32} = 2^4\cdot 2^{28} \equiv -5^4\cdot 2^{28} = -(5\cdot 2^7)^4\equiv -(-1)^4 = -1 \mod 641 \end{eqnarray*}$

20.11.2006, 23:07

piloan

Auf diesen Beitrag antworten »

danke schoen Wink

....irgendwie hab ich nach -5^4*2^28 nix mehr hinbekommen

21.11.2006, 15:08

piloan

Auf diesen Beitrag antworten »

habe noch ein problem in Zahlentheorie...
ich soll Identitäten beweisen ...

$\begin{eqnarray*} \prod_{d|n}~d=\sqrt{n^{d(n)}} \end{eqnarray*}$ wobei d die Teileranzahlfunktion ist.

Braeuchte mal einen Tipp ,da ich nicht weiter komme....
hatte irgendwie gedacht so anzufangen aber sehe hier kein weiterkommen (koennte es abschaetzen was aber nix bringt verwirrt

)

$\begin{eqnarray*} 1*d_1*d_2*....n <n^n=\sqrt{n^{2n}} \end{eqnarray*}$

gruß

21.11.2006, 15:23

Auf diesen Beitrag antworten »

Abschätzen bringt nix, du musst hier genau rechnen. Also ausgehend von der Primfaktorzerlegung

$\begin{eqnarray*} n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_r^{e_r} \end{eqnarray*}$

genau überlegen, wie oft der Primfaktor $\begin{eqnarray*} p_k \end{eqnarray*}$ im Produkt $\begin{eqnarray*} \prod\limits_{d | n} d \end{eqnarray*}$ auftaucht. Für festes $\begin{eqnarray*} k \end{eqnarray*}$ kann man jeden Teiler $\begin{eqnarray*} d \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ zerlegen in

$\begin{eqnarray*} d = p_k^{a_k}\cdot d' \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq a_k\leq e_k \end{eqnarray*}$ sowie $\begin{eqnarray*} d' | n' \end{eqnarray*}$ mit $\begin{eqnarray*} n':=\frac{n}{p_k^{e_k}} \end{eqnarray*}$ .

Jetzt betrachten wir alle Teiler $\begin{eqnarray*} d \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ , dann durchlaufen $\begin{eqnarray*} d' \end{eqnarray*}$ alle Teiler von $\begin{eqnarray*} n' \end{eqnarray*}$ , und $\begin{eqnarray*} a_k \end{eqnarray*}$ alle Werte $\begin{eqnarray*} 0,1,\ldots,e_k \end{eqnarray*}$ und zwar unabhängig voneinander. Die Teiler von $\begin{eqnarray*} n' \end{eqnarray*}$ enthalten den Primfaktor $\begin{eqnarray*} p_k \end{eqnarray*}$ gemäß Konstruktion nicht - dafür aber $\begin{eqnarray*} p_k^{a_k} \end{eqnarray*}$ , letzterer genau $\begin{eqnarray*} a_k \end{eqnarray*}$ -mal. Also gilt:

$\begin{eqnarray*} p_k \end{eqnarray*}$ ist in $\begin{eqnarray*} \prod\limits_{d | n} d \end{eqnarray*}$ genau mit dem Exponent

$\begin{eqnarray*} \sum\limits_{d'|n'} \sum\limits_{a_k=0}^{e_k} a_k = \frac{e_k(e_k+1)}{2}\cdot d(n') \stackrel{!}{=} \frac{e_k}{2}\cdot d(n) \end{eqnarray*}$

enthalten... Der Rest sollte klar sein.

21.11.2006, 19:35

piloan

Auf diesen Beitrag antworten »

verstehe ich momentan ueberhaupt nicht ...
du zerlegst eine zahl n in primfaktoren und dann soll man schauen wie oft jede Primzahl in dem Produkt vorkommt...
angenommen n=12 dann zerlege ich das in $\begin{eqnarray*} n=2^2*3 \end{eqnarray*}$ die Primzahl p=2 taucht im Produkt der Teiler jedoch 6 mal auf denn
$\begin{eqnarray*} 1*2*3*4*6*12=1*2^6*3^3 \end{eqnarray*}$ nun zerlege ich diesen teiler aber welchen teiler nehm ich nu ....ich habe ja die Teiler im Produkt wieder in Primfaktoren zerlegt .....steig ich irgendwie nicht hinter Hammer

21.11.2006, 19:38

Auf diesen Beitrag antworten »

Inwiefern ist das ein Widerspruch zu meinem Beitrag?

$\begin{eqnarray*} n=12 \end{eqnarray*}$ ist $\begin{eqnarray*} p_1=2,e_1=2,p_2=3,e_2=1 \end{eqnarray*}$

Für $\begin{eqnarray*} k=1 \end{eqnarray*}$ ergibt sich

$\begin{eqnarray*} \frac{e_1}{2}\cdot d(n) = \frac{2}{2}\cdot d(12) = d(12) = 6 \end{eqnarray*}$ ,

alles Ok.

23.11.2006, 11:42

Auf diesen Beitrag antworten »

Irgendwie bist du noch in Schockstarre, oder? Ich weiß leider nicht, wie man es anders beweisen kann. Aber ich kann versuchen, es nochmal von vorn anders aufzuschreiben, wenn auch umständlicher:

Ausgehend von der Primfaktorzerlegung

$\begin{eqnarray*} n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_r^{e_r} \end{eqnarray*}$

überlegt man sich, wie oft jeder der Primfaktoren $\begin{eqnarray*} p_k \end{eqnarray*}$ im Produkt $\begin{eqnarray*} \prod\limits_{d | n} d \end{eqnarray*}$ auftaucht. Jeden Teiler $\begin{eqnarray*} d \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ besitzt die Struktur

$\begin{eqnarray*} d = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_r^{a_r} \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq a_j\leq e_j \end{eqnarray*}$ für $\begin{eqnarray*} j=1,\ldots,r \end{eqnarray*}$ ,

das sind insgesamt $\begin{eqnarray*} (e_1+1)\cdot (e_2+1)\cdot \ldots \cdot (e_r+1)=d(n) \end{eqnarray*}$ Teiler. Dann gilt nach Potenzgesetzen

$\begin{eqnarray*} \prod\limits_{d | n} ~ d &=& \prod\limits_{a_1=0}^{e_1} \prod\limits_{a_2=0}^{e_2} \ldots \prod\limits_{a_r=0}^{e_r} \left( p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_r^{a_r} \right)\\ &=& p_1^{\sum\limits_{a_1=0}^{e_1} \sum\limits_{a_2=0}^{e_2} \ldots \sum\limits_{a_r=0}^{e_r} a_1} \cdot p_2^{\sum\limits_{a_1=0}^{e_1} \sum\limits_{a_2=0}^{e_2} \ldots \sum\limits_{a_r=0}^{e_r} a_2} \cdot \ldots \cdot p_r^{\sum\limits_{a_1=0}^{e_1} \sum\limits_{a_2=0}^{e_2} \ldots \sum\limits_{a_r=0}^{e_r} a_r} = \prod\limits_{k=1}^r p_k^{\sum\limits_{a_1=0}^{e_1} \sum\limits_{a_2=0}^{e_2} \ldots \sum\limits_{a_r=0}^{e_r} a_k} \qquad (*) \end{eqnarray*}$

Grauenhaft, nicht wahr? Genau das wollte ich oben vermeiden... Ziel ist jetzt, diese Exponenten

$\begin{eqnarray*} E_k := \sum\limits_{a_1=0}^{e_1} \sum\limits_{a_2=0}^{e_2} \ldots \sum\limits_{a_r=0}^{e_r} a_k \end{eqnarray*}$

zu vereinfachen. Bzgl. der Summation über $\begin{eqnarray*} a_j \end{eqnarray*}$ mit $\begin{eqnarray*} j\neq k \end{eqnarray*}$ ist der Summand $\begin{eqnarray*} a_k \end{eqnarray*}$ konstant, man muss also nur mit der Anzahl der Indizes $\begin{eqnarray*} a_j=0,1,\ldots,e_j \end{eqnarray*}$ multiplizieren - das sind genau $\begin{eqnarray*} (e_j+1) \end{eqnarray*}$ . Es folgt

$\begin{eqnarray*} E_k = \left( \prod\limits_{\substack{j=1\\ j\neq k}}^r (e_j+1) \right) \cdot \sum\limits_{a_k=0}^{e_k} a_k \end{eqnarray*}$

Tja, und die letzte Summe? $\begin{eqnarray*} \sum\limits_{i=1}^n i = \frac{n(n+1)}{2} \end{eqnarray*}$ musst du doch kennen! Also diese dann angewandt ergibt sich

$\begin{eqnarray*} E_k = \left( \prod\limits_{\substack{j=1\\ j\neq k}}^r (e_j+1) \right) \cdot \frac{e_k(e_k+1)}{2} = \left( \prod\limits_{j=1}^r (e_j+1) \right) \cdot \frac{e_k}{2} = d(n) \cdot \frac{e_k}{2} \end{eqnarray*}$

Puuuh, jetzt alles wieder in (*) eingesetzt erhält man gemäß Potenzgesetz $\begin{eqnarray*} a^{bc} = (a^b)^c \end{eqnarray*}$ :

$\begin{eqnarray*} \prod\limits_{d | n} ~ d = \prod\limits_{k=1}^r p_k^{d(n) \frac{e_k}{2}} = \left[ \prod\limits_{k=1}^r p_k^{e_k} \right]^{\frac{d(n)}{2}} = n^{\frac{d(n)}{2}} \end{eqnarray*}$

Neue Frage »

Antworten »

Mersenne Zahlen & andere zahlentheoretische Fragen

Verwandte Themen