Udowodnienie podzielności przez 2003

[tomalla]

Witam wszystkich użytkowników

Podczas rozwiązywania jednego z zadań ( dotyczące właśnie podzielności ) zatrzymałem się nad jedną rzeczą ... a mianowicie, w jaki sposób udowodnić, że \(\displaystyle{ 2003|1+2^{1001}}\) ? Ma ktoś jakiś pomysł?

[czeslaw]

Aby \(\displaystyle{ 2003|1+2^{1001}}\), musi zachodzić \(\displaystyle{ 2002|2^{1001}}\). No a \(\displaystyle{ 2^{1001}}\) na pewno dzieli się przez 2 oraz przez 1001 (bo to po prostu iloczyn 1001 dwójek), zatem jest podzielne także przez iloczyn tych liczb - 2002.

[kubek1]

Najlepiej policzyć to siłowo, korzystając z kongruencji i wtedy wyjdzie
czeslaw, a od kiedy \(\displaystyle{ 2^n}\) dzieli się przez liczbę nieparzystą? Ponadto z tego, że \(\displaystyle{ 2003|2^{1001}+1}\) nie można wnioskować, że \(\displaystyle{ 2002|2^{1001}}\), (bo według Ciebie z podzielności np. \(\displaystyle{ 5|5^2}\) wynika \(\displaystyle{ 6|5^2+1}\))

[tomalla]

@kubek1, na początku też tak próbowałem, ale to chyba bez sensu ... na pewno jest na to łatwiejszy sposób niż męczenie się nad mnożeniem pisemnym

[kubek1]

Niestety, takiego nie ma. 2003 jest liczbą pierwszą, a więc z MTF wiadomo, że \(\displaystyle{ 2003|2^{2002}-1}\), dlatego trzeba to robić siłowo.

Poprawiłem

[czeslaw]

O kurde. Nieźle. Nie wiem o czym ja myślałem.

[max]

Tam wyżej zdarzyła się literówka - z MTF wiadomo, że \(\displaystyle{ 2003\mid 2^{2002} - 1.}\)
Uzasadnienie bez potęgowania stronami kongruencji można uzyskać wiedząc trochę o resztach kwadratowych:
\(\displaystyle{ 2003\equiv 3\pmod{8},}\) w związku z tym \(\displaystyle{ 2}\) jest nieresztą kwadratową \(\displaystyle{ \mod 2003,}\) (co wynika np z ) zatem z :
\(\displaystyle{ 2^{1001}=2^{\frac{2003 - 1}{2}} \equiv -1 \pmod{2003}.}\)