Question

! Малая теорема Ферма!
Все возможные остатки n^7 - n при деление на 42
В чем проблема. Я раскладываю на n^7 n n = 1 (mod 7) и n(n^6 - 1). Второе раскладываю на n^6 - 1 = 1 (mod 6) и n/6. Получается остатки все цифры от 0 до 5 включительно, но это не подходит. Помогите, пожалуйста, я не понимаю, где ошибка

Answer 1

Ответ:

Как ты уже правильно раскладываешь, мы имеем:

n^7 - n = n(n^6 -1) = n(n^3 - 1)(n^3 + 1) = n(n-1)(n+1)(n^2+n+1)(n^2-n+1)(n^3 + 1)

П1)

Используем малую теорему Ферма для n, которые не делятся на 7:

n^(7-1) ≡ 1 (mod 7)

n^6 ≡ 1 (mod 7)

Тогда n^(7) - n ≡ 0 (mod 7) для всех n, которые не делятся на 7.

Теперь рассмотрим n, которые делятся на 7:

n^7 - n = n(n^6 - 1)

n^6 - 1 = (n^3)^2 - 1 = (n^3 + 1)(n^3 - 1)

Сначала рассмотрим n^3 - 1. Используем малую теорему Ферма для n, которые не делятся на 3:

n^(3-1) ≡ 1 (mod 3)

n^2 ≡ 1 (mod 3)

Тогда (n^3 - 1) ≡ (n^2 - 1) ≡ 0 (mod 3) для всех n, которые не делятся на 3.

Теперь рассмотрим n^3 + 1. Используем малую теорему Ферма для n, которые не делятся на 2:

n^(2-1) ≡ 1 (mod 2)

n ≡ 1 или -1 (mod 2)

Тогда, если n нечетное, то n^3 + 1 будет четное, а если n четное, то n^3 + 1 будет нечетное. Таким образом, для всех n, которые не делятся на 2, будет выполняться (n^3 + 1) ≡ 2 (mod 4).

Итак, мы имеем:

(n^3 - 1) ≡ 0 (mod 3) для всех n, которые не делятся на 3.

(n^3 + 1) ≡ 2 (mod 4) для всех n, которые не делятся на 2.

Используя китайскую теорему об остатках, мы можем найти все возможные остатки n^7 - n при делении на 42. Для этого нам нужно решить систему уравнений:

x ≡ 0 (mod 3)

x ≡ 2 (mod 4)

Решение этой системы - x ≡ 26 (mod 12).

Таким образом, все возможные остатки n^7 - n при делении на 42 равны 0 или 26.