Show that we can find infinitely many positive integers $ \displaystyle n $ such that $ \displaystyle 2^n - n $ is a multiple of any given prime $ \displaystyle p $.
Traduzione:
Dimostrare che esistono infiniti interi positivi $ \displaystyle n $ tali che $ \displaystyle 2^n-n $ è un multiplo di un dato primo $ \displaystyle p $.
Bye,
#Poliwhirl#
Per chi adora il Canada...(CanMO 1983)
La tesi è banale se $ p = 2 $, ché è sufficiente assumere in tal caso $ n = 2k $, con $ k\in\mathbb{N}_0 $. Sia dunque per il seguito $ p \geq 3 $. Allora $ \gcd(p,2) =1 $, e di conseguenza, in base al teorema di Euler-Fermat: $ 2^{(p-1)u} \equiv 1 \bmod p $, qualunque sia $ u\in\mathbb{N} $. Posto pertanto $ n = (p-1)(pk-1) $, per qualsivoglia $ k\in\mathbb{N}_0 $, si trova $ 2^n - n \equiv 2^{(p-1)(pk - 1)} - (p-1)(pk - 1) \equiv 1 - 1 \equiv 0 \bmod p $. Da qui l'asserto, q.e.d.