Balkan MO : 가능한 모든 소수 찾기 $p$ 과 $q$ 그런 $3p^{q-1}+1$ 분할 $11^p+17^p$. [닫은]

Nov 23 2020

가능한 모든 소수 찾기 $p$ 과 $q$ 그런 $3p^{q-1}+1$ 분할 $11^p+17^p$.

이 문제는 MSE에 2 번 게시되었지만 해결되지 않았습니다. 누군가 나를 도울 수 있습니까?

나는 주문과 모드를 사용해야한다

답변

3 TeresaLisbon Nov 23 2020 at 13:39

숨겨진 힌트로 대답하십시오. 우리는$3p^{q-1} +1$ 분할 $11^p+17^p$ 일부 소수 $p$ 과 $q$.

만약 $p=2$, 불가능합니다. (브 루트 포스)

에 대한 $p=2$ 우리는 $11^2+17^2 = 410$ 누구의 요인은 $1,2,5,10,41,82,205,410$. 만약$3 \times 2^{q-1}+1$ 그 요인은 다음과 같은 형태입니다. $3k+1$ 즉 그 요인은 $1,10,82$ 또는 $204$, 그러나 각각의 경우 $k \neq 2^{q-1}$ ...에 대한 $q$ 초기.

이제 $p>2$, $ 8 \nmid 11^p+17^p$.

이후 $p$ 이상하다 $$11^p + 17^p \equiv 3^p+1 \equiv 3+1\equiv 4 \mod 8$$

허락하다 $r$ 홀수 소수가되다 $3p^{q-1}+1$. 그때$r \notin \{3,11,17\}$.

물론이야 $r \neq 3$그렇지 않으면 형식의 숫자를 나눌 수 없습니다. $3k+1$. 그러나$3p^{q-1}+1$ 분할 $11^p+17^p$ 그래서 만약 $r$ RHS를 나누면 다음 중 하나를 나눌 수 없습니다. $11^p$ 또는 $17^p$다른 쪽도 나눠야하지만 둘 다 코 프라임입니다. 따라서$r \neq 11,17$.

이있다 $b$ 그런 $17b \equiv 1 \mod r$, Bezout의 정리에 의해. 보여줘$ord_r(11b) \in \{2,2p\}$.

만약 $17b \equiv 1 \mod r$ 그때 $b^p(11^p+17^p) \equiv (11b)^p +1\mod r$,하지만 $r$ 분할 $11^p+17^p$ 그래서 $(11b)^p + 1$ 의 배수입니다 $r$, 따라서 $(11b)^{2p}-1$ 의 배수입니다 $r$. 따라서$ord_r(11b)$ 분할 $2p$이지만 같지 않음 $1$ 명백하게.

허락하다 $ord_r(11b) = 2$. 그때$r=7$.

그렇다면 $r$ 분할 $(11b)^2-1$,하지만 또한 분할 $(11b)^2 - (17b)^2$, 그리고 그것은 coprime이기 때문에 $b$ 의 제수 $11^2-17^2 = -168$. 이후$r \neq 3$ 우리는 가져야한다 $r=7$.

만약 $ord_r(11b) = 2p$ 그때 $2p$ 분할 $r-1$, Fermat의 작은 정리에 의해. 따라서 우리는 소수 분해를 쓸 수 있습니다$$ 3p^{q-1}+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k} $$ 어디 $p_i \neq 2,7$ 주요 요인입니다 $p_i \equiv 1 \mod 2p$.
우리는 $\beta \leq 1$, 그것을 관찰함으로써 $\frac{11^p+17^p}{28}$ 의 배수가 아닙니다. $7$. (힌트 :$11+17= 28$, 그래서 분수는 확실히 자연수이지만 더 말할 수 있습니다) 따라서 $\beta \leq 1$.

표준 분해 $\frac{a^p-b^p}{a-b} = \sum_{k=1}^{n-1} a^kb^{n-k}$ 적용 $a=11,b=-17$ 그리고 우리는 $11 \equiv 4$ 과 $17 \equiv -4$ 모드 $7$, 그 $\frac{11^p+17^p}{28} \equiv p4^{p-1}$ 모드 $7$, 및 $p \neq 7$(왜?)

만약 $q=2$이면 문제에 해결책이 없습니다.

그렇다면 $3p+1 = 2^{\alpha}7^{\beta}p_1^{\gamma_1}...p_k^{\gamma_k}$, 그러나 각각 $p_i$ 적어도 $2p+1$ 절반 이상 $3p+1$. 그러므로 아니$p_i$있다. 기존 경계에 따라$\alpha,\beta$ 후보자 만있다 $3p+1 = 2,4,14,28$, 어느 것도 작동하지 않습니다.

만약 $q>2$, 다음 $\alpha = 2$ 과 $p=3$.

만약 $q>2$, 다음 $p^{q-1} \equiv 1 \mod 4$ 이후 $q-1$ 짝수이므로 $3p^{q-1} +1$ 의 배수입니다 $4$, 그래서 $\alpha = 2$. 드디어,$2^{\alpha}7^{\beta} p_1^{\gamma_1}...p_k^{\gamma_k}$ 에 합동 $4$ 또는 $28$ 모듈로 $p$, 때문에 $p_i$ 모두 합동 $1$ 모듈로 $p$. 그러나$3p^{q-1}+1$ 에 합동 $1$ 모듈로 $p$. 이것들이 같기 때문에 우리는$1-4$ 또는 $1-28$ 의 배수입니다 $p$. 어느 쪽이든$p=3$.

저것 좀 봐 $q=3$ 다음 경우에 발생해야합니다 $p=3$.

글쎄, 우리는 $11^3+17^3= 6244 = 2^2 \times 7 \times 223$, 그래서 만약 $3 \times 3^{q-1} +1$ 의 배수입니다 $6244$, 그러면 이것은 말하는 것과 같습니다. $3^q+1$ 의 배수입니다 $6244$, 따라서 $q=3$ 이후 유일한 옵션입니다 $q=1,2,4,...,7$ 작동하지 않고 $q=8$ 너무 큽니다.

그러므로 $p=q=3$ 유일한 해결책입니다.

2 sirous Nov 23 2020 at 14:49

또 다른 접근 방식 :

오일러의 기준으로 인해 :

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

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

이 두 관계는 $p=q=3$

이 경우 $A=28$.

우리는 이것을 RHS로 확인합니다. $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$ 과 $3^q$ 그래서 이상하다 $7b$ 따라서 짝수입니다.

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

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

$11^p+17^q$ 과 $4^p+3^q$ 그래서 이상하다 $7a+7b$ 짝수 여야합니다. $7b=14b_1$ 짝수이므로 $7a$ 또한 짝수 여야합니다. $7a=14a_1$, 그래서 우리는 :