For which $n$ does $p_n(x)=\sum\limits_{{k=1,(k,n)=1}}^n o(k) x^k $ have exactly two real roots? Let $n\in\mathbb{N}$ be fixed and denote by $o(k)$ the multiplicative order of $k$ modulo $n$. Define $$p_n(x)=\sum_{\substack{k=1 \\ (k,n)=1}}^n o(k) x^k ;$$here the sum is taken over $k$ that are coprime to $n$, so $o(k)$ is well-defined. Here are two simple observations:

*

*If $n$ is even, $p_n(x)$ is odd. Further, in this case it only has one real root.

*If $n$ is odd, aside from $n=1$ it seems that $n$ has an even number of real roots. Here is a picture of the number of roots for $1\le n \le 1000$ and $n$ odd.


I checked OEIS and it didn't return any matches. Perhaps this problem is very difficult, as I don't know how easy it is to compute $o(k)$ for arbitrary $n$. If we denote $R(n)$ as the number of real roots of $p_n(x)$ for odd $n$, here are some questions I think are worth pursuing about $R(n$):

*

*Is there an estimate or asymptotic for $R(n)$? Is there an upper bound for $R(n)$?

*When does $R(n)=2$? For $1\le n\le 1000$, this occured when $n=\{3, 5, 7, 11, 31, 89, 127, 257, 331, 635\}$; OEIS didn't recognize this sequence either.

*As a follow-up, does $R(n)=2$ infinitely often?

 A: Decomposition of $p_n$
Let $n$ be odd. Then we have
$$
(n,2k)=1 \wedge 2k<n  \Leftrightarrow (n,k)=1 \wedge k<n/2. 
$$
Thus, the terms with even exponents can be written as
$$
\sum_{\ell<\frac n2} o(2\ell) x^{2\ell}.
$$
The remaining odd numbers can be written as $n-2\ell$. Thus, we can write $p_n$ as
$$
p_n(x)=\sum_{\ell<\frac n2} o(2\ell) x^{2\ell} + \sum_{\ell<\frac n2} o(-2\ell) x^{n-2\ell} \ \ \ (1)
$$
so that the first sum gives even exponents, the second sum gives odd exponents.
Obviously, there are no positive real roots. As observed in comments, $x=0$ is a real root. Aside from $x=0$, all real roots must be negative. Then $-x\leq 0$ is a real root if and only if the following holds.
$$
\sum_{\ell<\frac n2} o(2\ell) x^{2\ell} = \sum_{\ell < \frac n2} o(-2\ell) x^{n-2\ell}. \ \ \ (2)
$$
For any $k$ with $(n,k)=1$, there is a relation between $o(k)$ and $o(-k)$.
Explicitly, this is
$$
o(-k)=\begin{cases} \frac{o(k)}2 &\mbox{ if }o(k) \mbox{ is even and } \frac{o(k)}2 \mbox{ is odd}\\
o(k) &\mbox{ if } o(k) \mbox{ is even and }\frac{o(k)}2 \mbox{ is even}\\
2o(k) &\mbox{ if } o(k) \mbox{ is odd.}
\end{cases} \ \ \ (3)
$$
This shows that we only need to compute $o(k)$ when $k<\frac n2$. Then $o(-k)$ is obtained as above. This might help reducing the computing time.
An upper bound of $R(n)$
By Descartes' rule of signs, we have
$$
R(n)\leq \phi(n).
$$
Zero-free intervals
Let $\lambda(n)$ be the exponent of the group $(\mathbb{Z}/n\mathbb{Z})^*$ (Carmichael's function).
The LHS of (2) is $2x^{n-1} + \sum_{2\ell<n-1} o(2\ell)x^{2\ell}$, the RHS of (2) is $x+\sum_{2\ell<n-1}o(-2\ell)x^{n-2\ell}$.
First, we use $o(2\ell)\geq 0$ on LHS of (2), and $o(-2\ell)\leq \lambda(n)$ on RHS of (2). By the geometric series partial sum formula,
$$
x + \lambda(n) \frac{x^3-x^n}{1-x^2} \geq \text{RHS} .
$$
On the other hand,
$$
\text{LHS}\geq 2x^{n-1}.
$$
After some manipulation, we have $\lambda(n) x^n + 2x^{n-1} < 2x^{n+1} + x + (\lambda(n)-1) x^3$ when $x \geq \tau=\frac{\lambda(n)}4+\sqrt{1+\frac{\lambda(n)^2}{16}}$. This gives
$$
\text{LHS}\geq 2x^{n-1} > x + \lambda(n) \frac{x^3-x^n}{1-x^2} \geq \text{RHS}.
$$
Thus, there is no real root of (2) when $x\geq \tau$.
Next, we use $o(2\ell)\leq \lambda(n)$ on LHS of (2), and $o(-2\ell)\geq 0$ on RHS of (2). By the geometric series partial sum formula,
$$
\text{LHS}\leq 2x^{n-1} +\lambda(n) \frac{x^2-x^{n-1}}{1-x^2}.
$$
On the other hand,
$$
\text{RHS}\geq x.
$$
After some manipulation, we have $\lambda(n) x^2  + x^3 < 2x^{n+1} + (\lambda(n)-2)x^{n-1} + x$ when $0<x\leq \mu=-\frac{\lambda(n)}2+\sqrt{1+\frac{\lambda(n)^2}4}$.
This gives
$$
\text{LHS}\leq 2x^{n-1} +\lambda(n) \frac{x^2-x^{n-1}}{1-x^2}<x\leq \text{RHS}.
$$
Thus, there is no real root of (2) when $0<x\leq \mu$.
Hence, the equation (1) does not have any real root when
$$
x\in \left(-\infty, -\left(\frac{\lambda(n)}4+\sqrt{1+\frac{\lambda(n)^2}{16}}\right)\right] \cup \left[-\left(-\frac{\lambda(n)}2+\sqrt{1+\frac{\lambda(n)^2}4}\right), 0\right).
$$
By Intermediate Value Theorem, there is at least one real root of (2) in the interval $(\mu,\tau)$. Therefore, there is at least one real root of (1) in the interval $(-\tau,-\mu)$ for any odd $n$.
Fermat prime case
Let $n=2^{2^m}+1$ be Fermat prime. Then by (3), we have
$$
o(-2\ell)=o(2\ell) \ \textrm{ if } 2\ell < n-1.
$$
Thus, we obtain
$$
\textrm{LHS} = 2x^{n-1} + \sum_{2\ell < n-1} o(2\ell) x^{2\ell},
$$
$$
\textrm{RHS} = x + \sum_{2\ell < n-1} o(2\ell) x^{n-2\ell}.
$$
For $x=1$, we see that
$$
\textrm{LHS}=2+\sum_{2\ell < n-1} o(2\ell),
$$
$$
\textrm{RHS} = 1 + \sum_{2\ell < n-1} o(2\ell). 
$$
This gives $\textrm{LHS} = \textrm{RHS}+1 > \textrm{RHS}$ at $x=1$.
Previously, we have seen that $\textrm{LHS}<\textrm{RHS}$ if $0<x\leq \mu$. Since $\mu<1$, we obtain that there is at least one root of (2) in the interval $(\mu, 1)$. Hence, for $n=3,5,17,257,65537$, there is a real root of (1) in the interval $(-1,-\mu)$.
Currently, we do not know whether there are infinitely many Fermat primes.
A: $\deg(p_n) = n-1$.
$p_n$ has $2d_n$ non-real roots thus $n-1-2d_n$ real roots counted with multiplicity, maybe you just didn't find the rare cases where it has some double real roots.
For $n$ even then $p_n$ is odd and it is $> 0$ on $(0,\infty)$ thus its only one real root is at $0$.
The same holds when replacing $order(k\bmod n)$ by any non-negative function such that $f(n-1)>0$.
Not convinced that we can say anything about $R(n)$, do more simulations and see if some non-random estimate pops up.
