Rozkład iloczynu

[mol_ksiazkowy]

Udowodnić, że jesli \(\displaystyle{ 2^n - 1 = ab}\) to \(\displaystyle{ ab - (a-b)-1}\) jest w formie \(\displaystyle{ k2^{2m}}\) gdzie \(\displaystyle{ k}\) i \(\displaystyle{ m}\) są to liczby naturalne, oraz \(\displaystyle{ k}\) jest nieparzystą.

[arek1357]

\(\displaystyle{ n=3}\)

\(\displaystyle{ 2^n-1=2^3-1=7=1 \cdot 7=7 \cdot 1}\)

\(\displaystyle{ a=7, b=1}\)

\(\displaystyle{ ab-(a-b)-1=7 \cdot 1-(7-1)-1=7-6-1=0=k \cdot 2^{2m}}\)

\(\displaystyle{ k}\) - nieparzyste...

jakaś lipa...

[Blazo2000]

Ja powiem tak, że \(\displaystyle{ k=0}\), dla \(\displaystyle{ b=1}\) oraz \(\displaystyle{ k}\) jest nieparzyste w każdym innym przypadku.
\(\displaystyle{ k}\) w rozwiązaniu to nie to samo \(\displaystyle{ k}\) co w treści.
Rozwiązanie:

Ukryta treść:    

Zauważmy, że:
\(\displaystyle{ (1)ab - (a - b) - 1 = (a+1)(b-1)}\)
Niech \(\displaystyle{ p(x)}\) oznacza największy wykładnik, w jakim \(\displaystyle{ 2}\) dzieli \(\displaystyle{ x}\), pokażemy, że \(\displaystyle{ p(a+1)=p(b-1)}\), dla \(\displaystyle{ b>1}\), co zakończy dowód. Przypuśćmy, że nasza teza nie zachodzi, dla pewnych \(\displaystyle{ a, b}\), takich że \(\displaystyle{ b>1}\). Możemy założyć, że \(\displaystyle{ p(a+1)>p(b-1)}\), dowód w przeciwnym przypadku jest analogiczny. Mamy więc, \(\displaystyle{ p(a+1)=k+z}\) oraz \(\displaystyle{ p(b-1)=k}\), gdzie \(\displaystyle{ z>0}\), skoro \(\displaystyle{ b>1}\), to \(\displaystyle{ k}\) jest skończone. Przypuśćmy teraz, że \(\displaystyle{ k \ge n}\), mamy wówczas:
\(\displaystyle{ ab \ge 2 ^{2k+z} > 2 ^{k} \ge 2 ^{n}>2 ^{n} -1=ab}\)
Jawna sprzeczność dowodzi, że \(\displaystyle{ k<n}\), wobec tego \(\displaystyle{ (2)p(ab+1)=p(2 ^{n})=n \ge k+1}\). Z drugiej strony skoro \(\displaystyle{ z>0}\), to \(\displaystyle{ a}\) daje resztę \(\displaystyle{ -1}\) z dzielenia przez \(\displaystyle{ 2 ^{k+1}}\), natomiast \(\displaystyle{ b}\) daje pewną resztę \(\displaystyle{ 0 \le y \le 2 ^{k+1}-1}\), z dzielenia przez \(\displaystyle{ 2 ^{k+1}}\), jednak nie jest to \(\displaystyle{ 1}\), bo \(\displaystyle{ 2 ^{k+1}}\) nie dzieli \(\displaystyle{ b-1}\). W tej sytuacji \(\displaystyle{ ab}\) daje resztę \(\displaystyle{ -(2 ^{k+1}-1) \le -y \le 0}\) z dzielenia przez \(\displaystyle{ 2 ^{k+1}}\), ale różną od \(\displaystyle{ -1}\), co oznacza, że liczba \(\displaystyle{ ab+1}\), daje resztę \(\displaystyle{ -(2 ^{k+1}-1)+1 \le -y+1 \le 1}\), z dzielenia przez \(\displaystyle{ 2 ^{k+1}}\), ale różną od \(\displaystyle{ 0}\) i nie jest w takim razie podzielna przez \(\displaystyle{ 2 ^{k+1}}\), co oznacza, że \(\displaystyle{ p(ab+1)<k+1}\), co w połączeniu z wyrażeniem \(\displaystyle{ (2)}\) daje sprzeczność i kończy dowód.
Drugą część dowodu można przeprowadzić ładniej. Skoro \(\displaystyle{ z>0}\), to \(\displaystyle{ 2 ^{k+1}}\) dzieli \(\displaystyle{ (a+1)(b+1)=ab+1+a+b}\), a skoro \(\displaystyle{ k+1 \le n}\), to dzieli także \(\displaystyle{ ab+1}\) i wobec tego dzieli również \(\displaystyle{ a+b=(a+1)+(b-1)}\), więc dzieli także \(\displaystyle{ b-1}\), a zatem mamy \(\displaystyle{ k=p(b-1) \ge k+1}\), co jest sprzecznością dla skończonego \(\displaystyle{ k}\).