Gfrktyl

While José Carlos Santos's answer is correct, I think it might be useful to talk about why $r(x)$ is defined to have degree less than $p_2(x)$. (J.G. explains this, but at a higher level than I suspect someone wanting "pre-calculus" would follow.)

If the degree of $r(x)$ is the same size or greater than $p_2(x)$, then you can subtract off a multiple of $p_2(x)$ from $r(x)$ to get a new remainder of lower degree. I.e., we can continue the division process until $r(x)$ is of lower degree than $p_2(x)$. It is only then that we have to stop and call anything left over the remainder.

For example, dividing $3x^3 - 2x^2 + x - 5$ by $x^2 + 1$ follows these steps:

1. Note that the ratio of the leading terms is $frac {3x^3}{x^2} = 3x$
   


2. Multiply $x^2 + 1$ by $3x$ and subtract the result ($3x^3 + 3x$) from $3x^3 - 2x^2 + x - 5$, leaving $-2x^2 - 2x - 5$. I.e.,$$3x^3 - 2x^2 + x - 5 = (3x)(x^2 + 1) + (-2x^2 - 2x - 5)$$
   


3. Note that the ratio of the leading terms of the remainder and $x^2 + 1$ is $frac {-2x^2}{x^2} = -2$.


4. Multiply $x^2 + 1$ by $-2$ and subtract the result ($-2x^2 - 2$) from $-2x^2 - 2x - 5$, leaving $-2x - 3$. I.e., $$-2x^2 - 2x - 5 = (-2)(x^2 + 1) + (-2x-3)$$
   


5. Note that the ratio of the leading terms is now $frac {-2x}{x^2} = frac {-2}x$, which is not a polynomial, so we cannot continue.

Combining the results from steps 2 and 4:
$$begin{align}3x^3 - 2x^2 + x - 5 &= (3x)(x^2 + 1) + (-2)(x^2 + 1) + (-2x-3)\&=(3x - 2)(x^2 + 1) + (-2x-3)end{align}$$

If you stop at step 2, then $r(x)$ is indeed not linear. But at that stage, we could continue the division to get something smaller. It was only when the remainder was of lower degree that we had to stop.

The point is we can prove as much. Let the quadratic be $q:=ax^2+bx+c$. Working modulo $q$, $x^2=-(bx+c)/a$. Each $x^n$ is then of the form $cx+d$ modulo $q$; you can prove this by induction (you can even get recursion relations on the coefficients). For example, $x^3=-(bx^2+cx)/a$, but we can turn replace $x^2$ as above.

An explanation rather than a full proof. Trying to describe it more simply:

Suppose your first polynomial is
$$P=ax^4+bx^3+cx^2+dx+e$$
and you want to divide it by
$$Q=fx^2+gx+h$$

The first step is to multiply $Q$ by something which will turn its first term into $ax^4$. You've now got a polynomial which, when you subtract it from $P$, will make $ax^4$ disappear.

Then you do the same again, except you arrange for the $x^3$ term to disappear.

Now you have two quadratics: what's left of $P$, and $Q$.

So, multiply $Q$ by a suitable constant to make the $x^2$ terms match, and subtract it. Now all that's left is a multiple of $x$ and a constant, since you've got rid of all the higher order terms—and that's your linear remainder.

Simply explaining: the key IDEA is that you are not done dividing until your remainder is not further divisible by your divisor. The key WORD in your post is "GENERALLY" because the conclusion is not hard and fast, it is simply "usually" so.

IDEA first. Consider simple numbers, perhaps dividing 1,034 by 10. You begin at the left and work right (this is taught in first grade of course so I won't belabor the process) until you cannot usefully continue. So you get 100 R 34, and 3 R 4, and stop when left with a remainder (4) less than your divisor, 10. Easy enough to figure when it's "less than" with numbers, but slightly less so with polynomials. But we see it slightly differently with polynomials: we stop when the order of the remainder is lower than the order of the divisor. So dividing by 7x^2, and having a remainder with just x^2, we usually grit our teeth (we DO love our integers...) and use "1/7" eliminating the remainder's 2nd order term (x^2). At that point, coninuing becomes difficult even with gritted teeth.

And so we stop. Notice that it is not that the remainder is now linear with that being special in some way: it is simply of lower order than the divisor. In the case of dividing by a 2nd order polynomial, that means it is 1st order, or simply a constant (number).

Which brings in the "generally" part: in practice, it COULD be just the constant, and not a linear equation. "x^2 + 8" divided by x^2, for example. But not usually. Hence "generally" in your post's statement. And moving up in order, say a fifth order divisor, while you'd usually expect, just out of probability, a fourth order remainder, it could also be a third, second, or first order remainder, or just a constant.

So it's not a great theorem with a stunning proof, just a practical observation based upon the mechanics we use for the division.

(And it adds an "idiot check" in case one stops early, thinking he's finished. "Wait, I can't be, it ought to be linear and it isn't so maybe I need to keep working...")

The accepted answer is perfect, of course, and I would not have posted this as an answer if I had enough reputation to comment... but I haven't, so this is my answer (or really a follow-up-question).

I wonder if the solution provided in the question $p(x)=(x^2−2x−3)q(x)+ax+b$ is the "full" solution. This solution describes only the form of the remainder: a linear term.

With the actual terms given in the question, it is possible to determine actual values for $a$ and $b$, being $3$ and $-4$. The remainder therefore is the term $3x-4$.

I found this solution by setting up an Excel sheet and trying out a couple (hundred) of combinations, but I now wonder if there is a way of finding this term without using "brute force".

Note: if you multiply the two terms given in the question $(x-3)$ and $(x+1)$ you get the third term $(x^2-2x-3)$, so this question boils down to something like "remainder when dividing by 3, remainder when dividing by 5, remainder when dividing by 15", which might have an impact on solving it.