Question: What is a primitive polynomial? I was looking into some random number generation algorithms and 'primitive polynomial' came up a sufficient number of times that I decided to look into it in more detail.

I'm unsure of what a primitive polynomial is, and why it is useful for these random number generators.

I'd find it particularly helpful if an example of a primitive polynomial could be provided.

Answer: 
BBischof's answer is correct, but unfortunately there's another, quite different possible meaning of the same term: that is a polynomial whose coefficients have no common prime factor (this makes sense over the integers, or other UFDs as well).
See this: and related references there, there is an algorithm for checking any polynomial to be primitive or not.
[COMPUTING PRIMITIVE POLYNOMIALS - THEORY AND ALGORITHM](http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/theory.html)