Малая теорема Ферма. Найдите все возможные остатки 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 включительно, но это не подходит. Где ошибка?

Единственный возможный остаток: \(0\).

Действительно, по малой теореме Ферма для любого целого \(n\):

\[n^7\equiv n\pmod 7,\]

значит, \(n^7-n\) делится на \(7\).

Также \(n^7-n=n(n^6-1)\) делится на \(2\) и на \(3\): при делении на \(2\) и на \(3\) всегда выполняется \(n^7\equiv n\). Следовательно, число делится на \(2\), \(3\) и \(7\). Эти числа попарно взаимно просты, поэтому оно делится на

\[2\cdot3\cdot7=42.\]

Значит,

\[n^7-n\equiv0\pmod{42}.\]

Ошибка в рассуждении — в записи \(n^6-1\equiv1\pmod6\). Это неверно: остаток \(n^6-1\) при делении на \(6\) зависит от \(n\). Например, при \(n=1\) он равен \(0\), а не \(1\).

0 0 Пожаловаться