Задача теории чисел с участием 42
Докажите, что n⁷ - n делится на 42 для любого натурального числа n.
Университет Торонто разместил эту полторы страницы головоломок. Сколько вы можете решить?
Вот первое:
Show that n⁷ − n is divisible by 42 for every positive integer n.
Мое решение
Сначала разложите многочлен на множители.
Многочлен состоит из трех факторов. Так же 42:
Мы должны найти каждый из этих трех целочисленных множителей среди полиномиальных множителей. Например, поскольку 42 четное, по крайней мере одно из n, n³ + 1 и n³-1 должно быть четным. Если n четно, мы удовлетворены. Если n нечетное, то и n³ тоже нечетное. Но и n³ + 1, и n³-1 будут четными.
По крайней мере, один из полиномиальных множителей четный. Этого достаточно, чтобы показать, что n⁷-n должно быть четным.
Считайте 3 фактором. Если 3 не делит n, то оно не делит и n³. Но любая строка из трех соседних целых чисел будет иметь ровно одно кратное 3. И такой строкой являются n³-1, n³ и n³ + 1. Одно из них кратно 3. Итак, n⁷-n должно быть кратно трем.
Чтобы показать, что 7 делит хотя бы одно из n, n³-1 и n³ + 1, мы раскроем нашу модульную арифметику.
Если 7 в n оставит нам 7 возможных остатков.
Первый случай, n≡0 (mod 7) соответствует 7 делению n. Затем подставьте каждый из следующих вычетов в два других полиномиальных множителя. В каждом случае один из них даст остаток по модулю 7. В этом случае 7 делит множитель.
Если 7 не делит n, оно делит либо n³ + 1, либо n³-1.
Поскольку мы показали, что 2, 3 и 7 являются делителями n⁷-n, мы показали, что 42 должно делить выражение.
Ваш дядя Боба!
