2^2013+1 в виде суммы двух квадратов

Ktina · 01/12/11 ∞ 8634

Доказать, что число $2^{2013}+1$
не представимо в виде суммы двух точных квадратов.

Cash · 12/09/10 1547

Так ведь оно на 3 делится...

Ktina · 01/12/11 ∞ 8634

Cash,
И что?
И поэтому оно не представимо?
$2^3+1$ тоже на 3 делится.

nnosipov · 20/12/10 9062

Это число делится на простое $683 \equiv 3 \pmod{4}$ , но не делится на $683^2$ . Последнее можно проверить и вручную. Но можно и обойтись без вычислений.

Ktina · 01/12/11 ∞ 8634

nnosipov в сообщении #701185 писал(а):

Это число делится на простое $683 \equiv 3 \pmod{4}$ , но не делится на $683^2$ .

А побольше простое не могли взять?
67, вроде, достаточно :wink:

Cash · 12/09/10 1547

Ktina в сообщении #701182 писал(а):

Cash,
И что?
И поэтому оно не представимо?
$2^3+1$ тоже на 3 делится.

Померещилось, что на 9 не делится...

nnosipov · 20/12/10 9062

Ktina в сообщении #701187 писал(а):

67, вроде, достаточно

Верю. Но как на него наткнуться? А $683$ --- это делитель $2^{11}+1$ .

Ktina · 01/12/11 ∞ 8634

Cash в сообщении #701189 писал(а):

Померещилось, что на 9 не делится...

На 9-то делится, да вот на 27 не делится. Значит, простой множитель $3=4\cdot 0+3$ содержится в чётной степени, а это нам ничего не даёт.

-- 25.03.2013, 16:15 --

nnosipov в сообщении #701197 писал(а):

Верю. Но как на него наткнуться? А $683$ --- это делитель $2^{11}+1$ .

А 67 -- это делитель $2^{33}+1$ .

nnosipov · 20/12/10 9062

Ktina в сообщении #701198 писал(а):

А 67 -- это делитель $2^{33}+1$

Как это увидеть без компьютера?

Ktina · 01/12/11 ∞ 8634

nnosipov в сообщении #701244 писал(а):

Как это увидеть без компьютера?

Выписать остатки, которые дают степени двойки при делении на простые числа вида $4n+3$ .
Я это сделала на бумаге, но мне просто повезло. Дойдя до числа 67, я обнаружила, что задачу можно решить :wink:

nnosipov · 20/12/10 9062

Понятно. Можно ещё так рассуждать. Рассмотрим число $2^{33}+1$ --- очевидный делитель числа $2^{2013}+1$ . Заметим, что число $p=67=2 \cdot 33+1$ --- простое. По критерию Эйлера имеем $2^{(p-1)/2} \equiv (2/p) \pmod{p}$ . Поскольку $(2/67)=-1$ , получим, что $2^{33}+1$ делится на $67$ .

Правда, теперь надо доказывать, что $2^{2013}+1$ не делится на $67^2$ . Но это тоже можно сделать без вычислений.

hippie · 18/01/12 933

nnosipov в сообщении #701244 писал(а):

Ktina в сообщении #701198 писал(а):

А 67 -- это делитель $2^{33}+1$

Как это увидеть без компьютера?

По малой теореме Ферма $(2^{33})^2 =2^{66}\equiv 1\ (\mod 67).$ В то же время $-2\equiv 400\ (\mod 67)$ — квадратичный вычет. Следовательно 2 — квадратичный невычет. Таким образом $2^{33}\not\equiv 1\ (\mod 67),$ и, следовательно, $2^{33}\equiv -1\ (\mod 67).$

Ktina в сообщении #701187 писал(а):

А побольше простое не могли взять?

Можно и побольше. 1772303994379887829769795077302561451 устроит? :mrgreen: