Matematyka.pl

Znaleźć wszystkie liczby całkowite dodatnie \(\displaystyle{ n<10^{100}}\), dla których jednocześnie zachodzi
\(\displaystyle{ n|2^n, \ n-1|2^{n}-1, \ n-2|2^n-2}\)

Widzimy, że \(\displaystyle{ n=1}\) nie spełnia warunków zadania, dalej niech \(\displaystyle{ n>1}\).
Skoro \(\displaystyle{ n|2^n}\), to mamy \(\displaystyle{ n=2^k}\) dla pewnego \(\displaystyle{ k\in \NN}\).
Lemat:
\(\displaystyle{ 2^k-1|2^n-1 \Leftrightarrow k|n}\)

Implikacja w lewo wynika natychmiast ze wzoru na różnicę \(\displaystyle{ r}\)-tych potęg, pokażemy implikację w prawo. Przypuśćmy nie wprost, że
liczby \(\displaystyle{ k\le n \in \NN^+}\) spełniają warunek \(\displaystyle{ 2^k-1|2^n-1}\), lecz \(\displaystyle{ k\nmid n}\). Zapiszmy \(\displaystyle{ n=ak+b, \ a\in \NN^+, \ b\in \left\{ 1,\ldots k-1\right\}}\).
Mamy
\(\displaystyle{ 2^{n}-1=2^{ak+b}-1=2^b(2^{ak}-1)+2^b-1}\).
ze wspomnianego wzoru na różnicę \(\displaystyle{ r}\)-tych potęg wiemy, że \(\displaystyle{ 2^k-1|2^{ak}-1}\), stąd
\(\displaystyle{ 2^{k}-1|2^b(2^{ak}-1)}\), więc aby zaszło \(\displaystyle{ 2^k-1|2^n-1}\), potrzeba i wystarcza, że
\(\displaystyle{ 2^{k}-1|2^b-1}\), ale to jest wykluczone, gdyż \(\displaystyle{ f(x)=2^x}\) jest rosnąca (by się o tym przekonać, można obliczyć jej pochodną, choć to fakt ze szkoły) oraz \(\displaystyle{ 0< b<k}\), toteż \(\displaystyle{ 0<2^b-1<2^k-1}\). Otrzymana sprzeczność kończy dowód.

Wracając do rozwiązania zadania, niech \(\displaystyle{ n=2^k}\). Mamy \(\displaystyle{ n-1|2^n-1}\), czyli
\(\displaystyle{ 2^k-1|2^n-1}\), z lematu \(\displaystyle{ k|n}\), toteż \(\displaystyle{ k=2^l}\) dla pewnego \(\displaystyle{ l\in \NN}\).
Ponadto ma być \(\displaystyle{ n-2|2^n-2}\), czyli \(\displaystyle{ 2^k-2|2^n-2}\) i stąd
\(\displaystyle{ 2^{k-1}-1|2^{n-1}-1}\), z lematu
\(\displaystyle{ k-1|n-1}\), czyli \(\displaystyle{ 2^l-1|2^k-1}\), ponownie z lematu mamy, że \(\displaystyle{ l|k}\), ale \(\displaystyle{ k}\) jest w formie \(\displaystyle{ 2^l}\), czyli \(\displaystyle{ l=2^i}\) dla pewnego \(\displaystyle{ i\in \NN}\).
Ostatecznie otrzymujemy, że warunki zadania spełniają liczby postaci
\(\displaystyle{ n=2^{2^{2^i}}}\), a ponieważ ma być \(\displaystyle{ n<10^{100}}\)
i jest
\(\displaystyle{ 2^{2^{2^4}}=2^{2^{16}}>2^{2^{10}}=2^{1024}=16^{256}>10^{100}}\)
oraz
\(\displaystyle{ 2^{2^{2^3}}=2^{256}<2^{258}=8^{84}<10^{100}}\), więc warunki zadania spełniają liczby
\(\displaystyle{ 2^{2^{2^0}}, \ 2^{2^{2^1}}}, \ 2^{2^{2^2}}, \ 2^{2^{2^3}}}\)