Математикадан республикалық олимпиада, 2001-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$ что верно, значит такой простой делитель есть.