Какой остаток от p 12 ^ (p-1), когда p простое число?

Ответ:

Остаток равен #0# когда #п# либо #2# или же #3#и это равно #1# для всех других простых чисел.

Объяснение:

Прежде всего, эту проблему можно переформулировать как необходимость найти значение # 12 ^ (p-1) mod p # где #п# это простое число.

Для решения этой проблемы нужно знать теорему Эйлера. Теорема Эйлера утверждает, что #a ^ { varphi (n)} - = 1 mod n # для любых целых # A # а также # П # это взаимно (они не разделяют никаких факторов). Вам может быть интересно, что # varphi (n) # является. На самом деле это функция, известная как функция totient. Он определен равным количеству целых чисел # <= П # так что эти целые числа взаимно просты # П #, Имейте в виду, что число #1# считается взаимно простым для всех целых чисел.

Теперь, когда мы знаем теорему Эйлера, мы можем решить эту проблему.

Обратите внимание, что все простые числа, кроме #2# а также #3# взаимно просты с #12#, Давайте отложим 2 и 3 на потом и сосредоточимся на остальных простых числах. Поскольку эти другие простые числа взаимно просты с 12, мы можем применить к ним теорему Эйлера:

# 12 ^ { varphi (p)} - = 1 mod p #

поскольку #п# простое число, # Varphi (р) = р-1 #, Это имеет смысл, потому что каждое число, меньшее простого, будет взаимно простым.

Поэтому теперь у нас есть # 12 ^ {p-1} - = 1 мод p #

Вышеуказанное выражение может быть переведено на # 12 ^ {р-1} # деленное на #п# имеет остаток #1#.

Теперь нам просто нужно учесть #2# а также #3#, который, как вы сказали ранее, у обоих были остатки #0#.

Таким образом, в целом мы доказали, что # 12 ^ {р-1} # деленное на #п# где #п# простое число имеет остаток #0# когда р либо #2# или же #3# и имеет остаток #1# иначе.