Как решить 1990 IMO Q3
Для моего урока по заказу одним из упражнений, которые дал мне мой учитель, был вопрос 3 из статьи ИМО 1990 года:
Найти все целые числа $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