What happens when you mod out by a non-primitive irreducible polynomial over $F_q$? What is the difference between modding out by a primitive polynomial and modding out by a non-primitive irreducible polynomial in a finite field $F_q$?
From what I understand either one should generate a field of $q^n$ elements, where $n$ is the degree of the polynomial, but a big deal is made out of finding primitive polynomials to make the larger field.  What is the difference exactly in the way the resulting field works?
 A: Qiaochu's comment contains the essential algebraic reason. I don't want to hog his priority, but as examples explaining why we are interested in primitive polynomials let me list the following:


*

*Discrete log-tables. One efficient way of presenting a finite field in a computer program is to have a look-up table of discrete logarithms at hand. Using such a LUT implementing multiplication of two field elements becomes easy. At least every program involving finite fields that I have ever written begins by generating such a discrete logarithm table. To that end it is imperative to have a primitive polynomial $p(x)$. If you have one, then its easy to recursively present the powers of the generator $x+(p(x))$ as low degree polynomials in $x$, and you can generate the log-table while doing that.

*As a concrete application, where we immediately see a primitive polynomial show an advantage I mention CRC-(=cyclic redundancy check) polynomials. These are polynomials in $F_2[D]$ (telecommunication engineers prefer to use $D$ as unknown here). The way these are used is that data to be protected by a CRC is first turned into a polynomial in $F_2[D]$ bit-by-bit. Then a few (redundancy) bits are appended to it so that in the end the resulting polynomial becomes divisible by a pre-determined CRC-polynomial $p(D)$. The point of the exercise is that whoever later reads the data can obtain a degree of confidence on its correctness by verifying that the data is, indeed, divisible by $p(D)$. What kind of errors might happen? Usually only a few bits will get toggled. If only a single bit is read incorrectly, then almost any $p(D)$ will work (as long as it is not a monomial). What about the occasions where two bits are toggled, say at positions $i$ and $j$? This would pass the CRC-test undetected only, if the binomial $D^i+D^j$ is divisible by $p(D)$. How does primitivity enter the scene? It is an easy exercise to show that any polynomial of $F_2[D]$ divides some binomials. The key question is: what's the degree of the lowest degree binomial divisible by $p(D)$? This is motivated by the fact the if we can maximize this degree, then we are maximizing the length of the data packet we can protect against such undetected errors. Because the number of redundant bits = the degree of $p(D)$, we are minimizing the nuymber of the redundancy bits needed to protect our data at this level of protection. 
W.l.o.g we can assume that $p(0)=1$, and then the we easily see that the lowest degree binomial divisible by $p(D)$ is $1+D^\ell$, where $\ell$ is the order of $D$ in the quotient ring $F_2[D]/p(D)$. So primitive polynomials show an advantage here. This is only the beginning of the theory, and occasionally we want to protect for more than two bit errors. A typical CRC-polynomial is of the form $p(D)=(1+D)q(D)$, where $q(D)$ is primitive. The extra factor $1+D$ has the effect that in order for an error to pass undetected, the number of errors must be even. Thus polynomials of the above form catch all the patterns of at most 3 errors up to a maximum size of data packet $2^{\deg q(D)}-1-\deg q(D)$ bits.

A: A more intuitive way of understanding why reducing modulo a primitive irreducible polynomial is because you want to avoid duplicated values so that you get a full range field, as explained here:

Reed Solomon codes are created by the manipulation of finite group of
  numbers called a Galois Field. GF(256) is a field consisting of the
  every integer in the range 0 to 255 arranged in a particular order. If
  you could devise an arithmetic where the result of each operation
  produces another number in the field the overflow issues could be
  avoided. The generation (ordering) of the field is key. e.g. a simple
  monotonic series from 0 to 255 is a finite field BUT modulo 255
  arithmetic fails commutative tests i.e. certain operations will not
  reverse. 
A Galois field gf(p) is the element 0 followed by the (p-1) succeeding
  powers of α : 1, α, α^2, α^3, ..., α^(p-1)
Extending the gf(2) field used in binary arithmetic (and CRC
  calculation) to 256 elements that fit nicely in a computer byte:
  gf(2^8) = gf(256). Substituting the primitive element α=2 in the galois
  field it becomes 0, 1, 2, 4, 8, 16, and so on. This series is
  straightforward until elements greater than 127 are created. Doubling
  element values 128, 129, ..., 254 will violate the range by producing
  a result greater than 255. Some way must be devised to "fold" the
  results back into the finite field range without duplicating existing
  elements (this lets modulo 255 aritmetic out). This requires an
  irreducible primitive polynomial. "Irreducible" means it cannot be
  factored into smaller polynomials over the field. Without this
  mathematical insight it is possible to search for suitable numbers
  using empirical methods. There has to be some way of turning off bit 8
  so an XOR operation on results greater than 255 with a number in the
  range 256 to 256+255 will find "irreducible primitive polynomial" if
  they exist. A "brute force" scanning program [source] checks each
  candidate and rejects potential polynomials if they duplicate existing
  elements in the field.

In other words: you need to reduce modulo a primitive irreducible polynomial to avoid duplicated values in your precomputed tables: indeed, your precomputed tables replace 0,1,2,...,256 by alpha^0, alpha^1, ..., alpha^255 so that you can easily replace multiplication by additions of exponents. However, you of course know that some values, like alpha^255, will overflow, so that you need to reduce modulo something. But if you don't use a primitive irreducible polynomial, you will get duplicated values, so that for example alpha^128 may be equal to alpha^1, thus giving you a truncated field (ie, not all values are uniquely represented).
