I am looking for the following theorem (or rather I should say I am hoping the following is indeed true):
CONJECTURE 1: First, let $q$ be a power of a prime integer ($q$ may be even), and let $\mathbb{F}_q$ be the field with $q$ elements. Next, let $f(x)$ be an irreducible polynomial in $\mathbb{F}_q[x]$ of degree $d$, and let $h(x)$ be an irreducible polynomial of degree $2d$. Then there is a root $\phi$ of $f(x)$ in the field $\mathbb{F}_q[x]/h(x)\mathbb{F}_q[x]$. Equivalently, there is a $\phi$ such that $f(\phi) \equiv 0 \mod h(x)$.
Any insight you can give would be really helpful. I am not a number theorist so I am not sure where else to look.
This is indeed true.
Since $h(x)$ is irreducible of degree $2d$, $\mathbb{F}_q[x] / (h(x))$ is a field extension of degree $2d$ over $\mathbb{F}_q$, hence is $\mathbb{F}_{q^{2d}}$ (and by construction this field contains a root of $h(x)$). In fact, one can show that $h(x)$ splits in $\mathbb{F}_{q^{2d}}$ by showing that if $\alpha$ is a root of $h$, then the other possible roots are $\alpha^q,\alpha^{q^2}, ... , \alpha^{q^{2d-1}}$.
By the same argument, $f(x)$ splits in $\mathbb{F}_{q^{d}}$, hence has a root (all roots) in $\mathbb{F}_{q^{2d}}$ which is an extension of $\mathbb{F}_{q^{d}}$.
Actually, you could replace $2d$ by any multiple of $d$ and the same argument would work.