Balkan MO: Finde alle möglichen Primzahlen $p$ und $q$ so dass $3p^{q-1}+1$ teilt $11^p+17^p$. [geschlossen]

Question

Finde alle möglichen Primzahlen $p$ und $q$ so dass $3p^{q-1}+1$ teilt $11^p+17^p$.

Dieses Problem wurde zweimal in MSE gepostet, aber nie gelöst. Kann mir jemand helfen?

Ich soll Befehle und Mods verwenden

Answer 1

Antworte mit versteckten Hinweisen. Wir nehmen an, dass$3p^{q-1} +1$ teilt $11^p+17^p$ für einige Primzahlen $p$ und $q$.

• Wenn $p=2$, es ist nicht möglich. (Rohe Gewalt)

Zum $p=2$ wir haben $11^2+17^2 = 410$ deren Faktoren sind $1,2,5,10,41,82,205,410$. Wenn$3 \times 2^{q-1}+1$ ist ein Faktor, dann ist dieser Faktor von der Form $3k+1$ dh dieser Faktor kann nur sein $1,10,82$ oder $204$, aber in jedem Fall $k \neq 2^{q-1}$ zum $q$ Prime.

• Jetzt für $p>2$, $ 8 \nmid 11^p+17^p$.

Schon seit $p$ ist ungerade, $$11^p + 17^p \equiv 3^p+1 \equiv 3+1\equiv 4 \mod 8$$

• Lassen $r$ sei ein seltsamer Hauptteiler von $3p^{q-1}+1$. Dann$r \notin \{3,11,17\}$.

Natürlich $r \neq 3$Andernfalls kann eine Anzahl der Formulare nicht geteilt werden $3k+1$. Aber$3p^{q-1}+1$ teilt $11^p+17^p$ also wenn $r$ teilt die RHS, dann kann sie keine von beiden teilen $11^p$ oder $17^p$wie es auch den anderen teilen müsste, aber beide sind Koprime. Folglich$r \neq 11,17$.

• Da ist ein $b$ so dass $17b \equiv 1 \mod r$nach dem Satz von Bezout. Zeige, dass$ord_r(11b) \in \{2,2p\}$.

Wenn $17b \equiv 1 \mod r$ dann $b^p(11^p+17^p) \equiv (11b)^p +1\mod r$, aber $r$ teilt $11^p+17^p$ so $(11b)^p + 1$ ist ein Vielfaches von $r$, und deshalb $(11b)^{2p}-1$ ist ein Vielfaches von $r$. Deshalb$ord_r(11b)$ teilt $2p$, ist aber nicht gleich $1$ offensichtlich.

• Lassen $ord_r(11b) = 2$. Dann$r=7$.

Wenn ja, dann $r$ teilt $(11b)^2-1$, aber dann teilt es sich auch $(11b)^2 - (17b)^2$und weil es Koprime ist $b$ ist ein Teiler von $11^2-17^2 = -168$. Schon seit$r \neq 3$ Wir müssen haben $r=7$.

• Wenn $ord_r(11b) = 2p$ dann $2p$ teilt $r-1$nach Fermats kleinem Satz. Daher können wir die Hauptzerlegung schreiben$$ 3p^{q-1}+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k} $$ wo $p_i \neq 2,7$ sind Hauptfaktoren mit $p_i \equiv 1 \mod 2p$.

• Wir haben $\beta \leq 1$, indem man das beobachtet $\frac{11^p+17^p}{28}$ ist kein Vielfaches von $7$. (Hinweis :$11+17= 28$, so dass dieser Bruch definitiv eine natürliche Zahl ist, aber man kann mehr sagen) Also $\beta \leq 1$.

Die Standardfaktorisierung $\frac{a^p-b^p}{a-b} = \sum_{k=1}^{n-1} a^kb^{n-k}$ gilt mit $a=11,b=-17$ und wir bekommen mit $11 \equiv 4$ und $17 \equiv -4$ mod $7$, Das $\frac{11^p+17^p}{28} \equiv p4^{p-1}$ mod $7$, und $p \neq 7$(Warum?)

• Wenn $q=2$, dann hat das Problem keine Lösungen.

Wenn ja, dann $3p+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k}$, aber jeder der $p_i$ ist mindestens $2p+1$ Das ist mehr als die Hälfte $3p+1$. Deshalb nein$p_i$existieren. Durch die bestehenden Grenzen weiter$\alpha,\beta$ Es gibt nur die Kandidaten $3p+1 = 2,4,14,28$, keine davon funktioniert.

• Wenn $q>2$, dann $\alpha = 2$ und $p=3$.

Wenn $q>2$, dann $p^{q-1} \equiv 1 \mod 4$ schon seit $q-1$ ist gerade, daher $3p^{q-1} +1$ ist ein Vielfaches von $4$, so $\alpha = 2$. Schließlich,$2^{\alpha}7^{\beta} p_1^{\gamma_1}...p_k^{\gamma_k}$ ist kongruent zu $4$ oder $28$ Modulo $p$, weil der $p_i$ sind alle kongruent zu $1$ Modulo $p$. Aber$3p^{q-1}+1$ ist kongruent zu $1$ Modulo $p$. Da diese gleich sind, bekommen wir das auch$1-4$ oder $1-28$ ist ein Vielfaches von $p$. So oder so$p=3$.

• Siehst du das $q=3$ muss passieren wenn $p=3$.

Nun, wir haben $11^3+17^3= 6244 = 2^2 \times 7 \times 223$, also wenn $3 \times 3^{q-1} +1$ ist ein Vielfaches von $6244$, dann ist das das gleiche wie zu sagen $3^q+1$ ist ein Vielfaches von $6244$, und deshalb $q=3$ ist die einzige Option seitdem $q=1,2,4,...,7$ nicht arbeiten und $q=8$ es ist zu groß.

• So $p=q=3$ ist die einzige Lösung.

Answer 2

Ein anderer Ansatz:

Aufgrund des Euler-Kriteriums:

$A=3^{\frac{7-1}2=3}+1 \equiv 0 \ mod (7)$

$3\times 3^{q-1}+1\equiv 0 \ mod (7)$

Diese beiden Beziehungen geben $p=q=3$

In diesem Fall $A=28$.

Wir überprüfen dies mit RHS, dh $B=11^p+17^q$::

$11\equiv 4 \mod (7)$ , $\rightarrow 11^p \equiv 4^p \mod (7)=7a+4^p$

$17 \equiv 3 \ mod (7)$, $\rightarrow 17^q\equiv 3^q \ mod (7)=7b+3^q$

$17^q$ und $3^q$ sind so seltsam $7b$ ist gerade deshalb:

$17^q=14 b_1+3^q$

⇒ $11^p+13^q=7a+7b+4^p+3^q$

$11^p+17^q$ und $4^p+3^q$ sind so seltsam $7a+7b$ muss gerade sein; $7b=14b_1$ ist gerade so $7a$ muss auch gerade sein, lass $7a=14a_1$, also haben wir:

$11^p+17^q=14(a_1+b_1)+4^p+3^q$

$4^p+3^q=(7-3)^p+3^q= 7t -3^p+3^q$

Wir brauchen $11^p+11^q\equiv (4^p+3^q)\equiv 0 \ mod (7)$

Dies ist nur möglich, wenn $p=q$ so dass:

$4^p+3^q=(7-3)^p+3^q= 7t +(-3^p+3^q=0)=7t$

Nun wenn $p=q=3$ dann $14a_1+14b_1=28 k$, weil:

$11^3+17^3=223\times 28$

Daher $A=28\big|B$

Das ist $p=q=3$ kann eine Lösung sein.