Question

Чому може дорівнювати остача при діленні k³ на 9?

Answer 1

У розв'язку конгруентність всюди мається на увазі за модулем 9, щоб кожний раз не писати $(\text{mod }9)$.

Число $k$ при діленні на 9 може дати одну з дев'яти остач від 0 до 8:

$k\equiv 0 \qquad k^3 \equiv 0^3 \equiv 0\\k \equiv 1 \qquad k^3 \equiv 1^3 \equiv 1\\k \equiv 2 \qquad k^3 \equiv 2^3 \equiv 8\\ \\k \equiv 3 \qquad k^3 \equiv 3^3 =9 \cdot 9^2 \equiv 0\\ k \equiv 4 \qquad k^3\equiv 4^3=4^2 \cdot 4=16 \cdot 4 \equiv 7 \cdot 4=28 \equiv 1\\k \equiv 5 \qquad k^3 \equiv 5^3=25 \cdot 5 \equiv 7 \cdot 5=35 \equiv 8$

$k \equiv 6 \qquad k^3\equiv 6^3=36 \cdot 6= 9\cdot 4 \cdot 6 \equiv 0\\k\equiv 7 \qquad k^3\equiv 7^3=49 \cdot 7 \equiv 4 \cdot 7=28 \equiv 1\\k\equiv8 \qquad k^3\equiv 8^3 \equiv 64 \cdot 8 \equiv 1 \cdot 8\equiv 8$

Відповідь: 0, 1, 8.

P. S. Оскільки остачі циклічно повторюються, то має існувати коротший алгоритм пошуку, але я розв'язав напролом.

Якщо що-небудь незрозуміло — запитуй, поясню.