XV OM - I - Zadanie 5

Zawody matematyczne:

XV OM, 1963-1964

Etap:

Dowieść następujących twierdzeń, w których, $m$ i $n$ oznaczają liczby naturalne.
1. Jeżeli $m > 1$ , a $m^n-1$ jest liczbą pierwszą, to $n$ jest potęgą liczby 2 o wykładniku całkowitym.
2. Jeżeli $n > 1$ , a $m^n- 1$ jest liczbą pierwszą, to $m = 2$ , a $n$ jest liczbą pierwszą.

Rozwiązanie

1. Przypuśćmy, że $n$ nie jest potęgą liczby $2$ o wykładniku całkowitym. W takim razie $n$ posiada dzielnik nieparzysty większy od $1$ , np. $2p+1$ ; gdzie $p$ jest liczbą naturalną, zatem $n = k (2p + 1)$ , gdzie $k$ jest liczbą naturalną mniejszą od $n$ . Wówczas

$ m^n + 1 = m^{k(2p+1)} + 1 = (m^k)^{2p+1} + 1^{2p+1} $

zatem $m^n+1$ jest podzielne przez $m^k+1$ . Lecz z nierówności $m > 1$ , $k <n$ wynika, że

$ 1 < m^k + 1 < m^n + 1 $

wobec czego $m^n+1$ nie jest liczbą pierwszą. Otrzymaliśmy sprzeczność z założeniem twierdzenia; przypuszczenie, że $n$ nie jest potęgą całkowitą liczby $2$ jest zatem fałszywe.

2. Stwierdzamy najpierw, że $m > 1$ , gdyż dla $m = 1$ liczba $m^n- 1$ równałaby się zeru, a więc nie byłaby liczbą pierwszą. Ponieważ

$ m^n - 1 = m^n - 1^n, $

więc $m^n-1$ jest podzielne przez $m-1$ . Otóż $m^n- 1$ jest według założenia liczbą pierwszą, a $m-1 < m^n -1$ , gdyż $n > 1$ , wobec tego $m- 1= 1$ , tzn. $m = 2$ i $m^n-1 = 2^n-1$ . Gdyby $n$ nie było liczbą pierwszą, to zachodziłaby równość $n = p \cdot q$ , gdzie $p$ i $q$ oznaczają liczby naturalne większe od $1$ . Wtedy byłoby $2^n-1 = 2^{pq}- 1 = (2^p)^q - 1^q$ , więc $2^n-1$ byłoby podzielne przez $2^p-1$ , co jest niemożliwe, gdyż $1 < p < n$ , więc

$ 1 < 2^p - 1 < 2^n -1 $

a $2^n-1$ jest według założeń liczbą pierwszą.