Root of unity modulo n

In mathematics, namely ring theory, a k-th root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n, that is, a solution x to the equation (or congruence) x k ≡ 1 ( mod n ) {displaystyle 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. See modular arithmetic for notation and terminology. In mathematics, namely ring theory, a k-th root of unity modulo n for positive integers k, n ≥ 2, is a root of unity in the ring of integers modulo n, that is, a solution x to the equation (or congruence) x k ≡ 1 ( mod n ) {displaystyle 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. See modular arithmetic for notation and terminology. Do not confuse this with a primitive root modulo n, which is a generator of the group of units of the ring of integers modulo n. The primitive roots modulo n are the primitive φ ( n ) {displaystyle varphi (n)} -roots of unity modulo n, where φ {displaystyle varphi } is Euler's totient function. For the lack of a widely accepted symbol, we denote the number of k-th roots of unity modulo n by f ( n , k ) {displaystyle f(n,k)} .It satisfies a number of properties: 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 ) {displaystyle g(n,k)} .It satisfies the following properties: By fast exponentiation you can check that x k ≡ 1 ( mod n ) {displaystyle 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 ℓ ≡ 1 ( mod n ) {displaystyle 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: Among the primitive k-th roots of unity, the primitive λ ( n ) {displaystyle lambda (n)} -th roots are most frequent.It is thus recommended to try some integers for being a primitive λ ( n ) {displaystyle lambda (n)} -th root, what will succeed quickly.For a primitive λ ( n ) {displaystyle lambda (n)} -th root x, the number x λ ( n ) / k {displaystyle x^{lambda (n)/k}} is a primitive k {displaystyle k} -th root of unity.If k does not divide λ ( n ) {displaystyle lambda (n)} , then there will be no k-th roots of unity, at all. Once you have a primitive k-th root of unity x, every power x l {displaystyle x^{l}} is a k {displaystyle k} -th root of unity, but not necessarily a primitive one. The power x l {displaystyle x^{l}} is a primitive k {displaystyle k} -th root of unity if and only if k {displaystyle k} and l {displaystyle l} are coprime. The proof is as follows: If x l {displaystyle x^{l}} is not primitive, then there exists a divisor m {displaystyle m} of k {displaystyle k} with ( x l ) m ≡ 1 ( mod n ) {displaystyle (x^{l})^{m}equiv 1{pmod {n}}} , and since k {displaystyle k} and l {displaystyle l} are coprime, there exists an inverse l − 1 {displaystyle l^{-1}} of l {displaystyle l} modulo k {displaystyle k} . This yields 1 ≡ ( ( x l ) m ) l − l ≡ x m ( mod n ) {displaystyle 1equiv ((x^{l})^{m})^{l^{-l}}equiv x^{m}{pmod {n}}} , which means that x {displaystyle x} is not a primitive k {displaystyle k} -th root of unity because there is the smaller exponent m {displaystyle m} . That is, by exponentiating x one can obtain φ ( k ) {displaystyle 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. 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 {displaystyle k} -dimensional integer vector. In order to perform the inverse transform, you also need to divide by k {displaystyle k} , that is, k shall also be a unit modulo n {displaystyle n} .