Ungleichung mit Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:46 Mo 07.01.2013 | | Autor: | wauwau |
| Aufgabe | Sei $a [mm] \in \IN$, $p_1,p_2,...p_n, [/mm] n [mm] \ge [/mm] 2$ paarweise verschiedene Primzahlen
Zeige, wenn [mm] $3^a-2 [/mm] = [mm] p_1p_2...p_n$
[/mm]
dann gilt [mm] $(p_1-1)(p_2-1)..(p_n-1) [/mm] > [mm] 2.3^{a-1}$ [/mm] |
Hab das mal mit Pari/gp getestet und das stimmt. die linke Seite ist bei weitem größer als die Rechte!
Aber wie man so was zeigen soll, weiß ich nicht.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:40 Fr 11.01.2013 | | Autor: | felixf |
Moin!
> Sei [mm]a \in \IN[/mm], [mm]p_1,p_2,...p_n, n \ge 2[/mm] Primzahlen
Sollen die Primzahlen paarweise verschieden sein, oder muessen sie das nicht sein?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Mo 14.01.2013 | | Autor: | wauwau |
die [mm] $p_i$ [/mm] sollen paarweise verschieden sein.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:09 Fr 11.01.2013 | | Autor: | leduart |
Hallo
[mm] 3^3-2=5*5
[/mm]
[mm] 4*4<2*3^2
[/mm]
entgegen der Beh.
Kannst du praezisieren?
Gruss leduart
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:14 Sa 12.01.2013 | | Autor: | felixf |
Moin leduart!
> [mm]3^3-2=5*5[/mm]
> [mm]4*4<2*3^2[/mm]
Ich habe die Ungleichung so interpretiert, dass auf der rechten Seite der Dezimalbruch 2.3 hoch $a - 1$ genommen wird. Da [mm] $(2.3)^2 [/mm] = 5.29$ ist, gilt $4 [mm] \cdot [/mm] 4 > 5.29$.
Also neben der Frage, ob die Primzahlen mehrmals vorkommen duerfen (was bei dir der Fall ist) haben wir auch noch die Frage an wauwau, ob [mm] $(2.3)^{a-1}$ [/mm] oder $2 [mm] \cdot 3^{a-1}$ [/mm] gemeint ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:22 Mo 14.01.2013 | | Autor: | wauwau |
Paarweise verschiedene Primzahlen und rechte Seite der Ungleichung [mm] $2.(3^{a-1})$
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:51 Mo 14.01.2013 | | Autor: | leduart |
hallo
was bedeutet der Punkt hinter 2, falls er mal bedeutet, warum dannder Punkt?
Gruss leduart
|
|
|
| |
|
Meinst du $2 + [mm] \frac{3^{a-1}}{10}$?
[/mm]
Denn sonst wäre doch $ [mm] 2.(3^{a-1}) \leq [/mm] 3$ und die Aussage damit recht witzlos.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:59 Mo 14.01.2013 | | Autor: | felixf |
Moin!
> Sei [mm]a \in \IN[/mm], [mm]p_1,p_2,...p_n, n \ge 2[/mm] paarweise
> verschiedene Primzahlen
>
> Zeige, wenn [mm]3^a-2 = p_1p_2...p_n[/mm]
> dann gilt
> [mm](p_1-1)(p_2-1)..(p_n-1) > 2.3^{a-1}[/mm]
Ich nehme mal an, mit dem Dezimalpunkt soll eine Multiplikation gemeint sein.
Ich vermute, diese Aussage stimmt nicht. Beweisen kann ich das nicht, aber ich moechte beschreiben, wie man ein Gegenbeispiel konstruieren kann (mit genuegend viel Rechenpower und Langeweile - was allerdings nicht sehr praktikabel sein wird in unseren Lebzeiten).
Damit $p$ ein Primteiler von [mm] $3^a [/mm] - 2$ ist, muss $2 + [mm] p\IZ$ [/mm] in der von $3 + [mm] p\IZ$ [/mm] erzeugten Untergruppe von [mm] $(\IZ/p\IZ)^\ast$ [/mm] liegen. Falls dies so ist, sei [mm] $dlog_p(3, [/mm] 2)$ die kleinste Potenz von 3 modulo $p$, die 2 ergibt, und sei [mm] $ord_p(3)$ [/mm] die multiplikative Ordnung von 3 modulo $p$. Nach Lagrange ist [mm] $ord_p(3)$ [/mm] ein Teiler von $p - 1$.
Wenn [mm] $dlog_p(3, [/mm] 2)$ existiert, dann muss fuer ein solches $a$ gelten $a [mm] \equiv dlog_p(3, [/mm] 2) [mm] \pmod{ord_p(3)}$.
[/mm]
Finde jetzt genuegend viele Primzahlen [mm] $p_1, \dots, p_k$, [/mm] die folgendes erfuellen:
(a) [mm] $dlog_{p_i}(3, [/mm] 2)$ existiert;
(b) die Bedingungen $a [mm] \equiv dlog_p(3, [/mm] 2) [mm] \pmod{ord_p(3)}$ [/mm] sind kompatibel zueinander, d.h. fuer alle $i, j$ gilt [mm] $dlog_{p_i}(3, [/mm] 2) [mm] \equiv dlog_{p_j}(3, [/mm] 2) [mm] \pmod{ggT(ord_{p_i}(3), ord_{p_j}(3))}$;
[/mm]
(c) das Produkt [mm] $\prod_{i=1}^k [/mm] (1 - [mm] 1/p_i)$ [/mm] ist $< 2/3$.
Da das Produkt ueber $1 - 1/p$ ueber alle Primzahlen gegen 0 divergiert (da $0 = [mm] \zeta(1)^{-1}$; [/mm] vergl. die Eulerproduktdarstellung der Zetafunktion) sollte dies moeglich sein.
Durch Probieren habe ich ein paar solche Primzahlen mit (a) und (b) gefunden, (c) ist jedoch noch nicht erfuellt und ich habe gerade keine Lust von Hand weiterzuprobieren. Bisher habe ich:
[mm] $p_1 [/mm] = 5 [mm] \Rightarrow [/mm] dlog = 3$
[mm] $p_2 [/mm] = 19 [mm] \Rightarrow [/mm] dlog = 7$
[mm] $p_3 [/mm] = 23 [mm] \Rightarrow [/mm] dlog = 7$
[mm] $p_4 [/mm] = 47 [mm] \Rightarrow [/mm] dlog = 17$
[mm] $p_5 [/mm] = 71 [mm] \Rightarrow [/mm] dlog = 11$
[mm] $p_6 [/mm] = 97 [mm] \Rightarrow [/mm] dlog = 43$
[mm] $p_7 [/mm] = 149 [mm] \Rightarrow [/mm] dlog = 131$
Ich bin optimistisch, dass man genuegend viele [mm] $p_i$ [/mm] finden kann. Wenn man diese hat, so hat man:
* es gibt unendlich viele $a [mm] \in \IN$ [/mm] mit [mm] $\prod_{i=1}^k p_i \mid (3^a [/mm] - 2)$; sei $a$ ein solches;
* [mm] $\prod_{i=1}^k p_i$ [/mm] teilet [mm] $3^a [/mm] - 2$, womit es ein [mm] $N_a \in \IN$ [/mm] gibt mit [mm] $N_a \prod_{i=1}^k p_i [/mm] + 2 = [mm] 3^a$;
[/mm]
* die Bedingung [mm] $(p_1-1)(p_2-1)..(p_n-1) [/mm] > 2 [mm] \cdot 3^{a-1}$ [/mm] ist aequivalent zu [mm] $\prod_{i=1}^n [/mm] (1 - [mm] 1/p_i) [/mm] > [mm] \frac{2}{3} [/mm] - [mm] \frac{4}{3 \cdot \prod_{i=1}^n p_i}$.
[/mm]
Die linke Seite von [mm] $\prod_{i=1}^n [/mm] (1 - [mm] 1/p_i) [/mm] > [mm] \frac{2}{3} [/mm] - [mm] \frac{4}{3 \cdot \prod_{i=1}^n p_i}$ [/mm] ist wegen [mm] $\prod_{i=1}^k [/mm] (1 - [mm] 1/p_i) [/mm] < 2/3$ kleiner als $2/3$, und da [mm] $\prod_{i=1}^n p_i$ [/mm] riesig ist und somit $3/(3 [mm] \cdot \prod_{i=1}^n p_i)$ [/mm] winzig, ist die Ungleichung vermutlich nicht erfuellt.
Wenn nun $N$ quadratfrei ist und nicht durch eins der [mm] $p_1, \dots, p_k$ [/mm] geteilt wird, hat man also ein Gegenbeispiel.
Wie schon gesagt, ob es wirklich existiert und ob man wenn man genuegend [mm] $p_k$ [/mm] hat dies ueberhaupt verizifieren kann -- da [mm] $3^a [/mm] - 2$ dann riesig sein wird, selbst fuer die kleinste Loesung fuer $a$, und somit nicht faktorisierbar auf moderner Hardware -- kann ich nicht sagen, ich vermute eher nicht.
Und selbst wenn das nicht funktioniert: der obige Wert erlaubt schnell, viele Primzahlen als Teiler von [mm] $3^a [/mm] - 2$ auszuschliessen, etwa 2, 3, 11, 13, 37, 41, 59, 61, 67, 73, 83, 103, 107, 109, 131, 151, 157, 179, 181, 193. An Primteiler [mm] $\le [/mm] 200$ von [mm] $3^a [/mm] - 2$ kommen somit nur 5, 7, 17, 19, 23, 29, 31, 43, 47, 53, 71, 79, 89, 97, 101, 113, 127, 137, 139, 149, 163, 167, 173, 191, 197 und 199 in Frage.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:31 Mo 14.01.2013 | | Autor: | wauwau |
> Moin!
>
> > Sei [mm]a \in \IN[/mm], [mm]p_1,p_2,...p_n, n \ge 2[/mm] paarweise
> > verschiedene Primzahlen
> >
> > Zeige, wenn [mm]3^a-2 = p_1p_2...p_n[/mm]
> > dann gilt
> > [mm](p_1-1)(p_2-1)..(p_n-1) > 2.3^{a-1}[/mm]
>
> Ich nehme mal an, mit dem Dezimalpunkt soll eine
> Multiplikation gemeint sein.
>
> Ich vermute, diese Aussage stimmt nicht. Beweisen kann ich
> das nicht, aber ich moechte beschreiben, wie man ein
> Gegenbeispiel konstruieren kann (mit genuegend viel
> Rechenpower und Langeweile - was allerdings nicht sehr
> praktikabel sein wird in unseren Lebzeiten).
>
> Damit [mm]p[/mm] ein Primteiler von [mm]3^a - 2[/mm] ist, muss [mm]2 + p\IZ[/mm] in
> der von [mm]3 + p\IZ[/mm] erzeugten Untergruppe von [mm](\IZ/p\IZ)^\ast[/mm]
> liegen. Falls dies so ist, sei [mm]dlog_p(3, 2)[/mm] die kleinste
> Potenz von 3 modulo [mm]p[/mm], die 2 ergibt, und sei [mm]ord_p(3)[/mm] die
> multiplikative Ordnung von 3 modulo [mm]p[/mm]. Nach Lagrange ist
> [mm]ord_p(3)[/mm] ein Teiler von [mm]p - 1[/mm].
>
> Wenn [mm]dlog_p(3, 2)[/mm] existiert, dann muss fuer ein solches [mm]a[/mm]
> gelten [mm]a \equiv dlog_p(3, 2) \pmod{ord_p(3)}[/mm].
>
> Finde jetzt genuegend viele Primzahlen [mm]p_1, \dots, p_k[/mm], die
> folgendes erfuellen:
> (a) [mm]dlog_{p_i}(3, 2)[/mm] existiert;
> (b) die Bedingungen [mm]a \equiv dlog_p(3, 2) \pmod{ord_p(3)}[/mm]
> sind kompatibel zueinander, d.h. fuer alle [mm]i, j[/mm] gilt
> [mm]dlog_{p_i}(3, 2) \equiv dlog_{p_j}(3, 2) \pmod{ggT(ord_{p_i}(3), ord_{p_j}(3))}[/mm];
>
> (c) das Produkt [mm]\prod_{i=1}^k (1 - 1/p_i)[/mm] ist [mm]< 2/3[/mm].
>
> Da das Produkt ueber [mm]1 - 1/p[/mm] ueber alle Primzahlen gegen 0
> divergiert (da [mm]0 = \zeta(1)^{-1}[/mm]; vergl. die
> Eulerproduktdarstellung der Zetafunktion) sollte dies
> moeglich sein.
>
> Durch Probieren habe ich ein paar solche Primzahlen mit (a)
> und (b) gefunden, (c) ist jedoch noch nicht erfuellt und
> ich habe gerade keine Lust von Hand weiterzuprobieren.
> Bisher habe ich:
> [mm]p_1 = 5 \Rightarrow dlog = 3[/mm]
> [mm]p_2 = 19 \Rightarrow dlog = 7[/mm]
>
> [mm]p_3 = 23 \Rightarrow dlog = 7[/mm]
> [mm]p_4 = 47 \Rightarrow dlog = 17[/mm]
>
> [mm]p_5 = 71 \Rightarrow dlog = 11[/mm]
> [mm]p_6 = 97 \Rightarrow dlog = 43[/mm]
>
> [mm]p_7 = 149 \Rightarrow dlog = 131[/mm]
>
> Ich bin optimistisch, dass man genuegend viele [mm]p_i[/mm] finden
> kann. Wenn man diese hat, so hat man:
>
> * es gibt unendlich viele [mm]a \in \IN[/mm] mit [mm]\prod_{i=1}^k p_i \mid (3^a - 2)[/mm];
> sei [mm]a[/mm] ein solches;
> * [mm]\prod_{i=1}^k p_i[/mm] teilet [mm]3^a - 2[/mm], womit es ein [mm]N_a \in \IN[/mm]
> gibt mit [mm]N_a \prod_{i=1}^k p_i + 2 = 3^a[/mm];
> * die Bedingung
> [mm](p_1-1)(p_2-1)..(p_n-1) > 2 \cdot 3^{a-1}[/mm] ist aequivalent
> zu [mm]\prod_{i=1}^n (1 - 1/p_i) > \frac{2}{3} - \frac{4}{3 \cdot \prod_{i=1}^n p_i}[/mm].
Das stimmt glaube ich nicht
richtig ist vielmehr
[mm]\prod_{i=1}^n (1 - 1/p_i) > \frac{2}{3} + \frac{4}{3 \cdot \prod_{i=1}^n p_i}[/mm]
oder habe ich einen Umformungsfehler.
Bis a=177 hab ich das nun rechnen lassen und die Ungleichung stimmt bis dahin....
>
> Die linke Seite von [mm]\prod_{i=1}^n (1 - 1/p_i) > \frac{2}{3} - \frac{4}{3 \cdot \prod_{i=1}^n p_i}[/mm]
> ist wegen [mm]\prod_{i=1}^k (1 - 1/p_i) < 2/3[/mm] kleiner als [mm]2/3[/mm],
> und da [mm]\prod_{i=1}^n p_i[/mm] riesig ist und somit [mm]3/(3 \cdot \prod_{i=1}^n p_i)[/mm]
> winzig, ist die Ungleichung vermutlich nicht erfuellt.
>
> Wenn nun [mm]N[/mm] quadratfrei ist und nicht durch eins der [mm]p_1, \dots, p_k[/mm]
> geteilt wird, hat man also ein Gegenbeispiel.
>
> Wie schon gesagt, ob es wirklich existiert und ob man wenn
> man genuegend [mm]p_k[/mm] hat dies ueberhaupt verizifieren kann --
> da [mm]3^a - 2[/mm] dann riesig sein wird, selbst fuer die kleinste
> Loesung fuer [mm]a[/mm], und somit nicht faktorisierbar auf moderner
> Hardware -- kann ich nicht sagen, ich vermute eher nicht.
>
> Und selbst wenn das nicht funktioniert: der obige Wert
> erlaubt schnell, viele Primzahlen als Teiler von [mm]3^a - 2[/mm]
> auszuschliessen, etwa 2, 3, 11, 13, 37, 41, 59, 61, 67, 73,
> 83, 103, 107, 109, 131, 151, 157, 179, 181, 193. An
> Primteiler [mm]\le 200[/mm] von [mm]3^a - 2[/mm] kommen somit nur 5, 7, 17,
> 19, 23, 29, 31, 43, 47, 53, 71, 79, 89, 97, 101, 113, 127,
> 137, 139, 149, 163, 167, 173, 191, 197 und 199 in Frage.
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:22 Mo 14.01.2013 | | Autor: | felixf |
Moin!
> > * die
> Bedingung
> > [mm](p_1-1)(p_2-1)..(p_n-1) > 2 \cdot 3^{a-1}[/mm] ist aequivalent
> > zu [mm]\prod_{i=1}^n (1 - 1/p_i) > \frac{2}{3} - \frac{4}{3 \cdot \prod_{i=1}^n p_i}[/mm].
>
> Das stimmt glaube ich nicht
> richtig ist vielmehr
> [mm]\prod_{i=1}^n (1 - 1/p_i) > \frac{2}{3} + \frac{4}{3 \cdot \prod_{i=1}^n p_i}[/mm]
>
> oder habe ich einen Umformungsfehler.
Nein, du hast Recht. Das war ein Uebertragungsfehler meinerseits. Auf den Summanden kommt es allerdings nicht so an, da er eh winzig klein ist im Vergleich zum Rest.
> Bis a=177 hab ich das nun rechnen lassen und die
> Ungleichung stimmt bis dahin....
Irgendwo um die 150-170 herum war ich auch (weiss grad nicht mehr genau wo ich aufgehoert hab). Ich glaube, dass sich Gegenbeispiele erst fuer viel groessere $a$ finden lassen - soweit sie denn existieren.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 07.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
