Задача дискретной математики про эквивалентность функций

[ruslanbadamhsin]

Здравствуйте. Нашёл в задачнике по дискре такой вопрос, тема - k-значная логика:

При каких k >= 3 функции x^2, x^3 и x^4 имеют попарно различные значения?

Проверка вручную показала, что при k != 3, 4 не подходят, ответы добавили сюда ещё 6 и 12. К сожалению, я не очень хорош в теории чисел и не знаю многие факты про остатки, но чувствую, что доказательство не особо трудное, раз все остальные k (даже содержащие 3, 2 и 4 в множителях) подходят. Как это можно доказать? Заранее спасибо.

[dgwuqtj]

Я правильно понимаю, что нужно найти такие $k$, что ваши функции попарно различны как отображения $\mathbb Z / k \mathbb Z \to \mathbb Z / k \mathbb Z$? Можно начать с того, что если $k$ подходит, то все его кратные тоже подходят. А потом попробовать доказать, что $8$, $9$ и все простые числа, начиная с $5$, подходят.

[ruslanbadamhsin]

dgwuqtj в сообщении #1662010 писал(а):

если $k$ подходит, то все его кратные тоже подходят.

Не всегда. 12 кратно 3 и 4, но они все не подходят. 8 кратное 4, уже котируется, и тд

[iifat]

ruslanbadamhsin в сообщении #1661998 писал(а):

k-значная логика

Если вы думаете, что вы что-то сказали, то вы, по-моему, ошибаетесь. Вот в статье Википедии говорится о десятке различных логик; к примеру, в $k$-значных логиках Гёделя конъюнкция — это минимум двух аргументов, стало быть, $x^2=x$ и задача не имеет решения.

[ruslanbadamhsin]

[quote="iifat в [url=http://dxdy.ru/post1662037.html#p1662037]стало быть, $x^2=x$ и задача не имеет решения.[/quote]
Стало быть, это другая логика и вопрос не имеет смысла.
Речь о функциях обычного возведения в степень по модулю k. Например, для k = 3 $x^2$ принимает значения 0, 1, 1 (ровно как и $x^4$.

[dgwuqtj]

ruslanbadamhsin в сообщении #1662011 писал(а):

12 кратно 3 и 4, но они все не подходят.

А что, для 4 эти функции попарно различные?

[ruslanbadamhsin]

dgwuqtj в сообщении #1662047 писал(а):

А что, для 4 эти функции попарно различные?

$x^2 = x^4$ при k = 4.

[svv]

ruslanbadamhsin
Вы можете сказать, что за задачник? Авторы, точное название книги.

[dgwuqtj]

ruslanbadamhsin в сообщении #1662115 писал(а):

$x^2 = x^4$ при k = 4.

Ну вот, поэтому отсюда про случай $k = 12$ ничего нельзя сказать.