Республиканская олимпиада по математике, 2002 год, 11 класс

Докажите, что при любых целых $n > m > 0$ число $2^n-1$ имеет простой делитель, не делящий $2^m-1$.

Комментарий/решение

Воспользуемся леммой что $d=(2^n-1,2^m-1) = (2^{(n,m)}-1) \leq 2^{m}-1$ (следствие теоремы Евклида которая выполняется одновременно и для степеней).

Если $d=1$ то очевидно что такое число существует, рассмотрим случай $d=(a,b) \ne 1$ учитывая $n>m$, докажем что если $2^n-1=d \cdot a$ то $a>d$ (что и докажет существование такого делителя) или $(2^{(n,m)}-1)^2 \leq (2^m-1)^2<2^n-1$ пусть $n=dm$ и $2^m=t$ тогда $(t-1)^2<t^d-1$ откуда $t>1$ или $2^m>1$ что верно, значит такой простой делитель есть.