XXXI - I - Zadanie 9

Dowieść, że liczba naturalna $ n > 1 $ dzieli liczbę $ a^{(n-1)! + 1} $ - a dla każdego całkowitego $ a $ wtedy i tylko wtedy, gdy $ n $ jest iloczynem różnych liczb pierwszych.

Rozwiązanie

Liczby całkowite niepodzielne przez kwadrat żadnej liczby pierwszej nazywa się liczbami bezkwadratowymi. Pokażemy najpierw, że warunek, by $ n $ była liczbą bezkwadratową jest konieczny na to, by $ n $ dzieliło $ a^{(n-1)!+1} - a $ dla każdego całkowitego $ a $. Załóżmy bowiem, że $ n $ dzieli się przez kwadrat liczby pierwszej $ p $ i przyjmijmy $ a = p $. W różnicy $ p^{(n-1)!+1} - p $ odjemna
dzieli się przez $ p^2 $, odjemnik zaś nie dzieli się przez $ p^2 $, więc $ p^{(n-1)!+1} - p $ nie dzieli się przez $ p^2 $, tym bardziej więc nie dzieli się przez liczbę $ n $, która jest wielokrotnością liczby $ p^2 $.

Dla dowodu dostateczności warunku załóżmy, że $ n $ jest liczbą bezkwadratową, $ n = p_1p_2 \ldots p_k $, gdzie $ p_i $ są liczbami pierwszymi $ p_i \ne p_j $ dla $ i \ne j $. Aby wykazać, że $ n $ dzieli $ a^{(n-1)!+1} - a $, wystarczy stwierdzić, że $ a^{(n-1)!+1} - a $ jest podzielne przez $ p_i $ $ (i = 1, 2, \ldots,n) $. Jeżeli $ p_i $ dzieli $ a $, to oczywiście $ p_i $ dzieli $ a^{(n-1)!+1} - a $. Zajmijmy się przypadkiem, gdy $ p_i $ nie dzieli $ a $. W tym przypadku $ p_i $ nie dzieli żadnej z $ p_i $ liczb $ 1, a, a^2, \ldots, a^{p_i-1} $, zatem pewne dwie z tych liczb dają przy dzieleniu przez $ p_i $ tę samą resztę; niech będą to $ a^k $ i $ a^l $ dla $ 0 \leq k < l< p_i : a^k = t \cdot p_i + r $, $ a^l = s \cdot p_i + r $. Wobec tego liczba $ a^l - a^k $ dzieli się przez $ p_i $, a więc $ a^{l-k} - 1 $ dzieli się przez $ p_i $. Ponieważ $ l - k < p_i \leq n $, więc $ l - k $ dzieli $ (n- 1)! $. Jest więc $ (n - 1)! = (l - k) \cdot w $, a zatem $ a^{(n-1)!+1} - a = (a^{l-k} - 1) (a^{(l-k)(w-1)} + a^{(l-k)(w-2)} + \ldots + a^{l-k} + 1) $. Wobec tego $ a^{l-k} - 1 $ dzieli $ a^{(n-1)!} - 1 $, dzieli więc też $ a(a^{(n-1)!} - 1) = a^{(n-1)!+1} - a $. Wynika stąd, że $ p_i $ będące dzielnikiem $ a^{l-k} - 1 $ dzieli również $ a^{(n-1)!+1} - a $, co kończy dowód.

Uwaga. Dowód dostateczności warunku głoszącego, że $ n $ jest liczbą bezkwadratową można nieco skrócić korzystając z małego twierdzenia Fermata.

Dla każdej liczby całkowitej $ a $ oraz liczby pierwszej $ p_i $ liczba $ a^{p_i} - a $ jest podzielna przez $ p_i $.

W przypadku, gdy $ p_i $ nie dzieli $ a $, wynika z tego twierdzenia bezpośrednio, że $ p_i $ dzieli $ a^{p_i-1} - 1 $.

Komentarze

Dodaj nową odpowiedź