Balkan MO: trouver tous les nombres premiers possibles $p$ et $q$ tel que $3p^{q-1}+1$ se divise $11^p+17^p$. [fermé]

Question

Trouver tous les nombres premiers possibles $p$ et $q$ tel que $3p^{q-1}+1$ se divise $11^p+17^p$.

Ce problème a été publié 2 fois dans MSE, mais n'a jamais été résolu. Est-ce que quelqu'un peut m'aider?

Je suis censé utiliser les commandes et les mods

Answer 1

Répondez avec des indices cachés. Nous supposons que$3p^{q-1} +1$ se divise $11^p+17^p$ pour certains nombres premiers $p$ et $q$.

• Si $p=2$, ce n'est pas possible. (Force brute)

Pour $p=2$ nous avons $11^2+17^2 = 410$ dont les facteurs sont $1,2,5,10,41,82,205,410$. Si$3 \times 2^{q-1}+1$ est un facteur alors ce facteur est de la forme $3k+1$ c'est-à-dire que ce facteur ne peut être $1,10,82$ ou $204$, mais dans chaque cas $k \neq 2^{q-1}$ pour $q$ premier.

• Maintenant pour $p>2$, $ 8 \nmid 11^p+17^p$.

Puisque $p$ est impair, $$11^p + 17^p \equiv 3^p+1 \equiv 3+1\equiv 4 \mod 8$$

• Laisser $r$ être un diviseur premier impair de $3p^{q-1}+1$. ensuite$r \notin \{3,11,17\}$.

Bien sûr $r \neq 3$, sinon il ne peut pas diviser un certain nombre du formulaire $3k+1$. Mais$3p^{q-1}+1$ se divise $11^p+17^p$ donc si $r$ divise le RHS alors il ne peut diviser aucun des $11^p$ ou $17^p$car il faudrait aussi diviser l'autre, mais les deux sont premiers. par conséquent$r \neq 11,17$.

• Il y a un $b$ tel que $17b \equiv 1 \mod r$, par le théorème de Bezout. Montre CA$ord_r(11b) \in \{2,2p\}$.

Si $17b \equiv 1 \mod r$ puis $b^p(11^p+17^p) \equiv (11b)^p +1\mod r$, mais $r$ se divise $11^p+17^p$ donc $(11b)^p + 1$ est un multiple de $r$, et donc $(11b)^{2p}-1$ est un multiple de $r$. Donc$ord_r(11b)$ se divise $2p$, mais n'est pas égal à $1$ évidemment.

• Laisser $ord_r(11b) = 2$. ensuite$r=7$.

Si oui alors $r$ se divise $(11b)^2-1$, mais ensuite ça divise aussi $(11b)^2 - (17b)^2$, et parce que c'est le coprime de $b$ est un diviseur de $11^2-17^2 = -168$. Puisque$r \neq 3$ nous devons avoir $r=7$.

• Si $ord_r(11b) = 2p$ puis $2p$ se divise $r-1$, par le petit théorème de Fermat. On peut donc écrire la décomposition première$$ 3p^{q-1}+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k} $$ où $p_i \neq 2,7$ sont des facteurs premiers avec $p_i \equiv 1 \mod 2p$.

• Nous avons $\beta \leq 1$, en observant que $\frac{11^p+17^p}{28}$ n'est pas un multiple de $7$. (Indice:$11+17= 28$, donc cette fraction est définitivement un nombre naturel, mais vous pouvez en dire plus) Ainsi $\beta \leq 1$.

La factorisation standard $\frac{a^p-b^p}{a-b} = \sum_{k=1}^{n-1} a^kb^{n-k}$ s'applique avec $a=11,b=-17$ et nous utilisons $11 \equiv 4$ et $17 \equiv -4$ mod $7$, cette $\frac{11^p+17^p}{28} \equiv p4^{p-1}$ mod $7$, et $p \neq 7$(Pourquoi?)

• Si $q=2$, alors le problème n'a pas de solution.

Si oui alors $3p+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k}$, mais chacun des $p_i$ Est au moins $2p+1$ qui est plus de la moitié $3p+1$. Donc non$p_i$exister. Par les limites existantes sur$\alpha,\beta$ il n'y a que les candidats $3p+1 = 2,4,14,28$, aucun de qui fonctionne.

• Si $q>2$, puis $\alpha = 2$ et $p=3$.

Si $q>2$, puis $p^{q-1} \equiv 1 \mod 4$ puisque $q-1$ est égal, d'où $3p^{q-1} +1$ est un multiple de $4$, donc $\alpha = 2$. Finalement,$2^{\alpha}7^{\beta} p_1^{\gamma_1}...p_k^{\gamma_k}$ est congru à $4$ ou $28$ modulo $p$, parce que le $p_i$ sont tous congruents à $1$ modulo $p$. Mais$3p^{q-1}+1$ est congru à $1$ modulo $p$. Comme ils sont égaux, nous obtenons que soit$1-4$ ou $1-28$ est un multiple de $p$. D'une manière ou d'une autre$p=3$.

• Regarde ça $q=3$ doit arriver si $p=3$.

Eh bien, nous avons $11^3+17^3= 6244 = 2^2 \times 7 \times 223$, donc si $3 \times 3^{q-1} +1$ est un multiple de $6244$, alors c'est la même chose que de dire $3^q+1$ est un multiple de $6244$, et donc $q=3$ est la seule option depuis $q=1,2,4,...,7$ ne fonctionne pas et $q=8$ est trop grand.

• Donc $p=q=3$ est la seule solution.

Answer 2

Une autre approche:

En raison du critère d'Euler:

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

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

Ces deux relations donnent $p=q=3$

Dans ce cas $A=28$.

Nous vérifions cela avec RHS, c'est à dire $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$ et $3^q$ sont bizarres donc $7b$ est donc pair:

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

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

$11^p+17^q$ et $4^p+3^q$ sont bizarres donc $7a+7b$ doit être pair; $7b=14b_1$ est égal, donc $7a$ doit aussi être égal, laissez $7a=14a_1$, nous avons donc:

$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$

Nous avons besoin $11^p+11^q\equiv (4^p+3^q)\equiv 0 \ mod (7)$

Ceci n'est possible que si $p=q$ tel que:

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

Maintenant si $p=q=3$ puis $14a_1+14b_1=28 k$, car:

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

Par conséquent $A=28\big|B$

C'est $p=q=3$ peut être une solution.