You do not have permission to edit this page, for the following reasons:

This IP address has been blocked from editing Wikipedia.
This does not affect your ability to read Wikipedia pages.
Most people who see this message have done nothing wrong. Some kinds of blocks restrict editing from specific service providers or telecom companies in response to recent abuse or vandalism, and can sometimes affect other users who are unrelated to that abuse. Review the information below for assistance if you do not believe that you have done anything wrong.

The IP address or range 3.85.0.0/16 has been blocked (disabled) by ‪ST47‬ for the following reason(s):

The IP address that you are currently using has been blocked because it is believed to be a web host provider. To prevent abuse, web hosts may be blocked from editing Wikipedia.
You will not be able to edit Wikipedia using a web host provider because it hides your IP address, much like a proxy or VPN.
We recommend that you attempt to use another connection to edit. For example, if you use a proxy or VPN to connect to the internet, turn it off when editing Wikipedia. If you edit using a mobile connection, try using a Wi-Fi connection, and vice versa. If you are using a corporate internet connection, switch to a different Wi-Fi network. If you have a Wikipedia account, please log in.
If you do not have any other way to edit Wikipedia, you will need to request an IP block exemption.

How to appeal if you are confident that your connection does not use a web host's IP address:
If you are confident that you are not using a web host, you may appeal this block by adding the following text on your talk page: ((unblock|reason=Caught by a web host block but this host or IP is not a web host. My IP address is _______. Place any further information here. ~~~~)). You must fill in the blank with your IP address for this block to be investigated. Your IP address can be determined here. Alternatively, if you wish to keep your IP address private you can use the unblock ticket request system. There are several reasons you might be editing using the IP address of a web host (such as if you are using VPN software or a business network); please use this method of appeal only if you think your IP address is in fact not a web host.

Administrators: The IP block exemption user right should only be applied to allow users to edit using web host in exceptional circumstances, and they should usually be directed to the functionaries team via email. If you intend to give the IPBE user right, a CheckUser needs to take a look at the account. This can be requested most easily at SPI Quick Checkuser Requests. Unblocking an IP or IP range with this template is highly discouraged without at least contacting the blocking administrator.

This block will expire on 21:48, 22 February 2026.

Even when blocked, you will usually still be able to edit your user talk page, as well as email administrators and other editors.

For information on how to proceed, please read the FAQ for blocked users and the guideline on block appeals. The guide to appealing blocks may also be helpful.

Other useful links: Blocking policy · Help:I have been blocked
Your IP address is in a range that has been blocked on all Wikimedia Foundation wikis. The block was made by ‪Jon Kolbert‬. The reason given is Open proxy/Webhost: See the help page if you are affected .
- Start of block: 05:35, 21 February 2024
- Expiry of block: 05:35, 21 February 2029
Your current IP address is 3.85.235.113. The blocked range is 3.85.0.0/16. Please include all above details in any queries you make. If you believe you were blocked by mistake, you can find additional information and instructions in the No open proxies global policy. Otherwise, to discuss the block please post a request for review on Meta-Wiki. You could also send an email to the stewards VRT queue at stewards@wikimedia.org including all above details.

You can view and copy the source of this page:

((DISPLAYTITLE:Root of unity modulo ''n''))
((cleanup|reason= Lack of context, lack of explicit examples, lack of explanation of the main differences with [[Root of unity]] and ((slink|Finite field|Roots of unity)).|date=February 2023))
In [[number theory]], a '''''k''th root of unity modulo ''n''''' for positive [[integer]]s ''k'', ''n''&nbsp;≥&nbsp;2,  is a [[root of unity]] in the ring of [[integers modulo n|integers modulo ''n'']]; that is, a solution ''x'' to the [[equation]] (or ''congruence'') <math>x^k \equiv 1 \pmod{n}</math>.  If ''k'' is the smallest such exponent for ''x'', then ''x'' is called a '''primitive ''k''th root of unity modulo ''n'''''.<ref>
((Cite journal
  | last1 = Finch
  | first1 = Stephen
  | last2 = Martin
  | first2 = Greg
  | last3 = Sebah
  | first3 = Pascal
  | title = Roots of unity and nullity modulo ''n''
  | journal = [[Proceedings of the American Mathematical Society]]
  | volume = 138
  | issue = 8
  | pages = 2729–2743
  | url = http://www.math.ubc.ca/~gerg/papers/downloads/RUNM.pdf
  | accessdate = 2011-02-20
  | doi=10.1090/s0002-9939-10-10341-4| year = 2010
  | doi-access = free
  ))
</ref> See [[modular arithmetic]] for notation and terminology.

The roots of unity modulo ((mvar|n)) are exactly the integers that are [[coprime]] with ((mvar|n)). In fact, these integers are roots of unity modulo ((mvar|n)) by [[Euler's theorem]], and the other integers cannot be roots of unity modulo ((mvar|n)), because they are [[zero divisor]]s modulo ((mvar|n)).

A [[primitive root modulo n|primitive root modulo ((mvar|n))]], is a generator of the group of [[Unit (ring theory)|units]] of the ring of integers modulo ((mvar|n)). There exist primitive roots modulo ((mvar|n)) if and only if <math>\lambda(n)=\varphi(n),</math> where <math>\lambda</math> and <math>\varphi</math> are respectively the [[Carmichael function]] and [[Euler's totient function]].

A root of unity modulo ((mvar|n)) is a primitive ((mvar|k))th root of unity  modulo ((mvar|n)) for some divisor ((mvar|k)) of <math>\lambda(n),</math> and, conversely, there are primitive ((mvar|k))th roots of unity modulo ((mvar|n)) if and only if ((mvar|k)) is a divisor of <math>\lambda(n).</math>

== Roots of unity ==

=== Properties ===
* If ''x'' is a ''k''th root of unity modulo ''n'', then ''x'' is a unit (invertible) whose inverse is <math>x^{k-1}</math>. 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 <math>x-1</math> is not a [[zero divisor]], then <math>\sum_{j=0}^{k-1} x^j \equiv 0 \pmod{n}</math>, because
:: <math>(x-1)\cdot\sum_{j=0}^{k-1} x^j \equiv x^k-1 \equiv 0 \pmod{n}.</math>

=== Number of ''k''th roots ===
For the lack of a widely accepted symbol, we denote the number of ''k''th roots of unity modulo ''n'' by <math>f(n,k)</math>.
It satisfies a number of properties:

* <math>f(n,1) = 1</math> for <math>n\ge2</math>
* <math>f(n,\lambda(n)) = \varphi(n)</math> where &lambda; denotes the [[Carmichael function]] and <math>\varphi</math> denotes [[Euler's totient function]]
* <math>n \mapsto f(n,k)</math> is a [[multiplicative function]]
* <math>k\mid\ell \implies f(n,k)\mid f(n,\ell)</math> where the bar denotes [[divisibility]]
* <math>f(n,\operatorname{lcm}(a,b)) = \operatorname{lcm}(f(n,a),f(n,b))</math> where <math>\operatorname{lcm}</math> denotes the [[least common multiple]]
* For [[Prime number|prime]] <math>p</math>, <math>\forall i\in\mathbb{N}\ \exists j\in\mathbb{N}\ f(n,p^i) = p^j</math>. The precise mapping from <math>i</math> to <math>j</math> is not known. If it were known, then together with the previous law it would yield a way to evaluate <math>f</math> quickly.

=== Examples ===
Let <math> n = 7 </math> and <math> k = 3 </math>. In this case, there are three cube roots of unity (1, 2, and 4). When <math> n = 11 </math> however, there is only one cube root of unity, the unit 1 itself. This behavior is quite different from the field of complex numbers where every nonzero number has ''k'' ''k''th roots.

== Primitive roots of unity ==

=== Properties ===
* The maximum possible radix exponent for primitive roots modulo <math>n</math> is <math>\lambda(n)</math>, where &lambda; denotes the [[Carmichael function]].
* A radix exponent for a primitive root of unity is a [[divisor]] of <math>\lambda(n)</math>.
* Every divisor <math>k</math> of <math>\lambda(n)</math> yields a primitive <math>k</math>th root of unity. One can obtain such a root by choosing a <math>\lambda(n)</math>th primitive root of unity (that must exist by definition of &lambda;), named <math>x</math> and compute the power <math>x^{\lambda(n)/k}</math>.
* 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 <math>\gcd(k,\ell)</math>. Since ''k'' is minimal, it must be <math>k = \gcd(k,\ell)</math> and <math>\gcd(k,\ell)</math> is a divisor of&nbsp;''ℓ''.
<!--
* If <math>x</math> is a primitive <math>k</math>th root of unity and for another exponent <math>l</math> it holds <math>x^l \equiv 1 \pmod{n}</math>, then <math>k</math> is a divisor of <math>l</math>.
-->

=== Number of primitive ''k''th roots ===
For the lack of a widely accepted symbol, we denote the number of primitive ''k''th roots of unity modulo ''n'' by <math>g(n,k)</math>.
It satisfies the following properties:

* <math>g(n,k) = \begin{cases} >0 &\text{if } k\mid\lambda(n), \\ 0 & \text{otherwise}. \end{cases}</math>
* Consequently the function <math>k \mapsto g(n,k)</math> has <math>d(\lambda(n))</math> values different from zero, where <math>d</math> computes the [[number of divisors]].
* <math>g(n,1) = 1</math>
* <math>g(4,2) = 1</math>
* <math>g(2^n,2) = 3</math> for <math>n \ge 3</math>, since -1 is always a [[square root]] of 1.
* <math>g(2^n,2^k) = 2^k</math> for <math>k \in [2,n-1)</math>
* <math>g(n,2) = 1</math> for <math>n \ge 3</math> and <math>n</math> in ((OEIS|A033948))
* <math>\sum_{k\in\mathbb{N)) g(n,k) = f(n,\lambda(n)) = \varphi(n)</math> with <math>\varphi</math> being [[Euler's totient function]]
* The connection between <math>f</math> and <math>g</math> can be written in an elegant way using a [[Dirichlet convolution]]:
:: <math>f = \mathbf{1} * g</math>, i.e. <math>f(n,k) = \sum_{d\mid k} g(n,d)</math>
: One can compute values of <math>g</math> recursively from <math>f</math> 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'' ===
By [[Exponentiation by squaring|fast exponentiation]], one can check that <math>x^k \equiv 1 \pmod{n}</math>. 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 <math>x^{\ell} \equiv 1 \pmod{n}</math>. 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:

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

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

=== Finding multiple primitive ''k''th roots modulo ''n'' ===
Once a primitive ''k''th root of unity ''x'' is obtained, every power <math>x^\ell</math> is a <math>k</math>th root of unity, but not necessarily a primitive one. The power <math>x^\ell</math> is a primitive <math>k</math>th root of unity if and only if <math>k</math> and <math>\ell</math> are [[coprime]]. The proof is as follows: If <math>x^\ell</math> is not primitive, then there exists a divisor <math>m</math> of <math>k</math> with <math>(x^\ell)^m \equiv 1 \pmod n</math>, and since <math>k</math> and <math>\ell</math> are coprime, there exists integers <math>a,b</math> such that <math>ak+b\ell=1</math>. This yields 

<math>x^m\equiv (x^m)^{ak+b\ell}\equiv (x^k)^{ma} ((x^{\ell})^m)^b \equiv 1 \pmod n </math>,

which means that <math>x</math> is not a primitive <math>k</math>th root of unity because there is the smaller exponent <math>m</math>.

That is, by exponentiating ''x'' one can obtain <math>\varphi(k)</math> 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'' ===
In what integer [[residue class ring]]s does a primitive ''k''th root of unity exist? It can be used to compute a [[discrete Fourier transform]] (more precisely a [[number theoretic transform]]) of a <math>k</math>-dimensional integer [[Vector (mathematics and physics)|vector]]. In order to perform the inverse transform, divide by <math>k</math>; that is, ''k'' is also a unit modulo <math>n.</math>

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]] <math>k+1, 2k+1, 3k+1, \dots</math> 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 <math>p</math>, it holds <math>\lambda(p) = p-1</math>. Thus if <math>mk+1</math> is prime, then <math>\lambda(mk+1) = mk</math>, and thus there are primitive ''k''th roots of unity. But the test for primes is too strong, and there may be other appropriate moduli.

=== Finding an ''n'' with multiple primitive roots of unity modulo ''n'' ===
To find a modulus <math>n</math> such that there are primitive <math>k_1\text{th}, k_2\text{th},\ldots,k_m\text{th}</math> roots of unity modulo <math>n</math>, the following theorem reduces the problem to a simpler one:

: For given <math>n</math> there are primitive <math>k_1\text{th}, \ldots, k_m\text{th}</math> roots of unity modulo <math>n</math> if and only if there is a primitive <math>\operatorname{lcm}(k_1, \ldots, k_m)</math>th root of unity modulo&nbsp;''n''.

; Proof

Backward direction:
If there is a primitive <math>\operatorname{lcm}(k_1, \ldots, k_m)</math>th root of unity modulo <math>n</math> called <math>x</math>, then <math>x^{\operatorname{lcm}(k_1, \ldots, k_m)/k_l}</math> is a <math>k_l</math>th root of unity modulo <math>n</math>.

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

== References ==
((reflist))

[[Category:Modular arithmetic]]

Pages transcluded onto the current version of this page (help):

Root of unity modulo n (edit)
Template:Ambox (view source) (template editor protected)
Template:Category handler (view source) (protected)
Template:Cite journal (view source) (protected)
Template:Cleanup (view source) (template editor protected)
Template:DMC (view source) (template editor protected)
Template:DMCA (view source) (template editor protected)
Template:Dated maintenance category (view source) (template editor protected)
Template:Dated maintenance category (articles) (view source) (template editor protected)
Template:FULLROOTPAGENAME (view source) (template editor protected)
Template:Main other (view source) (protected)
Template:Mvar (view source) (template editor protected)
Template:Ns has subpages (view source) (protected)
Template:OEIS (view source) (semi-protected)
Template:Reflist (view source) (protected)
Template:Reflist/styles.css (view source) (protected)
Template:SUBJECTSPACE formatted (view source) (template editor protected)
Template:Section link (view source) (template editor protected)
Template:Slink (view source) (extended confirmed protected)
Template:Terminate sentence (view source) (template editor protected)
Module:Arguments (view source) (protected)
Module:Category handler (view source) (protected)
Module:Category handler/blacklist (view source) (protected)
Module:Category handler/config (view source) (protected)
Module:Category handler/data (view source) (protected)
Module:Category handler/shared (view source) (protected)
Module:Check for unknown parameters (view source) (protected)
Module:Citation/CS1 (view source) (protected)
Module:Citation/CS1/COinS (view source) (protected)
Module:Citation/CS1/Configuration (view source) (protected)
Module:Citation/CS1/Date validation (view source) (protected)
Module:Citation/CS1/Identifiers (view source) (protected)
Module:Citation/CS1/Utilities (view source) (protected)
Module:Citation/CS1/Whitelist (view source) (protected)
Module:Citation/CS1/styles.css (view source) (protected)
Module:Message box (view source) (protected)
Module:Message box/ambox.css (view source) (protected)
Module:Message box/configuration (view source) (protected)
Module:Namespace detect/config (view source) (protected)
Module:Namespace detect/data (view source) (protected)
Module:Ns has subpages (view source) (protected)
Module:Section link (view source) (template editor protected)
Module:Text (view source) (template editor protected)
Module:Unsubst (view source) (protected)
Module:Yesno (view source) (protected)

Return to Root of unity modulo n.

Retrieved from "https://en.wikipedia.org/wiki/Root_of_unity_modulo_n"