Kleinste Zahl, die ein Produkt nicht teilt

05.01.2010, 16:24

Manus

Kleinste Zahl, die ein Produkt nicht teilt

Nabend miteinander,

ich halte am Freitag zusammen mit einem Kommilitonen einen Proseminar-Vortrag über den AKS-Primzahltest. Leider ist mir in einem meiner Beweise eine Lücke aufgefallen, die ich nur zu gerne schließen würde.

Wir betrachten im Verlauf des Beweises die kleiste Zahl $\begin{eqnarray*} r \end{eqnarray*}$ , die das folgende Produkt NICHT teilt:

$\begin{eqnarray*} n^{\lfloor ld(B) \rfloor} \cdot \prod_{i=1}^{\lfloor ld^2(n) \rfloor}(n^i-1) \end{eqnarray*}$

Dabei ist ld der Logarithmus zur Basis 2 und $\begin{eqnarray*} B=\left\lceil ld^5(n) \right\rceil \end{eqnarray*}$

Dabei ist $\begin{eqnarray*} 3<n \in \mathbb{N} \end{eqnarray*}$ .

Was ich nun nur zu gerne zeigen würde ist, dass gilt:

$\begin{eqnarray*} ggT(n,r)=1 \end{eqnarray*}$

Leider komme ich da nicht voran.

Folgende Grundüberlegungen habe ich angestellt:

1. $\begin{eqnarray*} ggT(n,n^i-1)=1 \forall i \in \mathbb{N} \end{eqnarray*}$ das heißt der erste Faktor und das Produkt über die $\begin{eqnarray*} n^i-1 \end{eqnarray*}$ sind teilerfremd.

2. Es würde genügen zu zeigen, dass $\begin{eqnarray*} \frac{r}{ggT(r,n} \end{eqnarray*}$ das Produkt ebenfalls nicht teilt. (Dann folgt ja bereits aus der Minimalität von r die Behauptung)

3. Um 2. zu zeigen würde es bereits genügen zu zeigen, dass r nicht nur aus Primfaktoren besteht, die bereits in n enthalten sind. Denn wenn es Primfaktoren gibt, die in r auftauchen in n aber nicht, dann können wir r durch den ggT teilen und erhalten wieder eine Zahl, die $\begin{eqnarray*} n^{\lfloor ld(B) \rfloor} \end{eqnarray*}$ nicht teilt. Außerdem teilt diese Zahl auch das hintere Produkt nicht, da durch das dividieren durch den ggT(n,r) die Teilbarkeit für das hintere Produkt überhaupt nicht beeinflusst wird.
Somit teilt r auch das Produkt der beiden nicht.

(Bei 3. bin ich mir bezüglich des Arguments nicht ganz sicher, da ich glaube, dass das nur geht wenn $\begin{eqnarray*} r<n^{\lfloor ld(B) \rfloor} \end{eqnarray*}$ und $\begin{eqnarray*} r<\prod_{i=1}^{\lfloor ld^2(n) \rfloor}(n^i-1) \end{eqnarray*}$ , was ich aber so ohne weiteres nicht annehmen darf)

Leider scheitere ich jetzt aber immer daran, das eine oder andere zu zeigen. Vielleicht hat ja hier jemand eine Idee zu dem Thema.

05.01.2010, 16:39

Auf diesen Beitrag antworten »

Zitat:

Original von Manus
Wir betrachten im Verlauf des Beweises die kleiste Zahl $\begin{eqnarray*} r \end{eqnarray*}$ , die das folgende Produkt NICHT teilt:

Zuallererst würde ich mal festhalten, dass dann $\begin{eqnarray*} r \end{eqnarray*}$ eine Primzahlpotenz sein muss. Ob das beim Beweis nützt, vermag ich noch nicht zu sagen.

05.01.2010, 17:00

Manus

Auf diesen Beitrag antworten »

Das hilft mir zumindest in einer Richtung bedeutend weiter. Was ich nämlich vergessen habe zu erwähnen (weil ich es in diesem Zusammenhang noch nicht betrachtet hatte) ist, dass n keine echte Primzahlpotenz ist (kann also Primzahl sein, nicht aber Potenz mit einem Exponenten größer 1).

Das hieße ja, dass zu zeigen bleibt, wenn $\begin{eqnarray*} r=p^c \end{eqnarray*}$ für eine Primzahl p, dann gilt: $\begin{eqnarray*} p \nmid n \end{eqnarray*}$

EDIT:

So, ich habe endlich eine Möglichkeit gefunden, die etwas anders ansetzt.

Ich kann r abschätzen und zeigen, dass gilt: $\begin{eqnarray*} r<B \end{eqnarray*}$ . Damit gilt auch, dass r kleiner ist als die beiden Faktoren im Produkt. Und außerdem, dass auch schon r kleiner ist, als jede Primzahlpotenz, die in der Primfaktorzerlegung von $\begin{eqnarray*} n^{\lfloor ld(B) \rfloor} \end{eqnarray*}$ vorkommt. Mal angenommen, in der Primfaktorzerlegung von r kämen nur Primzahlen vor, die auch bei n vorkommen, dann wäre bereits $\begin{eqnarray*} n^{\lfloor ld(B) \rfloor} \end{eqnarray*}$ durch r teilbar. Da dass nicht der Fall ist, wissen wir auch, dass $\begin{eqnarray*} \frac{r}{ggT(r,n)} \end{eqnarray*}$ das Produkt nicht teilt.

Die Teilbarkeit für den hinteren Teil wird durch die Division nicht beeinflusst (da dieser teilerfremd zu n ist) und der vordere Teil ist nachwievor nicht dadurch dividierbar, da noch Primfaktoren vorkommen, die in n nicht enthalten sind.

Da $\begin{eqnarray*} \frac{r}{ggT(r,n)} \end{eqnarray*}$ kleiner ist als beide Teile und diese teilerfremd sind, wird also auch das Produkt nicht geteilt.

Und daraus folgt dann mit der Minimalität von r, dass ggT(r,n)=1.

05.01.2010, 18:46

Reksilat

Auf diesen Beitrag antworten »

Zitat:

Mal angenommen, in der Primfaktorzerlegung von r kämen nur Primzahlen vor, die auch bei n vorkommen...

Ist $\begin{eqnarray*} r=s\cdot t \end{eqnarray*}$ , mit $\begin{eqnarray*} {\rm ggt}(s,t)=1 \end{eqnarray*}$ und $\begin{eqnarray*} r\not|M \end{eqnarray*}$ , so gilt $\begin{eqnarray*} s\not|M \end{eqnarray*}$ oder $\begin{eqnarray*} t\not|M \end{eqnarray*}$ .
Per Minimalität ist $\begin{eqnarray*} r \end{eqnarray*}$ also eine Primzahlpotenz.

Habe Arthurs Bemerkung mal kurz ausformuliert, da ich dem Rest Deiner Argumentation nicht so ganz zu folgen vermag.
Das Problem ist doch hier einzig, dass $\begin{eqnarray*} r=p^m \end{eqnarray*}$ ist, $\begin{eqnarray*} p \end{eqnarray*}$ Primzahl und der $\begin{eqnarray*} p \end{eqnarray*}$ -Anteil von $\begin{eqnarray*} n^{\lfloor ld(B) \rfloor} \end{eqnarray*}$ ist geringer als $\begin{eqnarray*} p^m \end{eqnarray*}$ . Und das schließt Du durch Deine obige Abschätzung aus.
verwirrt

Gruß,
Reksilat.

05.01.2010, 19:49

Manus

Auf diesen Beitrag antworten »

Zitat:

Original von Reksilat

Zitat:

Mal angenommen, in der Primfaktorzerlegung von r kämen nur Primzahlen vor, die auch bei n vorkommen...

Gruß,
Reksilat.

Natürlich.

Ich wollte bloß zeigen, dass man den Beweis auch führen kann, wenn man nicht weiß, dass r eine Primzahlpotenz ist (was natürlich der Fall ist)

Wo in meiner Argumentation ist denn ein Haken?

Neue Frage »

Antworten »

Kleinste Zahl, die ein Produkt nicht teilt

Verwandte Themen