You need to use something call Kronecker's theorem. It is not hard, so we will prove it. Let F be a field and f(x) in F[x] be a non-constant polynomial. Then there exists an extension field K over F and such that . By unique factorization we can write f(x) as a product of irreducible polynomials. Thus it is necessary an sufficient that only of those factors p(x) has a zero . Since is a non-constant polynomial which is irreducible over F it means is a field. Let us call this field . We can identify that K contains F (up to isomorphism) by (where is the equivalence class mod ) for . Next we note that is a zero of for . Thus is an extension field that we desired. Now to go into induction you have to note that if f(x) is an arbitrary non-constant polynomial then we factorize it were all are irreducible. Now apply the argument on every irreducible factor times. Thus, there exists an extension field K such thatsplits(meaning factors into linear factors).

You can make this result a little stronger: Given field F there is extension field K for a non-constant polynomial such such [K:F]<=n! where n = deg f(x) and f(x) splits over K.