Modularen Ausdruck vereinfachen

09.02.2023, 10:44

Malcang

Modularen Ausdruck vereinfachen

Hallo zusammen,

ich habe etwas herausgefunden und wollte wissen, ob ich das nun noch weiter vereinfachen kann.
Ich habe eine natürliche Zahl $\begin{eqnarray*} k \end{eqnarray*}$ und eine natürliche Zahl $\begin{eqnarray*} h \end{eqnarray*}$ mit $\begin{eqnarray*} h\equiv 3\pmod 6. \end{eqnarray*}$
Nun betrachte ich die Zahl $\begin{eqnarray*} n = h\cdot 2^k+1 \end{eqnarray*}$ und möchte wissen, ob sie durch eine ungerade Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ teilbar ist. Dabei ist mir folgendes aufgefallen:
$\begin{eqnarray*} h\cdot 2^{k}+1\equiv 0 \pmod p \Leftrightarrow h\cdot 2^{k}+2\equiv 1 \pmod p \Leftrightarrow h\cdot 2^{k-1}+1\equiv (2^{-1})\pmod p. \end{eqnarray*}$
Das konnte ich induktiv fortführen und erhalte
$\begin{eqnarray*} h\cdot2^k+1\equiv 0\pmod p \Leftrightarrow 2^{-k} + 2^{-k+1}+\dots 2^{-1} \pmod p \end{eqnarray*}$ und mit der geometrischen Summenformel erhalte ich
$\begin{eqnarray*} h\cdot 2^k + 1\equiv 0 \pmod p \Leftrightarrow h+1\equiv 1 -(2^{-1})^k \pmod p \Leftrightarrow h\equiv -(2^{-1})^k\pmod p \end{eqnarray*}$ .
Nun kann ich das Inverse der $\begin{eqnarray*} 2 \end{eqnarray*}$ ganz einfach angeben mit $\begin{eqnarray*} 2^{-1}\equiv \frac{p+1}{2}\pmod p \end{eqnarray*}$ .

Nun frage ich mich, wo ich stehe. Der Ausdruck
$\begin{eqnarray*} h\cdot 2^k+1\equiv \pmod p \Leftrightarrow h\equiv -(2^{-1})^k\pmod p \end{eqnarray*}$
sieht ja irgendwie verlockend aus. Aber ich denke (fürchte), ob ich nun die linke Seite reduziere mod p oder die rechte macht keinen großen Unterschied. Wobei man halt noch den Satz von Euler auf den Exponenten anwenden könnte, auch das auf beiden Seiten.

Und kann ich irgendwie noch die Voraussetzung $\begin{eqnarray*} h\equiv 3\pmod 6 \end{eqnarray*}$ einbringen?
Danke smile

09.02.2023, 10:53

HAL 9000

Auf diesen Beitrag antworten »

Mal eine ganz bescheidene Frage: Warum veranstaltest du den Zirkus mit der geometrischen Summenformel, wenn du doch auch einfach so äquivalent umformen kannst

$\begin{eqnarray*} h\cdot 2^k+1\equiv 0\bmod p\qquad\Bigm|~-1 \end{eqnarray*}$

$\begin{eqnarray*} h\cdot 2^k\equiv -1\bmod p\qquad\Bigm|~\cdot 2^{-k} \end{eqnarray*}$

$\begin{eqnarray*} h\equiv -2^{-k}\equiv -\left(2^{-1}\right)^k\bmod p \end{eqnarray*}$ Augenzwinkern

09.02.2023, 10:56

Malcang

Auf diesen Beitrag antworten »

Edit (mY+): Unnötiger Vollquote wurde entfernt

Guter Punkt, HAL Big Laugh

Danke dafür.
Ich kam auf diese Umformung weil ich mich gefragt habe ob ich über $\begin{eqnarray*} h\cdot 2^{k}+1 \end{eqnarray*}$ etwas aussagen kann, wenn ich schon was über $\begin{eqnarray*} h\cdot 2^{k-1}+1 \end{eqnarray*}$ sagen kann.

09.02.2023, 13:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Und kann ich irgendwie noch die Voraussetzung $\begin{eqnarray*} h\equiv 3\pmod 6 \end{eqnarray*}$ einbringen?

Du hast ja nun $\begin{eqnarray*} h\equiv -\left(\frac{p+1}{2}\right)^k\bmod p \end{eqnarray*}$ rausbekommen. Im Fall $\begin{eqnarray*} p\geq 5 \end{eqnarray*}$ ist dann das System beider Kongruenzen gemäß Chinesischem Restsatz eindeutig lösbar modulo $\begin{eqnarray*} 6p \end{eqnarray*}$ .

Noch konkreter heißt das, genau einer der 6 Werte $\begin{eqnarray*} h_r\equiv rp-\left(\frac{p+1}{2}\right)^k\bmod (6p) \end{eqnarray*}$ mit $\begin{eqnarray*} r=0,1,2,3,4,5 \end{eqnarray*}$ erfüllt die Eigenschaft $\begin{eqnarray*} h_r\equiv 3\bmod 6 \end{eqnarray*}$ .

09.02.2023, 13:42

Malcang

Auf diesen Beitrag antworten »

Sehr interessant, HAL!
Ich werde mir in Ruhe anschauen, wie ich das weiter nutzen kann!

Ich danke dir vielmals! Freude

Neue Frage »

Antworten »

Modularen Ausdruck vereinfachen

Verwandte Themen