Cylotomic polynomial $\Phi_n(x) $: if $a$ is a root then so is $a^{k}, (k, n) =1$ It is well known that the $n$'th cylotomic polynomial $\Phi_n(x) \in\mathbb {Q} [x] $ has its roots as $\cos(2k\pi/n)+i\sin(2k\pi/n),(k,n)=1$.
I would like to establish the same fact without using any knowledge of complex numbers or circular functions by working entirely in the field $K=\mathbb{Q} [x] /(\Phi_n(x)) $.
More formally

Let $\Phi_n(x) $ be defined as the irreducible factor $f(x) $ of $x^n-1$ such that $f(x) $ is not a factor of $x^r-1$ for any $r<n$ and let $K=\mathbb{Q} [x] /(\Phi_n(x))$. If $a\in K$ is a root of $\Phi_n(x) $ then so is $a^{k}, (k, n) =1$.

I demonstrate the easy case for $n=3$. Here $\Phi_{3}(x)=x^2+x+1$ and clearly if $a^2+a+1=0$ and $b=a^2$ then $b^2=a^4=a^3a=a$ and hence $b^2+b+1=a+a^2+1=0$ so that both $a$ and $b=a^2$ are roots of the polynomial $x^2+x+1$.
I think (but not sure) this is same as saying that if the polynomial $\Phi_n(x^k) $ is divided by $x^n-1$ then the remainder is $\Phi_n(x) $. 

Your statement about the remainder after polynomial long division is false. For instance, $$\Phi_{15}(x) = x^8 -x^7 + x^5-x^4+x^3-x+1$$
$$\Phi_{15}(x^2) = x^{16} -x^{14} + x^{10}-x^{8}+x^6-x^2+1$$
which has remainder $-x^{14} +x^{10} -x^8+x^6-x^2+x+1$ after division by $x^{15}-1$.
Instead, let us proceed via the definition of $\Phi_n(x)$. The roots of $\Phi_n(x)$ are exactly those $\alpha$ which satisfy $\alpha^n=1$ but not $\alpha^d=1$ for any $1\leq d<n$. So if $k$ is an integer relatively prime to $n$, we have two things: $$(\alpha^k)^n = \alpha^{kn} = (\alpha^n)^k = 1$$ $$(\alpha^k)^d = \alpha^{kd} = \alpha^{k'} \neq 1$$ where in the final line, $1 \leq k' < n$ is an integer equal to $kd$ modulo $n$ - we know that $kd$ cannot be divisible by $n$ because $d$ is smaller than $n$ and $k$ is relatively prime to $n$. Therefore $\alpha^{k'}$ is a root of $\Phi_n(x)$.
