XXX OM - I - Zadanie 7

Zawody matematyczne:

XXX OM, 1978-1979

Etap:

Dla danego, naturalnego $n$ obliczyć liczbę liczb całkowitych $x$ z przedziału $[1, n]$ , dla których $x^3 - x$ jest podzielne przez $n$ .

Rozwiązanie

Jeżeli $n = p^k$ , gdzie $k \geq 1$ i $p$ jest liczbą pierwszą nieparzystą, to dla dowolnej liczby całkowitej $x$ co najwyżej jedna z liczb $x - 1, x, x + 1$ jest podzielna przez $p$ . Zatem liczba $x^3 - x = (x - 1) x(x + 1)$ jest podzielna przez $p^k$ wtedy i tylko wtedy, gdy jedna z liczb $x - 1, x, x + 1$ jest podzielna przez $p^k$ , to znaczy, gdy liczba $x$ daje jedną z reszt $1$ , $0$ lub $-1$ przy dzieleniu przez $p^k$ .

Jeżeli $n = 2^k$ , gdzie $k \geq 3$ , i $x$ jest liczbą parzystą, to liczby $x - 1$ i $x + 1$ są nieparzyste. Wobec tego liczba $x^3 - x = (x - 1)x(x+1)$ jest podzielna przez $2^k$ przy $x$ parzystym wtedy i tylko wtedy, gdy $x$ jest podzielne przez $2^k$ , tzn. gdy $x$ daje resztę $0$ przy dzieleniu przez $2^k$ .

Jeżeli $n = 2k$ , gdzie $k \geq 3$ , i $x$ jest liczbą nieparzystą, to tylko jedna z kolejnych liczb parzystych $x - 1$ i $x + 1$ jest podzielna przez $4$ . Ponieważ $k \geq 3$ , więc liczba $x^3 - x = (x - 1)x(x + 1)$ jest podzielna przez $2^k$ przy nieparzystym $x$ wtedy i tylko wtedy, gdy jedna z liczb $x- 1$ i $x + 1$ jest podzielna przez $2^{k-1}$ , a druga - przez $2$ . Ma to miejsce wtedy, gdy liczba $x$ przy dzieleniu przez $2^k$ daje jedną z reszt $1$ , $-1$ , $2^{k-1} + 1$ , $2^{k-1} - 1$ .

Wreszcie, jeżeli $n = 1$ lub $2$ , to dla dowolnej liczby $x$ zachodzi podzielność $n \mid x^3 - x$ , a jeżeli $n = 4$ , to liczba $x^3 - x = (x-<br /> 1)x(x + 1)$ jest podzielna przez $4$ wtedy i tylko wtedy, gdy $x$ daje resztę $1$ , $0$ lub $-1$ przy dzieleniu przez $4$ .

Dla rozpatrzenia przypadku ogólnego wykorzystamy tzw. twierdzenie chińskie o resztach: {\it Jeżeli $n_1, n_2, \ldots,n_r$ są liczbami naturalnymi parami względnie pierwszymi, $n = n_1 \cdot n_2 \ldots n_r$ , a $a_1, a_2, \ldots, a_r$ są dowolnymi liczbami całkowitymi, to istnieje dokładnie jedna liczba całkowita $a$ należąca do przedziału $[1, n]$ , taka że $n_i \mid a - a_i$ dla $i = 1, 2, \ldots, r$ , to znaczy liczby $a$ i $a_i$ dają tę samą resztę przy dzieleniu przez $n_i$ dla $i = 1, 2, \ldots, r$ .}

Niech $n = 2^k p_1^{k_1} p_2^{k_2} \ldots p_s^{k_s}$ , gdzie $s, k, k_1, k_2, \ldots, k_s$ są liczbami całkowitymi, $s \geq 0$ , $k \geq 0$ , $k_i > 0$ dla $i = 1,2, \ldots, s$ , a $p_1, p_2, \ldots, p_s$ są różnymi liczbami pierwszymi nieparzystymi.

Liczba $x^3 - x = (x - 1)x(x + 1)$ jest podzielna przez $n$ wtedy i tylko wtedy, gdy jest podzielna przez każdą z liczb $2^k, p_1^{k_1}, p_2^{k_2}, \ldots, p_s^{k_s}$ . Na mocy początkowej części rozwiązania warunek ten jest równoważny temu, że liczba $x$ daje jedną z reszt $0, 1, -1$ przy dzieleniu przez $p_i^{k_i}$ dla $i = 1, 2, \ldots, s$ oraz

$x$ daje resztę $0$ lub $1$ przy dzieleniu przez $2$ , gdy $k = 1$ ,
$x$ daje resztę $0$ , $1$ lub $-1$ przy dzieleniu przez $4$ , gdy $k = 2$ ,
$x$ daje jedną z reszt $0, 1, -1, 2^{k-1} -1, 2^{k-1} + 1$ przy dzieleniu przez $2^k$ , gdy $k \geq 3$ .

Na mocy twierdzenia chińskiego o resztach liczba liczb $x$ z przedziału $[1, n]$ spełniających warunki zadania jest więc równa $3^s, 2 \cdot 3^s, 3 \cdot 3^s$ lub $5 \cdot 3^s$ , gdy $k = 0$ , $k = 1$ , $k = 2$ lub $k \geq 3$ odpowiednio.