XXXI - I - Zadanie 9

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

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.