Найти их все (арифметическая задача)

[Ktina]

Найти все натуральные $n$, для которых существует такое натуральное $m$, что $m^2+9$ делится на $2^n-1$

[mihiv]

Если $m$ не кратно 3,то $m^2+9$,как сумма взаимно простых квадратов имеет простые делители только вида $4k+1$ и не может делиться на $2^n-1$,которое содержит простой делитель вида $4k-1$.
Поэтому $m=3m_1$ и $m^2+9=9(m_1^2+1)$.Следовательно,$2^n-1$ должно содержать простой делитель 3 в степени не выше второй и не содержать других простых делителей вида $4k-1$.Это возможно,только если $n=2^k$.

[Ktina]

mihiv в сообщении #574805 писал(а):

...сумма взаимно простых квадратов имеет простые делители только вида $4k+1$...

Что это за теорема?

[nnosipov]

Осталось добавить, что любого $n=2^k$ подходящее $m$ действительно существует.

-- Ср май 23, 2012 01:40:35 --

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

Что это за теорема?

Теорема Ферма-Эйлера. В "Кванте" про неё можно почитать. (Ой, пардон, это более простой факт, он вытекает из малой теоремы Ферма.)

А задача --- самодельная или откуда-то?

[Ktina]

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

А задача --- самодельная или откуда-то?

Из Румынии: http://imomath.com/othercomp/Rom/RomTST99.pdf (третий тест, задача № 3).