Zbiór zadań, (zadania różne)
Zadanie 303
Znajdź najmniejszą liczbę naturalną $n$ taką, że jest ona dzielnikiem liczby $2^n-2$, ale nie jest dzielnikiem liczby $3^n-3$.
Rozwiązanie
W myśl twierdzenie Fermata dla liczb pierwszych $n$ obie liczby są podzielne przez $n$, więc szukana liczba musi być liczbą złożoną. Liczby pseudopierwszymi nazywamy liczby złożone, które spełniają warunki małego twierdzenia Fermata. Najmniejsze liczby pseudopierwsze, dla których $2^n-2$ jest podzielne przez $n$ to: $341, 561, 645, 1105, 1387, 1729, 1905, \ldots$
Liczba $341$ jest podzielna przez $2^{341}-2$
Zachodzi $11|2^{10}-1 = 1023$, skąd $11|2^{340}-1$ oraz $11|2^{341}-2$
Mamy też $31 = 2^5 - 1|2^{340}-1$, skąd $31|2^{341}-2$
Liczba $2^{341}-2$ jest więc podzielna przez $11$ i $31$, zatem też przez $341$.
Sprawdźmy, czy liczba $341$ spełnia twierdzenie Fermata dla podstawy $3$.
$341 = 11 \cdot 31$
Na podstawie tego samego twierdzenia mamy $a^{p-1} \equiv 1 \pmod p$.
$3^{30} \equiv 1 \pmod {31}$
$3^{330} \equiv 1 \pmod {31}$
$3^{330} \equiv 3^{11} \pmod {31}$
wobec $3^{3} \equiv -4 \pmod {31}$ mamy $3^{9} \equiv -64 \pmod {31}$, skąd $3^{11} \equiv -18 \pmod {31}$
$3^{341} - 3 \equiv 3^{11} - 3 \pmod {31} = -21 \equiv \pmod {31}$
Stąd $31$ nie dzieli $3^{341} - 3$, tym bardziej $341 = 31 \cdot 11 $ nie dzieli $3^{341} - 3$.
Najmniejszą liczbą spełniającą warunki zadania jest $341$.
powrót do zbioru zadań | wersja do druku << poprzednie zadanie następne zadanie >>