Ответ 1
1 соответствует конгруэнту 9 mod 8, поэтому 3 - нетривиальный квадратный корень из 1 mod 8.
то, с чем вы работаете, - это не отдельные числа, а множества эквивалентности. [m]n
- это set всех чисел x
, для которых x
соответствует m
mod n
. Любая вещь, которая sqaures для любого элемента этого набора, является квадратным корнем из m
по модулю n
.
при любом n
, мы имеем множество целых чисел по модулю n, которое мы можем написать как Zn
. это множество (множеств) [1]n
, [2]n
,..., [n]n
. Каждое целое число лежит в одном и только одном из этих множеств. мы можем определить сложение и умножение на этом множестве на [a]n + [b]n = [a + b]n
и аналогично для умножения. Таким образом, квадратный корень из [1]n
является (n элементом) [b]n
таким, что [b*b]n = [1]n
.
На практике, однако, мы можем conflate m
с [m]n
и обычно выбираем уникальный элемент m'
of [m]n
такой, что 0 <= m' < n
как наш "представительский" элемент: это то, о чем мы обычно думаем как m mod n
. но важно помнить, что мы "злоупотребляем обозначениями", как говорят математики.
здесь некоторый (неидиоматический) код python, поскольку у меня нет схемы-интерпретатора ATM:
>>> def roots_of_unity(n):
... roots = []
... for i in range(n):
... if i**2 % n == 1:
... roots.append(i)
... return roots
...
>>> roots_of_unity(4)
[1, 3]
>>> roots_of_unity(8)
[1, 3, 5, 7]
>>> roots_of_unity(9)
[1, 8]
Итак, в частности (смотря на последний пример), 17 является корнем из единицы по модулю 9. Действительно, 17 ^ 2 = 289 и 289% 9 = 1. Возвращаясь к нашим предыдущим обозначениям [8]9 = [17]9
и ([17]9)^2 = [1]9