OK, I have a proof which meets your conditions. I relied on this write up of the standard proof as a reference.
Lemma 1: Let $K/F$ be an extension of fields, and let $f(x)$ and $g(x)$ be polynomials in $F[x]$. Let $d_F(x)$ be the GCD of $f$ and $g$ in $F[x]$ and let $d_K(x)$ be the GCD of $f$ and $g$ in $K[x]$. Then $d_F(x)$ and $d_K(x)$ coincide up to a scalar factor.
Proof: Since $d_F(x)|f(x)$ and $d_F(x)|g(x)$ in $K[x]$, we have $d_F(x)|d_K(x)$. Now, there are polynomials $p(x)$ and $q(x)$ in $F[x]$ such that $f(x) p(x) + g(x) q(x) = d_F(x)$. So $d_K(x) | d_F(X)$. Since $d_F(x)$ and $d_K(x)$ divide each other, they only differ by a scalar factor.
Lemma 2: Let $f(x)$ and $g(x)$ be polynomials with $g(0) \neq 0$. Then, for all but finitely many $t$, the polynomials $f(tx)$ and $g(x)$ have no common factor.
Proof: Let $f(x) = f_m x^m + \cdots + f_1 x + f_0$ and $g(x) = g_n x^n + \cdots + g_1 x + g_0$. If $f(tx)$ and $g(x)$ HAVE a nontrivial common factor, then there are polynomials $p(x)$ and $q(x)$, of degrees $\leq n-1$ and $\leq m-1$, such that
$$f(tx) p(x)=g(tx) q(x).$$
This is $m+n$ linear equations on the $m+n$ coefficients of $p$ and $q$.
Writing this out in coefficients, the matrix
$$\begin{pmatrix}
f_m t^m & \cdots & f_1 t & f_0 & 0 & 0 & \cdots & 0 \\
0 & f_m t^m & \cdots & f_1 t & f_0 & 0 & \cdots & 0 \\
\ddots \\
0 & 0 & \cdots & 0 & f_m t^m & \cdots & f_1 t & f_0 \\
g_n & \cdots & g_1 & g_0 & 0 & 0 & \cdots & 0 \\
0 & g_n & \cdots & g_1 & g_0 & 0 & \cdots & 0 \\
\ddots \\
0 & 0 & \cdots & 0 & g_n & \cdots & g_1 & g_0
\end{pmatrix}$$
has nontrivial kernel. The determinant of this matrix is a polynomial in $t$, with leading term $(f_m)^n (g_0)^n t^{mn} + \cdots$. (Recall that $g_0 \neq 0$.) So, for all but finitely many $t$, this matrix has nonzero determinant and $f(tx)$ and $g(x)$ are relatively prime. QED.
Now, we prove the primitive element theorem (for infinite fields). Let $\alpha$ and $\beta$, in $K$, be algebraic and separable over $F$, with minimal polynomials $f$ and $g$. We will show that, for all but finitely many $t$ in $F$, we have $F(\alpha - t \beta) = F(\alpha, \beta)$.
Let $f(x) = (x -\alpha) f'(x -\alpha)$ and $g(x) = (x - \beta) g'(x - \beta)$. Since $\beta$ is separable, we know that $g'(0) \neq 0$. Note that $f'$ and $g'$ have coefficients in $K$. By Lemma 2, for all but infinitely many $t$ in $F$, the polynomials $f'(ty)$ and $g'(y)$ have no common factor. Choose a $t$ for which no common factor exists. Set $F' = F(\alpha - t \beta)$; our goal is to show that $F'=F(\alpha, \beta)$.
Set $h_t(x) = f(tx + \alpha-t \beta)$. Note that $h_t(x)$ has coefficients in $F'$. We consider the GCD of $h_t(x)$ and $g(x)$.
Working in $K$, we can write $h_t(x) = t (x - \beta) f'(t (x- \beta))$ and $g(x) = (x-\beta) g'(x-\beta)$. By the choice of $t$, the polynomials $f'(t (x- \beta))$ and $g'(x-\beta)$ have no common factor, so the GCD of $h_t(x)$ and $g(x)$, in the ring $K[x]$, is $x-\beta$.
By Lemma 1, this shows that $x - \beta$ is in the ring $F'[x]$. In particular, $\beta$ is in $F'$. Clearly, $\alpha$ is then also in $F'$, as $\alpha= (\alpha - t \beta) + t \beta$. We have never written down an element of any field larger than $K$. QED.
These results have been known for many years. Here are some references and further developments; full bibliographic details are at the end of this answer.
Reducibility criteria for cubics over finite fields of characteristic at least $5$ were given already in 1906 by Dickson. In fact he gave conditions for a cubic to have each of the possible factorization types. Reducibility criteria for cubics in characteristic $2$ were given in 1966 by Berlekamp, Rumsey and Solomon (see also their 1967 paper). Those criteria are slightly different than your Theorem A. Your Theorems A and B appear to have been published for the first time in 1975 by Williams, who also gave criteria for each of the possible factorization types.
Reducibility criteria for quartics over prime fields of odd order were given by Skolem in 1952. In 1969, Leonard gave a different proof of Skolem's result, which extends at once to non-prime fields of odd order. Finally, reducibility criteria for quartics in characteristic $2$ were given by Leonard and Williams in 1972.
Your Theorems A and B can be generalized in various ways. Bluher's 2004 paper generalizes your Theorem A to polynomials of the form $x^{p^k+1}+ax+b$. In a series of papers culminating in 1980, Agou determined all instances when $f(L(x))$ is irreducible over $\mathbf{F}_{p^s}$, where $f,L\in\mathbf{F}_{p^s}[x]$ and all terms of $L(x)$ have degree $p^i$ with $i\ge 0$. The case $f=x+c_3$ and $L=x^3+c_2 x$ with $p=3$ yields your Theorem B. Subsequently, a simpler proof of Agou's results was given by Cohen in 1982; following two related papers by Moreno, Cohen gave an even simpler proof in 1989.
References:
- S. Agou, Irréducibilité des polynômes $f(\sum_{i=0}^m a_i X^{p^{ri}})$ sur un corps fini $\mathbf{F}_{p^s}$, Canadian Mathematical Bulletin 23 (1980), 207-212
- E. R. Berlekamp, H. Rumsey and G. Solomon, Solutions of algebraic equations in field of characteristic 2, Jet Propulsion Lab. Space Programs Summary No. 4 (1966), 37-39
- E. R. Berlekamp, H. Rumsey and G. Solomon, On the solution of algebraic equations over finite fields, Information and Control 10 (1967), 553-564.
- A. W. Bluher, On $x^{q+1}+ax+b$, Finite Fields and their Applications 10 (2004), 285-305
- S. D. Cohen, The irreducibility of compositions of linear polynomials over a finite field, Compositio Mathematica 47 (1982), 149-152
- S. D. Cohen, The reducibility theorem for linearised polynomials over finite fields, Bulletin of the Australian Mathematical Society 40 (1989), 407-412
- L. E. Dickson, Criteria for the irreducibility of functions in a finite field, Bulletin of the American Mathematical Society 13 (1906), 1-8
- P. A. Leonard, On factoring quartics (mod $p$), Journal of Number Theory 1 (1969), 113-115
- P. A. Leonard and K. S. Williams, Quartics over GF($2^n$), Proceedings of the American Mathematical Society 36 (1972), 347-350
- Th. Skolem, The general congruence of 4th degree modulo $p$, $p$ prime, Nordisk matematisk tidskrift 34 (1952), 73-80
- K. S. Williams, Note on cubics over GF($2^n$) and GF($3^n$), Journal of Number Theory 7 (1975), 361-365
Best Answer
Without loss of generality we may assume that $f_1$ and $f_2$ are monic with integral coefficients.
Let $P_i$ be the set of primes $p$ such that the image of $f_i$ in $\mathbb F_p[x]$ factors into linear factors.
Then, as a consequence of Chebotarev's density theorem (actually the weaker Frobenius density theorem is good enough here) the splitting fields of $f_1$ and $f_2$ are the same if and only if the sets $P_1$ and $P_2$ differ only by finitely many elements.
Using effective versions of Chebotarev, one can make a finite (yet impracticable) criterion from that.