Something is wrong. If $\beta = 0$ and $A$ is the matrix with all entries $0,$ then the algebraic multiplicity of the eigenvalue $0$ is $n,$ where $A$ is $n$ by $n.$ What you have is then $\dot{q} = p,$ so that $\deg q = 1 + \deg p.$ Same conclusion for $\beta \neq 0$ and $A = \beta I.$
Where did you get this, exactly? It is a bit elaborate for typical homework. What book are you using?
EDIT: Klara, this is a very recent book. If you look on the previous page to this exercise, he says "However, if the inhomogeneous term is of a special form, an asatz might be faster than evaluating the integral in (3.48). See Problem (3.13)."
So, I would say the author changed his mind a bit. The hint you are given does not seem to me to help. Now, I think everything is true for when $\beta$ is not an eigenvalue, and everything except the exact degree is true when $\beta$ is an eigenvalue. What I am going to do is rewrite both $p,q$ in a certain way, as both are vectors of polynomials, that is $ p(t) = \sum_{i=0}^{\deg p} \; t^i P_i, $ where each $P_i$ is a column vector of scalars in either $\mathbb R, \mathbb C,$ the field is not going to matter. Same with $ q(t) = \sum_{j=0}^{\deg q} \; t^j Q_j. $ The point is that multiplication by the matrix $A$ commutes with multiplication by the indeterminate $t$ or any $t^k.$ So we may ask ourselves what $A$ does to each $Q_j.$
Anyway, I will finish this up and then probably write to Gerald Teshl. It strikes me as unlikely that he wants solutions to his questions on the web, but he might be grateful to hear of errata. If it turns out his question is entirely correct, which I do not currently expect, I will think about what to do.