kgV einer Menge und Anteil

01.03.2023, 13:56

Malcang

kgV einer Menge und Anteil

Hallo zusammen,

kein Tag ohne Thread Augenzwinkern

Der Titel ist möglicherweise nicht passend gewählt, gerne mich darauf hinweisen.

Situation:
Algorithmus A liefert Lösung $\begin{eqnarray*} p \end{eqnarray*}$ für ein Element $\begin{eqnarray*} k \end{eqnarray*}$ und damit auch gleichzeitig für $\begin{eqnarray*} k\pmod{ord_p(2)} \end{eqnarray*}$ .
Jetzt möchte ich gerne die Genauigkeit bestimmen. Dazu habe ich erstmal das kgV von mehreren Elementen definiert:
[attach]56884[/attach]
Mich stören hier die Auslassungspunkte, aber ich komme auch nicht auf eine schönere Definition. Gibt es knackiges, induktives?

Meine eigentliche Frage ist aber eine andere.
Sagen wir, der Algortihmus hat mir nach zweimaligem Durchlauf die Elemente 5 und 7 gegeben.
Angenommen, damit kann ich die Restklassen $\begin{eqnarray*} k\pmod{35}\in\{1,2,3,7,8,9\} \end{eqnarray*}$ lösen (völlig fiktiv).
Dann lösen diese beiden Elemente ja nun $\begin{eqnarray*} \frac{6}{35} \end{eqnarray*}$ aller Fälle. Dazu habe ich den Begriff der Genauigkeit definiert:
[attach]56885[/attach]

Nun wollte ich noch zeigen, dass dieser wohldefiniert ist und zwischen 0 und 1 liegt.
[attach]56884[/attach]

Jetzt fehlt mir allerdings noch der $\begin{eqnarray*} \leq 1 \end{eqnarray*}$ Fall.
Mein Ansatz war anzunehmen, dass es $\begin{eqnarray*} >1 \end{eqnarray*}$ ist. Dann wäre die Anzahl der $\begin{eqnarray*} k\pmod{V(D_h)} \end{eqnarray*}$ größer als das kgV.

Jetzt wollte ich gerne argumentieren, dass ja dann das größte Element größer als das kgV ist, was zum Widerspruch führt.
Aber das darf ich doch in Restklassen nicht machen verwirrt

Edit: Ich dachte auch schon, statt $\begin{eqnarray*} k\pmod{V(D_h)} \end{eqnarray*}$ könnte ich ja auch $\begin{eqnarray*} 0\leq k \leq 34 \end{eqnarray*}$ betrachten. Ich fürchtete halt dass mir da dann der Zusammenhang zum kgV fehlt.

01.03.2023, 16:54

IfindU

Auf diesen Beitrag antworten »

RE: kgV einer Menge und Anteil
Wenn du es unbedingt mit Formeln machen willst, ist es etwas nervig. Aktuell ist $\begin{eqnarray*} V \end{eqnarray*}$ nicht wohldefiniert: Sei $\begin{eqnarray*} N = \{ 1,2\} \end{eqnarray*}$ und $\begin{eqnarray*} N_1 = N_2 = 2 \in N \end{eqnarray*}$ ist offenbar richtig. Dann wäre $\begin{eqnarray*} V(N) = 2 \end{eqnarray*}$ . Du hast nie gesagt, dass die $\begin{eqnarray*} N_i \end{eqnarray*}$ verschieden sind oder zusammen $\begin{eqnarray*} N \end{eqnarray*}$ aufstellen. Du könntest sowas schreiben wie:
Sei $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ , $\begin{eqnarray*} (N_i)_{i=1}^n \subset \mathbb N \end{eqnarray*}$ . Definiere $\begin{eqnarray*} V(N) \end{eqnarray*}$ als das kleinste gemeinsame Vielfache der $\begin{eqnarray*} (N_i) \end{eqnarray*}$ , d.h. $\begin{eqnarray*} V(N) = \min_{v \in \mathbb N} \{ N_i \text{ teilt } v \text{ für alle } i \} \end{eqnarray*}$ .

Zum anderen: Die Menge im Zähler enthält ja nur Restklassen zu $\begin{eqnarray*} V(\mathcal D_h) \end{eqnarray*}$ und es gibt nur $\begin{eqnarray*} V(\mathcal D_h) \end{eqnarray*}$ Restklassen.

D.h. $\begin{eqnarray*} \{ k \mod V(\mathcal D_h) | \text{ irgendeine Einschränkung} \} \subset \{ k \mod V(\mathcal D_h) \} \end{eqnarray*}$ und damit $\begin{eqnarray*} \left | \{ k \mod V(\mathcal D_h) | \text{ irgendeine Einschränkung} \} \right| \leq \left|\{ k \mod V(\mathcal D_h) \}\right| = V(\mathcal D_h) \end{eqnarray*}$

01.03.2023, 17:06

HAL 9000

Auf diesen Beitrag antworten »

Ich finde die Kennzeichnung der Mengenelemente $\begin{eqnarray*} k\pmod{V\left(\mathfrak{D}_h\right)} \end{eqnarray*}$ in dieser $\begin{eqnarray*} \mathcal{G} \end{eqnarray*}$ -Definition problematisch. Warum schreibst du nicht einfach

$\begin{eqnarray*} \mathcal{G}\left(\mathfrak{D}_h\right) = \frac{\left|\left\{ k\in \left\{0,1,\ldots,V\left(\mathfrak{D}_h\right)-1\right\}\Bigm| \exists p\in\mathfrak{D}_h:~\left(\frac{h\cdot 2^k+1}{p}\right) \neq 1\right\}\right|}{V\left(\mathfrak{D}_h\right)} \end{eqnarray*}$ ,

oder meinst du das in dem Sinne, dass Jacobi-Symbol $\begin{eqnarray*} \left(\frac{h\cdot 2^s +1}{p}\right)\neq 1 \end{eqnarray*}$ für ALLE $\begin{eqnarray*} s\equiv k\bmod V\left(\mathfrak{D}_h\right) \end{eqnarray*}$ gelten muss??? Ich finde das verwirrend.

01.03.2023, 17:20

Malcang

Auf diesen Beitrag antworten »

Hallo ihr zwei,

danke für eure Hilfe! Jetzt bin ich gerade unterwegs, den Rest des schönen Wetters noch ohne Mathematik genießen Augenzwinkern

Ich werde mich aber auf jeden Fall dazu wieder äußern.
Danke und schönen Resttag smile

02.03.2023, 11:28

Malcang

Auf diesen Beitrag antworten »

Guten Morgen zusammen,

wenn ein Element $\begin{eqnarray*} p\in\mathfrak{D}_h \end{eqnarray*}$ eine Lösung ist für einen Exponenten $\begin{eqnarray*} k \end{eqnarray*}$ dann für alle $\begin{eqnarray*} k\pmod ord_p(2) \end{eqnarray*}$ . Deshalb dachte ich es sinnvoll, mich direkt auf die ohnehin nur möglichen Restklassen zu beschränken.

Zitat:

Original von HAL 9000
Ich finde die Kennzeichnung der Mengenelemente $\begin{eqnarray*} k\pmod{V\left(\mathfrak{D}_h\right)} \end{eqnarray*}$ in dieser $\begin{eqnarray*} \mathcal{G} \end{eqnarray*}$ -Definition problematisch. Warum schreibst du nicht einfach

$\begin{eqnarray*} \mathcal{G}\left(\mathfrak{D}_h\right) = \frac{\left|\left\{ k\in \left\{0,1,\ldots,V\left(\mathfrak{D}_h\right)-1\right\}\Bigm| \exists p\in\mathfrak{D}_h:~\left(\frac{h\cdot 2^k+1}{p}\right) \neq 1\right\}\right|}{V\left(\mathfrak{D}_h\right)} \end{eqnarray*}$ ,

Ich wollte es umgehen, diese Menge in der auch noch ein Jacobisymbol vorkomt, zusätzlich auf einen Bruch zu schreiben. Das sah mir sonst so überlagert aus. Außerdem möchte ich die Menge $\begin{eqnarray*} \operatorname{M} \end{eqnarray*}$ auich im Beweis nochmal einzeln verwenden.

Zitat:

Original von HAL 9000
oder meinst du das in dem Sinne, dass Jacobi-Symbol $\begin{eqnarray*} \left(\frac{h\cdot 2^s +1}{p}\right)\neq 1 \end{eqnarray*}$ für ALLE $\begin{eqnarray*} s\equiv k\bmod V\left(\mathfrak{D}_h\right) \end{eqnarray*}$ gelten muss???

Genau. Denn ich gehe ich davon aus, dass in $\begin{eqnarray*} \mathfrak{D}_h \end{eqnarray*}$ bereits ein $\begin{eqnarray*} p \end{eqnarray*}$ existiert, dass Lösung für $\begin{eqnarray*} k \end{eqnarray*}$ ist.
Oder habe ich deine Frage falsch verstanden? verwirrt

02.03.2023, 11:30

Malcang

Auf diesen Beitrag antworten »

RE: kgV einer Menge und Anteil

Zitat:

Original von IfindU
Wenn du es unbedingt mit Formeln machen willst, ist es etwas nervig. Aktuell ist $\begin{eqnarray*} V \end{eqnarray*}$ nicht wohldefiniert: Sei $\begin{eqnarray*} N = \{ 1,2\} \end{eqnarray*}$ und $\begin{eqnarray*} N_1 = N_2 = 2 \in N \end{eqnarray*}$ ist offenbar richtig. Dann wäre $\begin{eqnarray*} V(N) = 2 \end{eqnarray*}$ . Du hast nie gesagt, dass die $\begin{eqnarray*} N_i \end{eqnarray*}$ verschieden sind oder zusammen $\begin{eqnarray*} N \end{eqnarray*}$ aufstellen. Du könntest sowas schreiben wie:
Sei $\begin{eqnarray*} n\geq 1 \end{eqnarray*}$ , $\begin{eqnarray*} (N_i)_{i=1}^n \subset \mathbb N \end{eqnarray*}$ . Definiere $\begin{eqnarray*} V(N) \end{eqnarray*}$ als das kleinste gemeinsame Vielfache der $\begin{eqnarray*} (N_i) \end{eqnarray*}$ , d.h. $\begin{eqnarray*} V(N) = \min_{v \in \mathbb N} \{ N_i \text{ teilt } v \text{ für alle } i \} \end{eqnarray*}$ .

Ich habe es mal so probiert:
[attach]56888[/attach]
Die natürlichen Zahlen sind bei mir ohne Null.

Ist dieser Version ok? Ich versuche immer möglichst auf Indizes zu verzichten (wo es geht, natürlich).

Zitat:

Original von IfindU
Zum anderen: Die Menge im Zähler enthält ja nur Restklassen zu $\begin{eqnarray*} V(\mathcal D_h) \end{eqnarray*}$ und es gibt nur $\begin{eqnarray*} V(\mathcal D_h) \end{eqnarray*}$ Restklassen.

D.h. $\begin{eqnarray*} \{ k \mod V(\mathcal D_h) | \text{ irgendeine Einschränkung} \} \subset \{ k \mod V(\mathcal D_h) \} \end{eqnarray*}$ und damit $\begin{eqnarray*} \left | \{ k \mod V(\mathcal D_h) | \text{ irgendeine Einschränkung} \} \right| \leq \left|\{ k \mod V(\mathcal D_h) \}\right| = V(\mathcal D_h) \end{eqnarray*}$

Dem kann ich folgen. Das schreibe ich gleich nochmal in Ruhe auf.

Edit: Sorry für den Doppelpost. Ich wollte diese Antwort eigentlich an den anderen Beitrag anhängen.

02.03.2023, 12:41

IfindU

Auf diesen Beitrag antworten »

Zum kgV: Fordere am besten, dass $\begin{eqnarray*} N \end{eqnarray*}$ nicht-leer ist. Sonst ist das Minimum nicht wohldefiniert. Es würde sich auch anbieten einfach $\begin{eqnarray*} kgV(N) \end{eqnarray*}$ zu definieren, statt extra neuen Buchstaben einzuführen, es sei denn du hast einen Grund. Letztes: Schreib lieber $\begin{eqnarray*} \min \{ k \in \mathbb N : \forall n \in N: n |k \} \end{eqnarray*}$ , ansonsten benutzt du den Strich $\begin{eqnarray*} | \end{eqnarray*}$ einmal, um die Grundmenge und die Einchränkung zu trennen, und nachher als Teilbarkeitssymbol. Deswegen hatte ichs ausgeschrieben.

Edt: Das sieht auch doof aus wegen dem anderen Doppelpunkt geschockt

02.03.2023, 13:07

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang

Zitat:

Genau.

Wenn das so ist, dann habe ich das ganze Konstrukt $\begin{eqnarray*} \left(\frac{h\cdot 2^{k\bmod V\left(\mathfrak{D}_h\right)}+1}{p}\right)\neq 1 \end{eqnarray*}$ nicht verstanden. Könntest du bitte nochmal GENAU erklären was es bedeutet, keine Zahl sondern eine Restklasse im Exponenten zu haben?

02.03.2023, 13:29

Malcang

Auf diesen Beitrag antworten »

@IfindU: Danke sehr für all diese Anmerkungen. Das N nichtleer ist werde ich noch fordern, danke für den Hinweis.

Zitat:

Original von IfindU
Edt: Das sieht auch doof aus wegen dem anderen Doppelpunkt geschockt

Wie man's macht, macht man's verkehrt Big Laugh

@HAL 9000:
Ich feile gerade an einer ausführlichen Formulierung, die ich dann gerne hier bereitstellen würde.

02.03.2023, 13:52

Malcang

Auf diesen Beitrag antworten »

Also, es geht nach wie vor um die Proth-Zahlen und das Jacobisymbol. Ich hole hier mal weit aus, auch wenn du, HAL, und sicherlich einige anderen das schon mehrfach in meinen anderen Threads gelesen haben Big Laugh

Es hilft mir aber auch, das nochmal zu ordnen.

Sei $\begin{eqnarray*} h \in \mathbb N \end{eqnarray*}$ ungerade. Für die Proth-Zahl $\begin{eqnarray*} h\cdot 2^k + 1 \end{eqnarray*}$ mit $\begin{eqnarray*} h<2^k \end{eqnarray*}$ gibt es dann diesen Primzahltest:
[attach]56889[/attach]

Schlussendlich geht es also darum, ein $\begin{eqnarray*} D \end{eqnarray*}$ zu finden, sodass das Jacobisymbol ungleich 1 ist.
Dieses $\begin{eqnarray*} D \end{eqnarray*}$ habe ich bisher immer $\begin{eqnarray*} p \end{eqnarray*}$ genannt, da es genügt, bei Primzahlen zu schauen.
Die Frage ist nun, ob eine endliche Menge $\begin{eqnarray*} \mathfrak{D}_h \end{eqnarray*}$ existiert, sodass
$\begin{eqnarray*} \forall k\exists p\in\mathcal{D}_h : \left(\frac{p}{h\cdot 2^k+1}\right) \neq 1 \end{eqnarray*}$ .

Nun konnte ich zeigen, dass ich das Jacobisymbol rumdrehen kann. Weiterhin darf ich dann reduzieren und erhalte
$\begin{eqnarray*} \left(\frac{p}{h\cdot 2^k+1}\right) = \left(\frac{h\cdot 2^k+1}{p}\right) =\left(\frac{h\cdot 2^k+1\pmod p}{p}\right) \end{eqnarray*}$ .

Nun ist $\begin{eqnarray*} h\cdot 2^k+1\equiv (h \mod p) \cdot 2^{k\mod ord_p(2)}+1\pmod p \end{eqnarray*}$ .

Jetzt geht es eigentlich erst los.
Sagen wir, ich finde ein $\begin{eqnarray*} p_1 \end{eqnarray*}$ , dass den Exponenten $\begin{eqnarray*} k=1 \end{eqnarray*}$ löst und ein $\begin{eqnarray*} p_2 \end{eqnarray*}$ , das den Exponenten $\begin{eqnarray*} k = 2 \end{eqnarray*}$ löst.
Sei nun $\begin{eqnarray*} ord_{p_1}(2) = 2 \end{eqnarray*}$ und $\begin{eqnarray*} ord_{p_3}(2)=3. \end{eqnarray*}$ .
Dann habe ich also Lösungen für alle $\begin{eqnarray*} k\equiv 1\pmod 2 \end{eqnarray*}$ und $\begin{eqnarray*} k\equiv 2 \pmod 3 \end{eqnarray*}$ .
Was mir also noch fehlt sind diejenigen $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} k\equiv 0 \pmod 6 \end{eqnarray*}$ oder $\begin{eqnarray*} k\equiv 4 \pmod 6 \end{eqnarray*}$ . Das war der Grund für diesen Thread
Nun sollte in dem Beispiel zu diesem Zeitpunkt $\begin{eqnarray*} \operatorname{M}(\mathfrak{D}_h) = \{1,2,3,5\} \end{eqnarray*}$ sein, denn für diese Exponenten (modulo 6) existiert ein entsprechendes $\begin{eqnarray*} p \end{eqnarray*}$ .
Mit der Genauigkeit wollte ich dann ausdrücken, dass $\begin{eqnarray*} \frac{4}{6} \end{eqnarray*}$ aller Fälle mit der Menge $\begin{eqnarray*} \mathfrak{D}_h = \{p_1, p_2\} \end{eqnarray*}$ gelöst werden können.

Das ist der Hintergrund dieses Threads hier. Ich habe unten einmal skizziert, was ich damit bezwecke.
Ich bedanke mich an dieser Stelle schonmal für's Lesen smile

---------------------
Der Hintergrund ist der, dass ich im weiteren Verlauf zeigen möchte, dass man für jedes $\begin{eqnarray*} \epsilon>0 \end{eqnarray*}$ eine Menge $\begin{eqnarray*} \mathfrak{D}_h \end{eqnarray*}$ findet, mit der man mindestens $\begin{eqnarray*} (1-\epsilon) \% \end{eqnarray*}$ aller Fälle lösen kann.
Der Gedanke ist (ich erkläre das mal mit dem Beispiel), dass ich ja nun einfach ein $\begin{eqnarray*} p_4 \end{eqnarray*}$ für den Exponenten $\begin{eqnarray*} k = 4 \end{eqnarray*}$ finden muss. Dann bestimme ich dessen Ordnung. Wenn sich das kgV nicht ändert, beträgt die Genaugighkeit der neuen Menge $\begin{eqnarray*} \mathfrak{D}_h = \{p_1, p_2, p_4\} \end{eqnarray*}$ ja mindestens $\begin{eqnarray*} \frac{5}{6}. \end{eqnarray*}$ Vielleicht sogar $\begin{eqnarray*} 1 \end{eqnarray*}$ , falls der übrige Exponent $\begin{eqnarray*} 0 \end{eqnarray*}$ auch abgedeckt wird.
Sollte sich das kgV ändern, dann wird die Genauigkeit trotzdem steigen, aber eben weniger. Denn dann bilde ich das neue kgV, streiche die Restklassen wie im Modul 6 (das sind dann immernoch $\begin{eqnarray*} \frac{2}{3} \end{eqnarray*}$ der Fälle und zusätzlich dann die Restklassen, die durch $\begin{eqnarray*} p_4 \end{eqnarray*}$ gelöst werden.

03.03.2023, 08:58

HAL 9000

Auf diesen Beitrag antworten »

tl;dr

Ich wollte eigentlich nur wissen, ob der Jacobisymbol-Wert $\begin{eqnarray*} \left( \frac{h\cdot 2^k+1}{p} \right) \end{eqnarray*}$ für $\begin{eqnarray*} k \end{eqnarray*}$ aus derselben Restklasse $\begin{eqnarray*} \bmod V\left(\mathfrak{D}_h\right) \end{eqnarray*}$ immer derselbe ist, ohne deine ganzen Überlegungen nachvollziehen zu müssen. Das scheinst du ja soweit bestätigt zu haben, wenn ich richtig quergelesen habe.

Und erst jetzt begreife ich, dass du im Exponenten das $\begin{eqnarray*} k\bmod V\left(\mathfrak{D}_h\right) \end{eqnarray*}$ nicht als Restklasse meinst, sondern als die zweistellige Operation "Rest bei der Division". Das ist vor allem deshalb verwirrend, weil du vorn noch mit $\begin{eqnarray*} k\pmod{V\left(\mathfrak{D}_h\right)} \end{eqnarray*}$ ebenfalls mit "mod" operiert hast, diesmal wohl aber als Restklassenkennzeichnung. verwirrt

Wenn das der Fall ist, dann halte ich nach wie vor diese Definition von $\begin{eqnarray*} \mathcal{G}\left(\mathfrak{D}_h\right) \end{eqnarray*}$ für deutlich klarer und erfüllt denselben Zweck: Denn egal, ob man die Menge der Restklassen mit dieser Eigenschaft, oder die Menge passender Repräsentanten daraus betrachtet, am Ende werden sie ja nur gezählt, und das kommt in beiden Fällen aufs selbe raus.

03.03.2023, 11:01

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
@IfindU: Danke sehr für all diese Anmerkungen. Das N nichtleer ist werde ich noch fordern, danke für den Hinweis.

Kannst du auch lassen. Weiß nicht, warum ich dachte das sei nicht wohldefiniert. Tatsächlich ist $\begin{eqnarray*} V(\{\}) = \min \mathbb N = 1 \end{eqnarray*}$ .

03.03.2023, 15:10

Malcang

Auf diesen Beitrag antworten »

Hallo zusammen,

@HAL 9000:
Ok, danke sehr. Ich werde dann auch die Definition übernehmen wie von dir vorgeschlagen. Dann muss ich davor eben nochmal deutlich machen, dass eine Lösung für ein $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} 0\leq k\leq V(\mathfrak{D}-1) \end{eqnarray*}$ auch ei.ne Lösung ist für $\begin{eqnarray*} k + V(\mathfrak{D}) \end{eqnarray*}$ .
Mir war/ist wichtig, dass ich die Mächtigkeit dieser Menge angeben kann und sie nicht $\begin{eqnarray*} \infty \end{eqnarray*}$ wird.

@IfindU: Diesen Hinweis werde ich so mit aufnehmen, als Sonderfall. Danke sehr!

Neue Frage »

Antworten »

kgV einer Menge und Anteil

Verwandte Themen