Komentarz

XXX OM - I - Zadanie 7

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

  1. $ x $ daje resztę $ 0 $ lub $ 1 $ przy dzieleniu przez $ 2 $, gdy $ k = 1 $,
  2. $ x $ daje resztę $ 0 $, $ 1 $ lub $ -1 $ przy dzieleniu przez $ 4 $, gdy $ k = 2 $,
  3. $ 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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz