1 совпадает с 9 модом 8, поэтому 3 является нетривиальным квадратным корнем из 1 мод 8.
вы работаете не с отдельными числами, а с множествами эквивалентности. [m]n - это набор всех чисел x, такой, что x соответствует m mod n. Любое, что связано с любым элементом этого набора, является квадратным корнем из 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.
На практике, однако, мы можем сопоставить m с [m]n и обычно выбрать уникальный элемент, m' из [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