1990 년 IMO Q3 해결 방법
주문에 대한 수업에서 선생님이 나에게 주신 연습 중 하나는 1990 IMO 논문의 질문 3이었습니다.
모든 정수 찾기 $n>1$ 그런 $\frac{2^n+1}{n^2}$ 정수입니다.
내 시도 :
우리는 $$n^2|2^n+1\Rightarrow2^n+1\equiv0\pmod{n^2}\Rightarrow2^n\equiv-1\pmod{n^2}\Rightarrow2^{2n}\equiv1\pmod{n^2}$$ 어느 한 쪽 $\text{ord}_{n^2}(2)=1$, $\text{ord}_{n^2}(2)=2$, $\text{ord}_{n^2}(2)=d$ 어디 $d|n$, 또는 $\text{ord}_{n^2}(2)=2d$ 어디 $d|n$ 그러나 $2d\nmid n$.
만약 $\text{ord}_{n^2}(2)=1$, $2^1\equiv1\pmod{n^2}$, 다음 $n^2=1\Rightarrow n=1$. 이것은 다음에 대한 요구 사항과 모순됩니다.$n$.
만약 $\text{ord}_{n^2}(2)=2$, $2^2\equiv1\pmod{n^2}$, 다음 $n^2=1$ 또는 $3$ 그래서 $n$ 이다 $1$ 또는 $\sqrt3$. 이것은 또한 다음에 대한 요구 사항과 모순됩니다.$n$.
만약 $\text{ord}_{n^2}(2)=d$ 그러면 정수가 있습니다. $k$ 그런 $dm=n$. 그때$2^n=2^{dm}=\left(2^d\right)^m\equiv1^m=1\pmod{n^2}$. 이것은 모순$2^n\equiv-1$ 앞서 보여 드렸던 것입니다.
따라서 $$\text{ord}_{n^2}(2)=2d$$
오일러 정리 $2^{\phi(n^2)}\equiv1\pmod{n^2}$, 그래서 $2d|\phi(n^2)$. 같이$\phi(n)=n\prod_{p|n}\frac{p-1}p=nk$ 어디 $k=\prod_{p|n}\frac{p-1}p$, 및 $n$ 과 $n^2$ 동일한 소인수를 공유합니다. $$\phi(n^2)=n^2\prod_{p|n}\frac{p-1}p=n\left(n\prod_{p|n}\frac{p-1}p\right)=n(nk)=n\phi(n)$$
계속,
$$2d|\phi(n^2)\Rightarrow2d|n\phi(n)\Rightarrow2|m\phi(n)$$
어디 $dm=n$. 이것은$m$ 짝수 (즉 $n$ 짝수) 또는 $\phi(n)$ 짝수이다.
불행히도 나는 여전히 문제를 실제로 해결하지 못하고 있습니다. 보여주는 것이 분명합니다.$n$ 짝수 또는 $\phi(n)$ 그것을 보여주기에도 충분하지 않습니다 $\frac{2^n+1}{n^2}$ 정수입니다 (반례에는 $n=4$ 과 $n=5$). 내가 정한 조건을 만족하는 숫자가 무한히 많다. 그러나 어떻게 진행해야할지 모르겠으므로 질문을 마무리하는 데 도움이 필요합니다.
답변
$\textbf{Hint:}$의 최소 소수를 고려하십시오. $n$.
그런 다음 "지수 해제"기본형을 사용합니다.
그런 다음 두 번째로 작은 소수를 다시 고려하십시오. $n$
처음에는 가장 작은 소수를 고려하십시오. $p$ 의 $n$. 일 수 없습니다 $2$. 그때,$2^{2n}=1 \pmod {p}$, 또한 FLT $2^{p-1}=1 \pmod {p}$.
이 두 가지는 함께 의미 $2^{gcd(p-1,2n)}=1 \pmod {p}$.그러나 지금, $gcd(p-1,2n)=2$ 그 이후로 $n$ 보다 클 것이다 $p-1$. 이것은 $3$ 최소 소수 여야합니다. $n$ .이후 $2^2=1 \pmod{p}$ 위에서.
이제 가장 큰 힘이되는 지수 기본형을 해제하여 추론하십시오. $3$ 나누기 $n$ 이다 $1$그런 다음 가장 작은 소수를 고려하십시오. $n/3$.
위와 유사한 인수를 사용하여 $7$. 그러나 사실에서 $3 \mid n$ 그럴 수 없다는 것을 보여주세요. 그래서 유일한 해결책은 $n=3$
(힌트를 제공하기 위해 작성했기 때문에 세부 사항은 생략되었습니다)
자세한 솔루션은 여기를 참조하십시오 : aops