Adding an explanation as to how I see Example 3.36. Hopefully this adds to your intuition.
The known fact that the polynomials $p_1(x)=x^4+x^3+1$ and $p_2(x)=x^4+x+1$ are primitive (i.e. have roots of maximal order, here $2^{\deg p}-1=15$) is the starting point. Consider a polynomial $q_i(x)=p_i(x^5), i=1,2.$ Let $\beta$ be one of its roots. Then $p(\beta^5)=0$, so $\beta^5$ is of order $15$. Because $5$ is a factor of $15$ this already implies that the order of $\beta$ is $5\cdot15=75$. But we don't know yet that $q_i$ would be irreducible. We can deduce this as follows.
Remember that the degree of the minimal polynomial (over a the prime field $\mathbb{F}_2$) of a root of unity of (odd) order $\ell$ is the smallest integer $r$ such that $\ell\mid 2^r-1$. This is because that is the smallest $r$ such that $\mathbb{F}_2^*$ has a cyclic subgroup of order $\ell$. Note that this is equivalent to saying that $ r=\mathrm{ord}_{\mathbb{Z}_\ell^*}(2) $ is the (multiplicative) order of the coset of $2$ modulo $\ell$. Here $2^r\equiv1\pmod{75}$, iff $2^r\equiv1\pmod{15}$ and $2^r\equiv1\pmod{25}$. The latter congruence is of interest here. That's because we know that $\mathbb{Z}_{25}^*$ is cyclic of order $\phi(25)=20.$ We know (or easily verify) that $2$ is of order 4 in $\mathbb{Z}_5^*$, but that $2^4\not\equiv1\pmod{5^2}$. Therefore $r=\mathrm{ord}_{\mathbb{Z}_{25}^*}(2)$ is a proper multiple of 4, but must also be a factor of $4\cdot5$. As 5 is a prime, we conclude that $r=20$. Hence the minimal polynomial of $\beta$ has degree $20$, and thus must be $q_i(x)$.
The preceding results, Lemma 3.34 and Theorem 3.35, describe this more generally. But my point is that this is also a manifestation of the familiar result from elementary number theory: if the order of an integer $g$ modulo a prime power $p^a$ is $r$, then the order of $g$ modulo $p^{a+1}$ is either $r$ or $pr$.
Note that if the order of the root of $p$ is $\ell$, and we define a new, hopefully irreducible, polynomial by declaring $q(x)=p(x^s)$, where $s$ is a prime, then it is absolutely essential that $s\mid \ell$. If we use a prime $s$ that is not a factor of $\ell$, then things won't work (think Chinese remainder theorem, Little Fermat and all that jazz). As an example consider $f(x)=p_1(x^{17})=x^{68}+x^{17}+1.$ If $\beta$ is a root of $f$, then $\beta^{17}$ is a root of $p_1$, and hence of order 15. Therefore already at this point we get options: the order of $\beta$ may be either $15$ or $15\cdot17=255$. Here both possibilities will occur. If $\alpha$ is a root of $p_1$, then $\alpha^{17}=\alpha^{16}\cdot\alpha=\alpha^2$ is a conjugate of $\alpha$, so we see that $p_1(x)\mid f(x)$. The remaining roots of $f$ are of order 255, but as the order of 2 modulo 255 is eight, this gives us a bunch of factors of degree 8 for $f(x)$. At this point it is not difficult to see that $f(x)$ has a single quartic factor $p_1(x)$ and eight distinct irreducible factors of degree 8.