Делимост

[Гост]

Да се докаже, че [tex]n[/tex] не дели [tex]2^{n}-1[/tex] за цели [tex]n>1[/tex].

[Добромир Глухаров]

Да допуснем, че $n|(2^n-1)\Rightarrow2^n\equiv1(mod\ n)$. Но от Теоремата на Ойлер $2^{\varphi(n)}\equiv1(mod\ n)\Rightarrow\varphi(n)|n$, а последното не е вярно за нечетни $n$. Ако пък $n$ е четно, но $n$ не се дели на $4$, $4^{\frac{n}{2}}\equiv1(mod\ \frac{n}{2})$, $(4,\frac{n}{2})=1$ и прилагаме Теоремата на Ойлер за $\frac{n}{2}$. Ако $n=2^k.m\ (2\nmid m)$, прилагаме последното $k$ пъти. Така винаги достигаме до противоречие.

Дано не съм Ви заблудил. Признавам, че не съм много сигурен в горното.

[Knowledge Greedy]

За четно [tex]n[/tex] е ясно.
Нека [tex]n[/tex] е нечетно. Понеже [tex](2, n)=1[/tex], се изпълнява МТФ. Значи [tex]2^n-2[/tex] се дели на [tex]n[/tex].
Ако допуснем, че за някое [tex]n[/tex] и числото [tex]2^n-1[/tex] се дели на [tex]n[/tex], ще излезе че и тяхната разлика - числото [tex]1[/tex] също се дели на [tex]n[/tex] - невъзможно за [tex]n>1[/tex].

[pal702004]

Горното е вярно за просто $n$, (само тогава е в сила МТФ). В по-общ вид, $2^n-1$ не се дели на най-малкия прост делител на $n$. Нека $p$ е най-малкият прост делител на $n$ и нека $d$ е най-малкото естествено, за което $2^d\equiv 1 \pmod p$. Тогава

$d\mid (p-1)$ (по МТФ), а също така $d\mid n$ (по условие). Или $d$ е общ делител на $n=kp$ и $p-1$.


Но $\gcd(kp,p-1)=\gcd(k,p-1)=1$

Последното следва от факта, че $p$ е най-малкият прост делител на $n=kp$, тоест, $k$ е взаимнопросто с всички естествени числа, по-малки от $p$


Значи $d=1$, което няма как да е вярно.