Find an irreducible polynomial in $ Q[x]$ of degree $726$. Find an irreducible polynomial in $ Q[x]$ of degree $726$.
I first thought of $x^{726}+1$ to start but its roots would be complex so not in $Q$. 
Now I'm thinking to use Eisenstein, so taking the polynomial to be $f(x) = a_nx^{n} + b_{n-1}x^{n-1}+...$ and finding an irreducible element p. However I'm not sure how I would assume p if I don't know anything else but the degree...
This is the first time I have seen a problem of this style so I do want to complete it myself however I would like to know if I am on the correct path.
 A: For this problem, we use Eisenstein's criterion. We deliberately construct a polynomial for which Eisenstein's criterion is satisfied. We could construct this for any prime, but we do it with $p=2$.
How? Well, Eisenstein requires two things :  all coefficients except the leading one should be divisible by $2$, and the constant coefficient should not be divisible by $2^2 = 4$. Multiples of $2$ are easy to find, and those which are not multiples of $4$ can also be found easily ($2$ is such an example). So, any polynomial satisfying this fits the bill. The polynomial $x^{726} +2$ is one such : all coefficients except the leading ($1$) are multiples of $2$ (almost all of those are $0$, so this is obvious), but $2$ is not a multiple of $4$. So Eisenstein applies and we have an example.
For another one : $x^{726} + 4x^{725} + ... + 4x^2+4x+2$ also qualifies.
Of course, switching $2$ for another prime can also be done.


How to identify which prime to perform an Eisenstein on?

Well, the first thing to note is that Eisenstein may not even work for an irreducible polynomial. For example, Eisenstein won't work on $x^6+108$ (You can try to see why), even if I shift $x \to x\pm a$ for a constant $a$. However, it is irreducible.
Similarly,Eisenstein would not work on $x^4 + 4$. But then, nothing would work : in fact $x^4+4 = (x^2-2x+2)(x^2+2x+2)$.
But when it does work, it comes in many ways : the most obvious from observing the constant coefficient. 
Example : Show that $x^6 + 48x+24$ is irreducible. 
Answer : $24$ is a multiple of $2$ but also of $4$, so you can't use $2$. You can use $3$ though : $24$ is not a multiple of $9$, and $48$ is a multiple of $3$. So things work out.
Another not-so-obvious one is from a shift. Also, usually while exhibiting something for a family of polynomials, you could use the index of the family. For an example of both these, for a prime, consider $x^p + x^{p-1} + \ldots + x+1$. It is irreducible after the shift $x \to x+1$, then applying Eisenstein for the prime $p$.
Sometimes there may be no link. For example, take $x^2+x+2$. It is irreducible after the shift $x \to x+3$ giving $x^2+7x+14$, which satisfies Eisenstein with $7$ although one would not have guessed this from the initial polynomial.
Finally, you can use the reversed polynomial technique. Any polynomial is irreducible if and only if the polynomial obtained by reversing the coefficients is irreducible. A reversed Eisenstein is possible, for this one observes the leading coefficient.
Let us take $2x^5-4x^2-3$. Clearly $4$ and $3$ are coprime, so right now you cannot apply Eisenstein. Reverse the coefficients : they are in the order $2,0,0,-4,0,-3$. After reversing, they would be in the order $-3,0,-4,0,0,2$ , giving the polynomial $-3x^5-4x^3+2$. This polynomial is Eisenstein with $2$, so is irreducible. One can then conclude that the latter is irreducible.
This tells you that when you are looking for a prime to do Eisenstein on, you must derive hints from a pattern (does it belong to a family?) , its middle and constant coefficients, or its middle and leading coefficients by reversal.
