# Looking for ways how to calculate $\Phi_n(i)$

$Φ_n(1)$ and $Φ_n(−1)$ for the cyclotomic polynomials are well-known.

I am now looking for $$Φ_n(i)$$ and/or $$Φ_n(−i)$$ with i the complex unit.

At this moments my endeavours result in intricate categorizing of values for $n$ e.g. as $4$, $2^k$, $4p$, $p^k$ with $p$ prime and considerations about the prime factors of an odd $n$ being e.g. $\equiv1\mod4$ or/and $\equiv3\mod4$.

• I think that using the formulas $\Phi_n(x)=\Phi_r(x^{n/r})$ (where $r$ is the product of all distinct prime divisors of $n$) and $\prod_{d\mid n}\Phi_d(x)=x^n-1$ one can determine both of these without much trouble. Did you try that at least to some extent? – Vladimir Dotsenko Sep 9 '14 at 10:08
• It would be interesting to see how this could be used on the case e.g. of an odd $n$ being a product of $5$ different primes where say $2$ are $\equiv1\mod4$ and $3$ are $\equiv3\mod4$. Then I cant imagine how to generalize to the case of a general squarefree prime factorization of an odd $n$. – Wolfgang Tintemann Sep 9 '14 at 12:05
• Let me quicky illustrate it for two primes. $\Phi_p(i)$ is $i$ for $p\equiv 3\pmod{4}$ and $1$ for $p\equiv1\pmod{4}$. $\Phi_1(i)=i-1$. Therefore, for $\Phi_{pq}(i)$ we have three possibilities. If both $p$ and $q$ are $1$ modulo $4$, we have $(i-1).1.1.\Phi_{pq}(i)=i^{pq}-1=i-1$, so $\Phi_{pq}(i)=1$. If both $p$ and $q$ are $3$ modulo $4$, we have $(i-1).i.i.\Phi_{pq}(i)=i^{pq}-1=i-1$, so $\Phi_{pq}(i)=-1$. Finally if $p$ and $q$ are different modulo $4$, then $(i-1).1.i.\Phi_{pq}(i)=i^{pq}-1=-i-1$, so $\Phi_{pq}(i)=1$ (since $(i-1).i=-i-1$). Is my plan clearer now? – Vladimir Dotsenko Sep 9 '14 at 12:42
• The recursive formula $\prod_{d|n}\Phi_d(x)=x^n-1$ can be solved explicitly by Möbius inversion: $\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}$. – Emil Jeřábek Sep 9 '14 at 12:56
• Thats perfect and I reasoned along the same lines though I work not using the results about cyclotomic polynomials directly but using another formula which i cant detail here. But now remains the problem how this way of solution could be made in the general e.g. odd squarefree $n$ case. For Information what the results of user Jack d'Auruzio are please look here math.stackexchange.com/questions/893968/… .But I dont see how he arrived at his result. – Wolfgang Tintemann Sep 9 '14 at 13:05

The question has already been answered by Vladimir Dotsenko, but as Wolfgang Tintemann is still interested in a solution using Möbius inversion, let me expand the comments I made above.

Since $\Phi_n(-i)=\overline{\Phi_n(i)}$, it is enough to deal with $i$. We are going to prove $$\Phi_n(i)=\begin{cases} i-1&n=1,\\ i+1&n=2,\\ 0&n=4,\\ p&n=4p^k,\\ i&n=p^k,\ p\equiv3\pod4,\text{ k odd, or}\\ &n=2p^k,\ p\equiv3\pod 4,\text{ k even,}\\ -i&n=p^k,\ p\equiv3\pod4,\text{ k even, or}\\ &n=2p^k,\ p\equiv3\pod 4,\text{ k odd,}\\ -1&n=p^kq^l\text{ or }n=2p^kq^l,\ p,q\equiv3\pod4,\\ 1&\text{if n is not of any of the forms above,} \end{cases}$$ where $p,q$ are prime, and $k,l\ge1$. The first three cases can be checked immediately, hence let me assume that $n\ne1,2,4$ below.

By Möbius inversion of the formula $x^n-1=\prod_{d|n}\Phi_d(x)$, we have $$\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}.$$ We cannot directly plug in $x=i$ as we might get $0/0$, but we can compute it as $\lim_{\epsilon\to0}\Phi_n(i+\epsilon)$.

Since $(i+\epsilon)^d=i^d+O(\epsilon)$ for $4\nmid d$, and $(i+\epsilon)^d=1-id\epsilon+O(\epsilon^2)$ for $4\mid d$, we see that $\Phi_n(i+\epsilon)$ is $$(1+O(\epsilon)) \prod_{\substack{d|n\\d\equiv1\pod4}}(i-1)^{\mu(\frac nd)} \prod_{\substack{d|n\\d\equiv3\pod4}}(-i-1)^{\mu(\frac nd)} \prod_{\substack{d|n\\d\equiv2\pod4}}(-2)^{\mu(\frac nd)} \prod_{\substack{d|n\\d\equiv0\pod4}}(-id\epsilon)^{\mu(\frac nd)}.$$ We can express $\pm i-1$ in terms of $\zeta_8=(1+i)/\sqrt2$ and reshuffle the terms to get $$\tag{*}(1+O(\epsilon)) (-\sqrt2)^{\sum_{d|n}\mu(\frac nd)} (\sqrt2)^{\sum_{2|d|n}\mu(\frac nd)} (2i\epsilon)^{\sum_{4|d|n}\mu(\frac nd)} \zeta_8^{s(n)} \prod_{4|d|n}(d/4)^{\mu(\frac nd)},$$ where $$s(n)=\sum_{\substack{d|n\\d\equiv3\pod4}}\mu(n/d) -\sum_{\substack{d|n\\d\equiv1\pod4}}\mu(n/d).$$ Since $n\ne1$, $\sum_{d|n}\mu(n/d)=0$. Moreover, $\sum_{2|d|n}\mu(n/d)=\sum_{d\mid\frac n2}\mu(\frac n2/d)=0$ for $n$ even, and trivially $\sum_{2|d|n}\mu(n/d)=0$ for $n$ odd; likewise for $4$. Thus the first four terms of $(*)$ disappear as $\epsilon\to0$. If $4\nmid n$, the last term is vacuously $1$. On the other hand, if $4\mid n$, we have $s(n)=0$: all the $\mu(n/d)$ summands vanish on account of $n/d$ being divisible by $4$. Thus we arrive at $$\tag{*{*}} \Phi_n(i)=\begin{cases} \zeta_8^{s(n)}&4\nmid n,\\ \prod_{d|m}d^{\mu(m/d)}&n=4m. \end{cases}$$ Assume first $4\mid n$. We can simplify $(*{*})$ further to $$\Phi_n(i)=m^{\sum_{d|m}\mu(m/d)}\prod_{d|m}(m/d)^{-\mu(m/d)} =\prod_{d|m}d^{-\mu(d)}.$$ If $m=p^k$ is a prime power, this gives immediately $\Phi_n(i)=p$. On the other hand, if $m=p_1^{k_1}\cdots p_r^{k_r}$ with $r\ge2$, we have $$\Phi_n(i)=\prod_{j=1}^rp_j^{\sum_{d|m_j}\mu(d)}=1,$$ where $m_j=m/p_j^{k_j}$.

Now assume $4\nmid n$, we need to compute $s(n)$ modulo $8$. Observe that if $n$ is odd, then $s(2n)=-s(n)$, hence $\Phi_{2n}(i)=\Phi_n(i)^{-1}$. It thus suffices to consider odd $n$.

If $n$ has a prime divisor $p\equiv1\pod4$, then each $d\mid n$ with $d\equiv3\pod4$ is paired with another one with opposite $\mu(n/d)$ by multiplying or dividing $d$ by $p$; likewise for $d\equiv1\pod4$. Thus in this case $s(n)=0$ and $\Phi_n(i)=1$.

Finally, assume that $n=p_1^{k_1}\cdots p_r^{k_r}$, where each $p_j\equiv3\pod4$. Let $t=\pm1$ be such that $n\equiv-t\pod4$. Then for every $I\subseteq\{1,\dots,r\}$, $d=n\prod_{i\in I}p_i^{-1}$ contributes $t(-1)^{|I|}\mu(n/d)=t$ to $s(n)$, hence $s(n)=t2^r$. Thus, $\Phi_n(i)=1$ if $r\ge3$, $\Phi_n(i)=-1$ if $r=2$, and $\Phi_n(i)=i^t=(-1)^{k_1+1}i$ if $r=1$.

• Thank you Emil Jeřábek that you gave this solution and the nice theorem-like formulation of the different cases. I think I need some time to try to understand it. Now I have the problem to decide which answer I should mark as "accepted". I at least accept both. – Wolfgang Tintemann Sep 11 '14 at 14:15
• I simply want to remark that in the formula (**) the second line is equal to $\Phi_m(1)$. Also I think e. g. in the case that $n$ has a prime divisor $p\equiv1\mod4$ we have $s(n)=\phi(n)$ with the $\phi$-function of Euler. I am still working on a proof that $s(n)=\phi(n)+c_n$ with a constant $c_n$ is being valid in other cases: e.g. if each $p_j\equiv3\mod4$ then $c_n=(-2)^r$. – Wolfgang Tintemann Sep 12 '14 at 13:33
• Yes, $\Phi_{4m}(i)=\Phi_m(1)$; I preferred to give a direct derivation using properties of the Möbius function to keep in line with the rest of the proof for illustrative reasons, as the other way is explained in Vladimir Dotsenko’s answer. I don’t quite understand the rest of your comment. $s(n)=0$ if $4\mid n$ or if $n$ has a prime divisor $p\equiv1\pod4$, otherwise it is $\pm$ a power of two, namely $s(n)=(-1)^{1+\nu_2(n)}\left(\frac{-1}{n'}\right)2^{\omega(n')}$, where $n'$ is the odd part of $n$. $\phi(n)$ is usually nowhere near a power of $2$. – Emil Jeřábek Sep 12 '14 at 14:21
• Yes you are right. I wrote nonsense. I only got for now in the case of squarefree $n=p_1p_2p_3$ if one factor is $\equiv1\mod4$ the equation $$(1-i)^{\phi(n)}\Phi_n(i)=(-1)^{\frac{\phi(n)}{4}}2^{\frac{\phi(n)}{2}}$$ which means $\Phi_n(1)=1$ and if all factors are $\equiv3\mod4$ the equation $(1-i)^{\phi(n)}\Phi_n(i)=(-1)^{\frac{\phi(n)+(-2)^3}{4}}2^{\frac{\phi(n)}{2}}$. I still work on the general proof via my method of calculation. I use the for me interesting property that if one evaluates the polynomial $(x-x_1)(x-x_2)(x-x_3)$ with $x_i=p_i\mod4$ on $x=1$ then one gets $0$ or $(-2)^3$. – Wolfgang Tintemann Sep 12 '14 at 15:07

Let me try to summarize what I said in the comment to your question and what I implicitly used in what did not fit in the comment. As you will instantly see, the answer is lengthy because of high-school level exercises you have to do along the way, not because some important ideas were missing.

I suggest to use the following properties of cyclotomic polynomials:

1. for $p$ prime, $k>1$, we have $\Phi_{mp^k}(x)=\Phi_{mp}(x^{p^{k-1}})$;
2. for $p$ prime and $m$ coprime with $p$, we have $\Phi_{mp}(x)=\frac{\Phi_m(x^p)}{\Phi_m(x)}$;
3. for odd $m>1$ we have $\Phi_{2m}(x)=\Phi_m(-x)$.

The first of these, interpreted as saying that a primitive $mp^k$-th root of unity raised to the power $p^{k-1}$ is a primitive $mp$-th root of unity, is easy to understand directly, as is the second one that effectively says that numbers that become primitive $m$-th roots of unity once raised to the power $p$ are either primitive $m$-th roots of unity themselves of primitive $mp$-th roots of unity. The third property says that negatives of $m$-th roots of unity are $2m$-th roots of unity.

(Iterating the first property, we easily obtain the formula $\Phi_n(x)=\Phi_{r}(x^{n/r})$ where $r$ is the product of all distinct prime divisors of $n$, which I mentioned in my comment).

Now, let us iterate these.

First let us suppose that $n$ is odd.

Let $p$ be a prime divisor of $n$ that is congruent to $1$ modulo $4$, and let $n=p^km$ where $\gcd(m,p)=1$.

A. For $k=1$ we have $\Phi_{n}(x)=\frac{\Phi_m(x^p)}{\Phi_m(x)}$, so $\Phi_n(i)=\Phi_n(-i)=1$. (Since under our assumption on $p$ we have $i^p=i$).

B. For $k>1$ we have $\Phi_n(x)=\Phi_{mp}(x^{p^{k-1}})$, so $\Phi_n(i)=\Phi_{mp}(i)=\Phi_n(-i)=\Phi_{mp}(-i)=1$.

Let $p$ be a prime divisor of $n$ that is congruent to $3$ modulo $4$, and let $n=p^km$ where $\gcd(m,p)=1$.

C. For $k=1$ we have $\Phi_{n}(x)=\frac{\Phi_m(x^p)}{\Phi_m(x)}$, so $\Phi_n(i)=\frac{\Phi_m(-i)}{\Phi_m(i)}$ and $\Phi_n(-i)=\frac{\Phi_m(i)}{\Phi_m(-i)}$. (Since under our assumption on $p$ we have $i^p=i^3=-i$).

D. For $k>1$ we have $\Phi_n(x)=\Phi_{mp}(x^{p^{k-1}})$, so when $k$ is even we have $\Phi_n(i)=\Phi_{mp}(-i)=\frac{\Phi_m(i)}{\Phi_m(-i)}$ and $\Phi_n(-i)=\Phi_{mp}(i)=\frac{\Phi_m(-i)}{\Phi_m(i)}$, and when $k$ is odd we have $\Phi_n(i)=\Phi_{mp}(i)=\frac{\Phi_m(-i)}{\Phi_m(i)}$ and $\Phi_n(-i)=\Phi_{mp}(-i)=\frac{\Phi_m(i)}{\Phi_m(-i)}$.

Now let us handle the case of even $n$. Let $n=2^km$, where $m>1$ is odd.

E. For $k=1$ we have $\Phi_{n}(x)=\Phi_m(-x)$, so $\Phi_n(i)=\Phi_m(-i)$ and $\Phi_n(-i)=\Phi_m(i)$.

F. For $k=2$ we have $\Phi_{n}(x)=\Phi_{2m}(x^2)=\Phi_m(-x^2)$, so $\Phi_{n}(i)=\Phi_{n}(-i)=\Phi_m(1)$.

G. For $k>2$ we have $\Phi_{n}(x)=\Phi_{2m}(x^{2^{k-1}})$, so $\Phi_{n}(i)=\Phi_{n}(-i)=\Phi_{2m}(1)$, which is equal to $1$ for $m>1$ and to $2$ for $m=1$.

Finally, if $n=2^k$, we see that $\Phi_n(x)=x^{2^{k-1}}+1$, so $\Phi_n(i)$ is equal to $i+1$ for $k=1$, to $0$ for $k=2$, and to $2$ for $k>2$. Similarly, $\Phi_n(-i)$ is equal to $-i+1$ for $k=1$, to $0$ for $k=2$, and to $2$ for $k>2$.

It remains to use simple induction to give the complete answer.

If $n=1$, then $\Phi_n(i)=i-1$ and $\Phi_n(-i)=-i-1$.

If $n$ is odd and has a prime divisor congruent to $1$ modulo $4$, then $\Phi_n(i)=\Phi_n(-i)=1$, this is established above.

If $n$ is odd and has just one prime divisor which is, in addition, congruent to $3$ modulo $4$, so that $n=p^k$, then $\Phi_n(i)=\frac{\Phi_1(i^{p^k})}{\Phi_1(i^{p^{k-1}})}$ which is equal to $\frac{\Phi_1(i)}{\Phi_1(-i)}=-i$ for even $k$ and to to $\frac{\Phi_1(-i)}{\Phi_1(i)}=i$ for odd $k$. Similarly, $\Phi_n(-i)$ is equal to $i$ for even $k$ and to $-i$ for odd $k$.

If $n$ is odd and has two distinct prime divisors $p$ and $q$, both congruent to $3$ modulo $4$, so that $n=p^aq^b$, then $\Phi_n(i)=\frac{\Phi_{q^b}(i^{p^a})}{\Phi_{q^b}(i^{p^{a-1}})}$, and by recalling from the previous case that $\Phi_{q^b}(i)=-\Phi_{q^b}(-i)$, we deduce that $\Phi_n(i)=-1$. Similarly, $\Phi_n(-i)=-1$.

If $n$ is odd and has at least three distinct prime divisors, all congruent to $3$ modulo $4$, so that $n=p^aq^bm$ with $m>1$, then $\Phi_n(i)=\frac{\Phi_{q^bm}(i^{p^a})}{\Phi_{q^bm}(i^{p^{a-1}})}$, and by induction and the previous case (saying that $\Phi_{p^aq^b}(i)=\Phi_{p^aq^b}(-i)$, we deduce that $\Phi_n(i)=1$. Similarly, $\Phi_n(-i)=1$.

If $n$ is even and is divisible by $2^k$ with $k\ge 3$, then $\Phi_n(i)=\Phi_n(-i)=1$, this is established above.

If $n$ is even, and $n=4m$ with odd $m>1$, then $\Phi_{n}(i)=\Phi_{n}(-i)=\Phi_m(1)$, as established above. The latter is equal to $1$ if $m$ is not a prime power, and is equal to $p$ if $m=p^k$, where $p$ is a prime.

If $n$ is even, and $n=2m$ with odd $m>1$, then $\Phi_n(i)=\Phi_m(-i)$ and $\Phi_n(-i)=\Phi_m(i)$, and the values $\Phi_m(i)$, $\Phi_m(-i)$ are established above.

Finally, we already established that if $n=2^k$, then $\Phi_n(i)$ is equal to $i+1$ for $k=1$, to $0$ for $k=2$, and to $2$ for $k>2$. Similarly, $\Phi_n(-i)$ is equal to $-i+1$ for $k=1$, to $0$ for $k=2$, and to $2$ for $k>2$.

• I am enthusiatic about this very elaborate solution using the often published theorems on cyclotomic polynomials. I think this should be cited in textbooks about elementary number theory. Sorry that I am not allowed to vote up this. – Wolfgang Tintemann Sep 10 '14 at 11:43
• I hope that Emil Jeřábek will publish his method too as my calculations also use a Möbius inversion style formula like/similar to the classical one he uses. – Wolfgang Tintemann Sep 10 '14 at 11:46
• @WolfgangTintemann If you find the answer satisfactory you can always accept it: meta.stackexchange.com/questions/5234/… – Vladimir Dotsenko Sep 10 '14 at 12:21
• I would accept it of course if my answer is not closed if I do it. But I am hoping to get some more answers using different approaches especially the one using the Möbius Inversion formula. I hope also that I can give an answer about the special case of $n$ odd and squarefree where the sum of divisors function $\sigma(n)$ plays a role. – Wolfgang Tintemann Sep 10 '14 at 14:55
• When I made a detailed check I came about this for instance: If $n$ is even, and $n=4m$ with odd $m>1$ , then $Φ_n(i)=Φ_n(−i)=Φ_m(1)$ , as established above. The latter is equal to $1$ if $n$ is not a prime power, and is equal to $p$ if $n=p^k$ , where $p$ is a prime. I suppose in the last sentence it should say $m$ instead of $n$ ? – Wolfgang Tintemann Sep 10 '14 at 15:48