Root of unity modulo n

From Wikipedia, the free encyclopedia
Jump to: navigation, search


In mathematics, namely ring theory, a k-th root of unity modulo n for positive integers k, n ≥ 2, is a solution x to the equation (or congruence) x^k \equiv 1 \pmod{n} . If k is the smallest such exponent for x, then x is called a primitive k-th root of unity modulo n.[1] See modular arithmetic for notation and terminology.

Do not confuse this with a primitive element modulo n, where the primitive element must generate all units of the residue class ring \mathbb{Z}/n\mathbb{Z} by exponentiation. That is, there are always roots and primitive roots of unity modulo n for n ≥ 2, but for some n there is no primitive element modulo n. Being a root or a primitive root modulo n always depends on the exponent k and the modulus n, whereas being a primitive element modulo n only depends on the modulus n — the exponent is automatically \varphi(n).

Roots of unity[edit]

Properties[edit]

  • If x is a k-th root of unity, then x is a unit (invertible) whose inverse is x^{k-1}. That is, x and n are coprime.
  • If x is a unit, then it is a (primitive) k-th root of unity modulo n, where k is the multiplicative order of x modulo n.
  • If x is a k-th root of unity and x-1 is not a zero divisor, then \sum_{j=0}^{k-1} x^j \equiv 0 \pmod{n}, because
(x-1)\cdot\sum_{j=0}^{k-1} x^j \equiv x^k-1 \equiv 0 \pmod{n}.

Number of k-th roots[edit]

For the lack of a widely accepted symbol, we denote the number of k-th roots of unity modulo n by f(n,k). It satisfies a number of properties:

Primitive roots of unity[edit]

Properties[edit]

  • The maximum possible radix exponent for primitive roots modulo n is \lambda(n), where λ denotes the Carmichael function.
  • A radix exponent for a primitive root of unity is a divisor of \lambda(n).
  • Every divisor k of \lambda(n) yields a primitive k-th root of unity. You can obtain one by choosing a \lambda(n)-th primitive root of unity (that must exist by definition of λ), named x and compute the power x^{\lambda(n)/k}.
  • If x is a primitive k-th root of unity and also a (not necessarily primitive) ℓ-th root of unity, then k is a divisor of ℓ. This is true, because Bézout's identity yields an integer linear combination of k and ℓ equal to \mathrm{gcd}(k,\ell). Since k is minimal, it must be k = \mathrm{gcd}(k,\ell) and \mathrm{gcd}(k,\ell) is a divisor of ℓ.

Number of primitive k-th roots[edit]

For the lack of a widely accepted symbol, we denote the number of primitive k-th roots of unity modulo n by g(n,k). It satisfies the following properties:

f = \bold{1} * g, i.e. f(n,k) = \sum_{d\mid k} g(n,d)
You can compute values of g recursively from f using this formula, which is equivalent to the Möbius inversion formula.

Testing whether x is a primitive k-th root of unity modulo n[edit]

By fast exponentiation you can check that x^k \equiv 1 \pmod{n}. If this is true, x is a k-th root of unity modulo n but not necessarily primitive. If it is not a primitive root, then there would be some divisor ℓ of k, with x^{\ell} \equiv 1 \pmod{n}. In order to exclude this possibility, one has only to check for a few ℓ's equal k divided by a prime. That is, what needs to be checked is:

\forall p \text{ prime dividing}\ k,\quad x^{k/p} \not\equiv 1 \pmod{n}.

Finding a primitive k-th root of unity modulo n[edit]

Among the primitive k-th roots of unity, the primitive \lambda(n)-th roots are most frequent. It is thus recommended to try some integers for being a primitive \lambda(n)-th root, what will succeed quickly. For a primitive \lambda(n)-th root x, the number x^{\lambda(n)/k} is a primitive k-th root of unity. If k does not divide \lambda(n), then there will be no k-th roots of unity, at all.

Finding multiple primitive k-th roots modulo n[edit]

Once you have a primitive k-th root of unity x, every power x^l is a k-th root of unity, but not necessarily a primitive one. The power x^l is a primitive k-th root of unity if and only if k and l are coprime. The proof is as follows: If x^l is not primitive, then there exists a divisor m of k with (x^l)^m \equiv 1 \pmod{n}, and since k and l are coprime, there exists an inverse l^{-1} of l modulo k. This yields 1 \equiv ((x^l)^m)^{l^{-l}} \equiv x^m \pmod{n}, which means that x is not a primitive k-th root of unity because there is the smaller exponent m.

That is, by exponentiating x one can obtain \varphi(k) different primitive k-th roots of unity, but these may not be all such roots. However, finding all of them is not so easy.

Finding an n with a primitive k-th root of unity modulo n[edit]

You may want to know, in what integer residue class rings you have a primitive k-th root of unity. You need it for instance if you want to compute a Discrete Fourier Transform (more precisely a Number theoretic transform) of a k-dimensional integer vector. In order to perform the inverse transform, you also need to divide by k, that is, k shall also be a unit modulo n.

A simple way to find such an n is to check for primitive k-th roots with respect to the moduli in the arithmetic progression k+1, 2k+1, 3k+1, \dots. All of these moduli are coprime to k and thus k is a unit. According to Dirichlet's theorem on arithmetic progressions there are infinitely many primes in the progression, and for a prime p it holds \lambda(p) = p-1. Thus if mk+1 is prime then \lambda(mk+1) = mk and thus you have primitive k-th roots of unity. But the test for primes is too strong, you may find other appropriate moduli.

Finding an n with multiple primitive roots of unity modulo n[edit]

If you want to have a modulus n such that there are primitive k_1-th, k_2-th, ..., k_m-th roots of unity modulo n, the following theorem reduces the problem to a simpler one:

For given n there are primitive k_1-th, ..., k_m-th roots of unity modulo n if and only if there is a primitive \mathrm{lcm}(k_1, ..., k_m)-th root of unity modulo n.
Proof

Backward direction: If there is a primitive \mathrm{lcm}(k_1, ..., k_m)-th root of unity modulo n called x, then x^{\mathrm{lcm}(k_1, \dots, k_m)/k_l} is a k_l-th root of unity modulo n.

Forward direction: If there are primitive k_1-th, ..., k_m-th roots of unity modulo n, then all exponents k_1, \dots, k_m are divisors of \lambda(n). This implies \mathrm{lcm}(k_1, \dots, k_m) \mid \lambda(n) and this in turn means there is a primitive \mathrm{lcm}(k_1, ..., k_m)-th root of unity modulo n.

See also[edit]

References[edit]

  1. ^ Finch, Stephen; Martin, Greg; Sebah, And Pascal. "Roots of unity and nullity modulo n". Proceedings of the American Mathematical Society (American Mathematical Society) 138 (8): 2729–2743. doi:10.1090/s0002-9939-10-10341-4. Retrieved 2011-02-20.