Zahlentheoretische Fragen

25.11.2006, 18:26

piloan

Auf diesen Beitrag antworten »

Zahlentheoretische Fragen

Hi ...
ich braeuchte nur mal ein Verfahren wie ich diese Aufgabe lösen kann...

Finde jeweils das kleinste $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ s.d $\begin{eqnarray*} 2^n\equiv 1 \mod 17 \end{eqnarray*}$ bzw $\begin{eqnarray*} 2^n \equiv 1 \mod 17 \end{eqnarray*}$

naja ...da steht ja quasi.. $\begin{eqnarray*} 2^n-1=17y \end{eqnarray*}$ und das links vom Gleichheitszeichen sind die Mersenne Zahlen ....und wenn 17 ein Teiler dieser Zahl sein soll dann muss $\begin{eqnarray*} 17\leq \sqrt{a} \end{eqnarray*}$ wobei a die gesuchte Zahl ist, die das mit dem kleinsten n liefert.
trotzdem weiss ich jetzt nur ab wo ich die zahl suchen kann....naemlich ab 17^2

gruß

26.11.2006, 11:30

Abakus

Auf diesen Beitrag antworten »

RE: Zahlentheoretische Fragen
Mit dem Kleinen Fermatschen Satz findest du eine Lösung. Alle kleineren Potenzen könntest du ausprobieren (es gibt eine kleinere Lösung).

Mit etwas Algebra siehst du ferner, dass es um eine multiplikative Gruppe mit 16 Elementen geht. Somit muss deine gesuchte Potenz ein Teiler von 16 sein, was die auszuprobierenden Zahlen deutlich reduziert.

Grüße Abakus smile

smile

27.11.2006, 09:17

piloan

Auf diesen Beitrag antworten »

ok ...dann kann ich also sagen
auf jeden fall finde ich eine lösung durch fermatschen satz

$\begin{eqnarray*} 2^{16}\equiv 1(mod)17 \end{eqnarray*}$ und da $\begin{eqnarray*} 2^{\frac{17-1}{2}}\equiv +1(mod)17 \end{eqnarray*}$ habe ich noch eine kleinere Zahl n gefunden ....bei $\begin{eqnarray*} 3^n \equiv 1(mod)17 \end{eqnarray*}$ geht wenn ich das analog mache nur

$\begin{eqnarray*} 3^{16}\equiv 1(mod)17 \end{eqnarray*}$ da $\begin{eqnarray*} 3^{\frac{17-1}{2}}\equiv -1(mod)17 \end{eqnarray*}$

aber das ist ja kein richtiger beweis ?1

27.11.2006, 09:22

AD

Auf diesen Beitrag antworten »

Doch, das ist Beweis genug, da 16 nur den Primteiler 2 hat. D.h., bei Basis 3 ist n=16 tatsächlich der kleinste positive Exponent mit $\begin{eqnarray*} 3^n \equiv 1\mod 17 \end{eqnarray*}$ . Siehe auch

Primitivwurzeln

27.11.2006, 16:40

piloan

Auf diesen Beitrag antworten »

hi arthur...habe es jetzt so bearbeitet...

nun habe ich die folgende aufg. ( habe sie auch schon geloest, wollte nur mal deine meinung wissen Augenzwinkern

Augenzwinkern

)

finde das kleinste $\begin{eqnarray*} m \in \mathbb N_+ \end{eqnarray*}$ sd fuer jedes
$\begin{eqnarray*} x \in \mathbb N_+ \end{eqnarray*}$ mit ggt (x,65) gilt :

$\begin{eqnarray*} x^m \equiv 1(mod)65 \end{eqnarray*}$

hatte mir gedacht nach chinesischem Restsatz muss das m auch fuer alle x
folgendes Aequivalenzensystem erfuellen

$\begin{eqnarray*} x^m \equiv 1(mod)13 \end{eqnarray*}$
$\begin{eqnarray*} x^m \equiv 1(mod)5 \end{eqnarray*}$

nun mit fermat

$\begin{eqnarray*} x^{12} \equiv 1(mod)13 \end{eqnarray*}$
$\begin{eqnarray*} x^4 \equiv 1(mod)5 \end{eqnarray*}$

es gehen nur die primitwurzeln wenn ich mich nicht verrechnet habe und dann ist die lösung m=12 wuerde ich sagen,da ich ja die schnittmenge der beiden brauche .....weiss nicht ob man das mathematisch noch korrekter hinbekommt ....wenn ja dann weis mich zurecht LOL Hammer

LOL Hammer

und nu noch folgendes:

$\begin{eqnarray*} n \in \mathbb N_+ \end{eqnarray*}$ und d|n
Zeige:

$\begin{eqnarray*} card=\{x\in R(n)| ggt(x,n)=d\}= \phi(\frac{n}{d}) \end{eqnarray*}$ und daraus folgern,dass
$\begin{eqnarray*} \sum_{d|n}~{\phi(d)}=n \end{eqnarray*}$ wobei $\begin{eqnarray*} \phi \end{eqnarray*}$ die eulersche Funktion ist......habe mir beispiele dazu gemacht und nachgerechnet.....jedoch weiss iuch noch keinen ansatz..
erstmal danke

27.11.2006, 16:52

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
$\begin{eqnarray*} x^{12} \equiv 1(mod)13 \end{eqnarray*}$
$\begin{eqnarray*} x^4 \equiv 1(mod)5 \end{eqnarray*}$

es gehen nur die primitwurzeln wenn ich mich nicht verrechnet habe und dann ist die lösung m=12 wuerde ich sagen,da ich ja die schnittmenge der beiden brauche

Etwas nebulös formuliert, aber du bist auf der richtigen Spur: Klar ist nach diesen Betrachtungen, dass für alle zu 65 teilerfremden Zahlen $\begin{eqnarray*} x \end{eqnarray*}$ die Kongruenz $\begin{eqnarray*} x^{12}\equiv 1\mod 13 \end{eqnarray*}$ gilt. Für alle diese $\begin{eqnarray*} x \end{eqnarray*}$ gilt aber auch $\begin{eqnarray*} x^{12} = (x^4)^3 \equiv 1^3=1\mod 5 \end{eqnarray*}$ und somit

$\begin{eqnarray*} x^{12} \equiv 1\mod 65 \end{eqnarray*}$

für alle teilerfremden $\begin{eqnarray*} x \end{eqnarray*}$ . Bleibt nur zu zeigen, dass es auch ein x mit $\begin{eqnarray*} x^t\not\equiv 1\mod 65 \end{eqnarray*}$ für $\begin{eqnarray*} t=1,\ldots,11 \end{eqnarray*}$ gibt, und das erfüllt jede Primitivwurzel modulo 13.

Anzeige

27.11.2006, 17:30

piloan

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Für alle diese $\begin{eqnarray*} x \end{eqnarray*}$ gilt aber auch $\begin{eqnarray*} x^{12} = (x^4)^3 \equiv 1^3=1\mod 5 \end{eqnarray*}$ und somit

$\begin{eqnarray*} x^{12} \equiv 1\mod 65 \end{eqnarray*}$
für alle teilerfremden $\begin{eqnarray*} x \end{eqnarray*}$ .

Bleibt nur zu zeigen, dass es auch ein x mit $\begin{eqnarray*} x^t\not\equiv 1\mod 65 \end{eqnarray*}$ für $\begin{eqnarray*} t=1,\ldots,11 \end{eqnarray*}$ gibt, und das erfüllt jede Primitivwurzel modulo 13.

ersten teil verstehe ich bis ...bleibt nur noch zu zeigen...
wenn ich gezeigt habe,dass fuer n=12 jedes x die gleichung erfuellt ,dann reicht das doch ... verwirrt

verwirrt

27.11.2006, 17:45

AD

Auf diesen Beitrag antworten »

Es könnte ja auch sein, dass sogar $\begin{eqnarray*} x^6\equiv 1\mod 65 \end{eqnarray*}$ für alle zu 65 teilerfremden $\begin{eqnarray*} x \end{eqnarray*}$ gilt - und dann lautet die Antwort 6 statt 12. Augenzwinkern

Augenzwinkern

Wenn du aber (aus anderen Sätzen) benutzen darfst, dass es modulo 13 primitive Wurzeln gibt, dann bist du in der Tat fertig.

27.11.2006, 18:12

piloan

Auf diesen Beitrag antworten »

dann habe ich aber etwas wohl noch nicht verstanden....
ich habe diese gleichung ja in ein äquivalenzsystem zerlegt...jetzt muessen die gefundenen loesungen doch beide gleichungen erfuellen.
so kann doch zb laut wikipedia

$\begin{eqnarray*} x^{12} \equiv 1(mod)13 \end{eqnarray*}$ nur 12 oder 6 als loesung vorkommen...da fuer x=2 und m=6 die gleichung schon nicht erfuellt ist kann sie auch fuer mod65 nicht erfuellt sein ....mit dem gleichen prinzip habe ich auch m=2 bei $\begin{eqnarray*} x^{m} \equiv 1(mod)5 \end{eqnarray*}$ ausgeschlossen ....somit kann das ganze ding doch nur m=12 als lösung besitzen, weil das auch
$\begin{eqnarray*} x^{m} \equiv 1(mod)5 \end{eqnarray*}$ erfuellt verwirrt

verwirrt

27.11.2006, 18:19

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
da fuer x=2 und m=6 die gleichung schon nicht erfuellt ist kann sie auch fuer mod65 nicht erfuellt sein

Eben deshalb, und das stand oben noch nicht da.

Ist doch ganz einfach: Wenn man nachweisen soll, dass die und die Zahl die kleinste mit einer Eigenschaft ist, muss man zwei Dinge nachweisen:

1) Dass sie diese Eigenschaft hat, und

2) Dass keine kleinere Zahl diese Eigenschaft hat.

1) hast du getan, aber 2) ist etwas kurz gekommen oben - mehr wollte ich doch nicht sagen.

27.11.2006, 18:22

piloan

Auf diesen Beitrag antworten »

ich sehs deutlich Augenzwinkern

Augenzwinkern

hat einer einen anstoss fuer die maechtigkeitsaufgabe ? smile

smile

27.11.2006, 18:40

AD

Auf diesen Beitrag antworten »

Du kannst die Menge $\begin{eqnarray*} R(n) := \{1,2,\ldots,n\} \end{eqnarray*}$ disjunkt aufteilen in Mengen

$\begin{eqnarray*} A_{n,t} := \{ x\in R(n) \bigm| \operatorname{ggT}(x,n)=t \} \end{eqnarray*}$ für Teiler $\begin{eqnarray*} t \end{eqnarray*}$ von $\begin{eqnarray*} n \end{eqnarray*}$ ,

d.h. $\begin{eqnarray*} R(n) = \bigcup\limits_{t|n} A_{n,t} \end{eqnarray*}$ . Aus der Disjunktheit folgt für die Mächtigkeit

$\begin{eqnarray*} \operatorname{card}(R(n)) = \sum\limits_{t|n} \operatorname{card}(A_{n,t}) \end{eqnarray*}$

Bleibt nachzuweisen $\begin{eqnarray*} \operatorname{card}(A_{n,t}) = \varphi\left( \frac{n}{t} \right) \end{eqnarray*}$ , und dazu schau dir doch mal die Elemente in $\begin{eqnarray*} A_{n,t} \end{eqnarray*}$ genauer an! Die haben die Struktur $\begin{eqnarray*} x=y\cdot t \end{eqnarray*}$ mit $\begin{eqnarray*} y\in R\left(\frac{n}{t}\right) \end{eqnarray*}$ ...

Zum Schluss bleibt lediglich festzustellen, dass

$\begin{eqnarray*} \sum\limits_{t|n} \varphi\left( \frac{n}{t} \right) = \sum\limits_{d|n} \varphi\left( d \right) \end{eqnarray*}$

gilt, weil links und rechts dieselben Summanden stehen, und zwar wegen der Bijektion $\begin{eqnarray*} t \leftrightarrow d:=\frac{n}{t} \end{eqnarray*}$ zwischen den Teilern $\begin{eqnarray*} d \end{eqnarray*}$ und $\begin{eqnarray*} t \end{eqnarray*}$ .

27.11.2006, 23:48

piloan

Auf diesen Beitrag antworten »

so endlich komm ich mal dazu dir zu antworten...
habe das alles noch nicht richtig verstanden...warum teilst du die menge eigentlich auf ? ist das t nicht in meinem fall mein d ?...oder hat das einen grund warum da eine neue variable auftaucht?...

und dann habe ich mir gedanken zu der struktur der elemente von $\begin{eqnarray*} A_{n,t} \end{eqnarray*}$ gemacht....habe mir das an beispielen versucht zu verdeutlichen ....eigentlich nehm ich doch $\begin{eqnarray*} x=yt \end{eqnarray*}$ und y nimmt gerade die werte ,der teilerfremden zahlen von n/t an und hat somit gleich viele elemente.....hoffe das ist verstaendlioch wie ich das meine

gruß

27.11.2006, 23:56

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
warum teilst du die menge eigentlich auf ?

Warum wohl: Wie groß ist denn $\begin{eqnarray*} \operatorname{card}(R(n)) \end{eqnarray*}$ ?

Und $\begin{eqnarray*} t \end{eqnarray*}$ oder $\begin{eqnarray*} d \end{eqnarray*}$ , das ist ja wohl egal...

28.11.2006, 00:05

piloan

Auf diesen Beitrag antworten »

hi
$\begin{eqnarray*} \operatorname{card}(R(n))=n \end{eqnarray*}$
wuerd ich mal behaupten

28.11.2006, 18:01

piloan

Auf diesen Beitrag antworten »

hi arthur ...
bin bis jetzt noch nicht recht weiter gekommen bei dem problem.

ich will
$\begin{eqnarray*} card\{x\in R(n): ggt(x,n)=d\}=\varphi({\frac{n}{d}}) \end{eqnarray*}$
bestimmen. jetzt nimmst du die vereinigung dieser mengen und betrachtest davon die Mächtigkeit.

$\begin{eqnarray*} \operatorname{card}(R(n)) = n=\sum\limits_{t|n} \operatorname{card}(A_{n,t}) \end{eqnarray*}$ aber ohne hilfe komm ich da nicht weiter..
sry

28.11.2006, 18:10

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
ich will
$\begin{eqnarray*} card\{x\in R(n): ggt(x,n)=d\}=\varphi({\frac{n}{d}}) \end{eqnarray*}$
bestimmen.

Was heißt "bestimmen"? Nachweisen sollst du das - ich dachte, das hättest du jetzt langsam? Und damit bist du doch dann fast fertig.

28.11.2006, 18:20

piloan

Auf diesen Beitrag antworten »

ne ich meinte ja auch nachweisen ...aber ich habs nicht ...weil ich es nicht 100 %ig verstanden habe ....

28.11.2006, 18:26

AD

Auf diesen Beitrag antworten »

Alle $\begin{eqnarray*} x \end{eqnarray*}$ mit $\begin{eqnarray*} \operatorname{ggT}(x,n)=d \end{eqnarray*}$ kann man zerlegen $\begin{eqnarray*} x=dy \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq y < \frac{n}{d} \end{eqnarray*}$ , also m.a.W. $\begin{eqnarray*} y\in R\left( \frac{n}{d} \right) \end{eqnarray*}$ .

Nun ist dann aber $\begin{eqnarray*} \operatorname{ggT}\left(y,\frac{n}{d}\right)=1 \end{eqnarray*}$ (Begründung?), also gilt aufgrund der Bijektion $\begin{eqnarray*} x \leftrightarrow y \end{eqnarray*}$ für die zugehörigen Mengenkardinalitäten

$\begin{eqnarray*} \operatorname{card}\left( \left\{ x\in R(n) \bigm| \operatorname{ggT}(x,n)=d \right\} \right) = \operatorname{card}\left( \left\{ y\in R\left( \frac{n}{d}\right) \bigm| \operatorname{ggT}\left(y,\frac{n}{d}\right)=1 \right\} \right) \end{eqnarray*}$ .

Und letzteres ist natürlich $\begin{eqnarray*} \varphi\left( \frac{n}{d} \right) \end{eqnarray*}$ . So schwer ist das doch nun wirklich nicht, nach all der Vorarbeit!

29.11.2006, 15:17

piloan

Auf diesen Beitrag antworten »

hab ich nun auch hinbekommen ...danke :-)

habe mir nun noch ein paar gedanken ueber die mandoltsche Fkt gemacht, die folgendermaßen definiert ist:

$\begin{eqnarray*} \Lambda(n):=\left\{\begin{array}{r@{\quad\quad}l}log(p) & n=p^k\\ 0& sonst\end{array}\right. \end{eqnarray*}$

nun soll ich dazu zeigen:

1.) $\begin{eqnarray*} \sum_{d|n}~\Lambda(d)=log(n) \end{eqnarray*}$
2.) $\begin{eqnarray*} \sum_{d|n}~\mu(d) log(\frac{n}{d})=\Lambda(n) \end{eqnarray*}$
3.) $\begin{eqnarray*} \sum_{d|n}~\mu(d) log(d)=-\Lambda(n) \end{eqnarray*}$

zu 1.)

$\begin{eqnarray*} n=p_1^{k_1}*p_2^{k_2}*...*p_n^{k_n} \end{eqnarray*}$ nur wenn die Teiler d der Form $\begin{eqnarray*} p_i^{k_i} \end{eqnarray*}$ sind, nimm die Mangoldtsche Fkt ueberhaupt einen Wert ungleich 0 an und es folgt

$\begin{eqnarray*} \sum_{d|n}~\Lambda(d)= (k_1)log(p_1)+....+(k_n)log(p_n)=log(p_1^{k_1} *....*p_n^{k_n})=log(n) \end{eqnarray*}$

hoffe das stimmt fuer die 1..bei den anderen schau ich noch

kannst ja shcon ma drueber schauen :-)
danke ersmtla

29.11.2006, 15:35

AD

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
nur wenn die Teiler d der Form $\begin{eqnarray*} p_i^{k_i} \end{eqnarray*}$ sind, nimm die Mangoldtsche Fkt ueberhaupt einen Wert ungleich 0 an

Jein: Teiler der Form $\begin{eqnarray*} p_i^j \end{eqnarray*}$ mit $\begin{eqnarray*} j=1,2,\ldots,k_i \end{eqnarray*}$ , das ist was anderes! Ich würde daher im Beweis noch ein paar Zwischenschritte aufschreiben, in etwa so:

$\begin{eqnarray*} \sum\limits_{d | n} ~ \Lambda(d) = \sum\limits_{i=1}^n ~ \sum\limits_{j=1}^{k_i} \Lambda(p_i^j) = \sum\limits_{i=1}^n ~ \sum\limits_{j=1}^{k_i} \log(p_i) = \sum\limits_{i=1}^n ~ k_i\cdot \log(p_i) = \sum\limits_{i=1}^n ~ \log(p_i^{k_i}) = \log\left( \prod\limits_{i=1}^n ~ p_i^{k_i} \right) = \log(n) \end{eqnarray*}$

2) folgt aus 1) mit etwas Grundwissen über die Dirichlet-Multiplikation von zahlentheoretischen Funktionen.

Und 3) folgt schließlich aus 2) durch simple Anwendung von Logarithmengesetzen.

29.11.2006, 18:29

piloan

Auf diesen Beitrag antworten »

So habe nun fuer 2

$\begin{eqnarray*} f(n)=\sum_{d|n}~F(\frac{n}{d})*\mu(d) \end{eqnarray*}$

so berechne ich doch durch Faltung von F mit $\begin{eqnarray*} \mu \end{eqnarray*}$ meine ursprüngliche Funktion f.
nun brauch ich doch nur von aufg 1 das einsetzen fuer f und F und bin fertig ...richtig ? smile

smile

29.11.2006, 19:04

AD

Auf diesen Beitrag antworten »

Richtig.

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »