Пленительная неделимость

[Ktina]

Доказать, что $3^n-1$ не делится на $2^n-1$ ни при каком натуральном $n>1$

[DjD USB]

От противного. Допустим делится, тогда и число $3^n-1-(2^n-1)=3^n-2^n$ делится на $2^n-1$ Следовательно

$$3^n \equiv 2^n \pmod {2^n-1}$$

$$ 3 \equiv 2 \pmod {2^n-1}$$

$$1 \equiv 0 \pmod {2^n-1}$$

Значит 1 длится на $2^n-1$, но при n>1 это не возможно... Получили противоречие.

(Оффтоп)

Теперь осталось найти ошибку в решении

[Ktina]

DjD USB в сообщении #804444 писал(а):

$$3^n \equiv 2^n \pmod {2^n-1}$$

$$ 3 \equiv 2 \pmod {2^n-1}$$

Это и есть ошибка.

-- 22.12.2013, 01:55 --

Нижняя строка из верхней, в общем случае, не следует!

-- 22.12.2013, 01:59 --

Иными словами,

$$\left((3^n \equiv 2^n \pmod {2^n-1})\quad\to\quad (3 \equiv 2 \pmod {2^n-1})\right)=0$$

[DjD USB]

А если так,

$$3^n \equiv 1 \pmod{2^n-1}$$

Значит либо

$$3 \equiv 1 \pmod{2^n-1}$$

Либо

$$3 \equiv -1 \pmod{2^n-1}$$

Получаем четное число делится на нечетное в обоих случаях...

[Ktina]

DjD USB в сообщении #804451 писал(а):

Получаем четное число делится на нечетное в обоих случаях...

А почему от амбала дети не рождаются чётное не может делится на нечётное?

[DjD USB]

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

DjD USB в сообщении #804451 писал(а):

Получаем четное число делится на нечетное в обоих случаях...

А почему от амбала дети не рождаются чётное не может делится на нечётное?

Потому что у нас четное-- это степень двойки

[Ktina]

DjD USB в сообщении #804454 писал(а):

Потому что у нас четное-- это степень двойки

Запутали Вы меня

[DjD USB]

Ну...

$$4 \equiv 0 \pmod{2^n-1}$$

Либо

$$2 \equiv 0 \pmod{2^n-1}$$

[nnosipov]

DjD USB, эта задача довольно сложная, здесь сермяжных соображений недостаточно. Нужен более тонкий подход.

Пару лет назад тонкости этого сюжета мы здесь уже обсуждали, попробуйте поискать соответствующую тему.

[Null]

$\varphi (2^n-1)\vdots n$

[Ktina]

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

...
Пару лет назад тонкости этого сюжета мы здесь уже обсуждали, ...

Я в курсе, но мне не удалось отыскать это обсуждение.

[nnosipov]

Null в сообщении #804526 писал(а):

$\varphi (2^n-1)\vdots n$

Это верно. А что дальше?

-- Вс дек 22, 2013 14:25:58 --

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

Я в курсе, но мне не удалось отыскать это обсуждение.

Надо бы всё-таки найти. Попозже попробую.

[Null]

$\varphi (2^n-1)\vdots n^2$ так как $2^l 3^m$ - подгруппа коммутативной группы.(и все элементы в ней различны)

[nnosipov]

Null в сообщении #804553 писал(а):

$\varphi (2^n-1)\vdots n^2$ так как $2^l 3^m$ - подгруппа коммутативной группы.(и все элементы в ней различны)

Это, видимо, какое-то условное утверждение, потому что если $n$ произвольно, то $\varphi(2^n-1)$ не обязано делиться на $n^2$. Вы не могли бы написать подробнее?

[Null]

Ну если $3^n-1\vdots(2^n-1)$