Let's forget the word "division" for a moment.
The claim is that if $f$ and $g$ are polynomials in one variable (i.e., in one indeterminate) with coefficients in a field (e.g., with rational coefficients), and if $g$ is not the zero polynomial, then there exist unique polynomials $q$ and $r$, with $\deg r < \deg g$, such that
$$
f = qg + r.
$$
The preceding equation expresses equality of polynomials as abstract algebraic entities. If you're working with coefficients in a field of characteristic zero (e.g., rational, real, or complex coefficients), it's safe to reformulate the preceding in terms of values of polynomial functions:
$$
f(x) = q(x) g(x) + r(x)
\quad\text{for all $x$.}
\tag{1}
$$
The discussion below uses "function value" language.
Uniqueness is easy: if
$$
q_{1}(x) g(x) + r_{1}(x)
= f(x)
= q_{2}(x) g(x) + r_{2}(x)
\quad\text{for all $x$,}
$$
then $\bigl(q_{1}(x) - q_{2}(x)\bigr) g(x) = r_{2}(x) - r_{1}(x)$. Since the left-hand side is a polynomial multiple of $g$ (hence is either $0$ for all $x$, or is a polynomial of degree at least $\deg g$) and the right-hand side is a polynomial of degree strictly smaller than $\deg g$, each side must be $0$. That is, $q_{1}(x) = q_{2}(x)$ for all $x$, and $r_{1}(x) = r_{2}(x)$ for all $x$.
One proof of existence proceeds by successive subtraction of (polynomial multiples of) $g$ from $f$: The preceding conclusion may be written
$$
f(x) - q(x) g(x) = r(x)
\quad\text{for all $x$,}
$$
in which case it's clear the goal is "to subtract a polynomial multiple of $g$ from $f$, obtaining a polynomial of degree strictly smaller than $\deg g$".
To illustrate the main idea, consider the example
$$
f(x) = x^{3} - 12x^{2} - 42,\quad
g(x) = x - 3.
$$
The "game" will be to subtract successive monomial multiples of $g$ from $f$ with the goal of reducing the degree of the difference at each step.
To that end, focus on the highest-degree term of each: $f(x) = x^{3} + \cdots$ and $g(x) = x + \cdots$. Since $x^{3} = x^{2} \cdot x$, we're led to consider
\begin{align*}
f(x) - x^{2}g(x)
&= x^{3} - 12x^{2} - 42 - x^{2}(x - 3) \\
&= -9x^{2} - 42.
\end{align*}
Since $\deg (-9x^{2} - 42) = 2 < 3 = \deg f$, we've succeeded in writing $f$ as a polynomial multiple of $g$ plus a remainder of degree smaller than $\deg f$ [sic., not $\deg g$]. Note that the preceding holds for all $x$.
Continue in this vein. By similar consideration of the highest-degree terms, $-9x^{2} = -9x\cdot x$, we're led to write
\begin{align*}
\bigl[f(x) - x^{2}g(x)\bigr] - (-9x)\, g(x)
&= \bigl[-9x^{2} - 42\bigr] + 9x(x - 3) \\
&= -27x - 42.
\end{align*}
Combining the two preceding steps, we have
$$
f(x) - (x^{2} - 9x)\, g(x) = -27x - 42\quad\text{for all $x$.}
$$
The remainder still has degree greater than or equal to the degree of $g$, so we can perform another step, obtaining
$$
f(x) - (x^{2} - 9x - 27)\, g(x) = -123\quad\text{for all $x$.}
$$
Here the process ends: Since $\deg(-123) = 0 < \deg g$, we cannot reduce the degree of the remainder further by subtracting monomial multiples of $g$. We have established a decomposition of the form (1) in this example:
$$
f(x) - \underbrace{(x^{2} - 9x - 27)}_{q(x)}\, g(x) = \underbrace{-123}_{r(x)}\quad\text{for all $x$.}
$$
The close analogy with Euclid's algorithm should be clear. The customary "polynomial long division" notation expresses this process more concisely.
Writing out a general proof is straightforward. The key technical step is the following observation: If $f(x) = a_{n}x^{n} + a_{n-1}x^{n-1} + \cdots$ is a polynomial of degree $n$ (i.e., if $a_{n} \neq 0$), if $g(x) = b_{m} x^{m} + b_{m-1}x^{m-1} + \cdots$ has degree $m$ (i.e., if $b_{m} \neq 0$), and if $\deg g = m \leq n = \deg f$ (i.e., if we do not already have a "remainder" of degree smaller than $\deg g$), then
$$
f(x) - \frac{a_{n}}{b_{m}} x^{n - m}\, g(x)
= \underbrace{\left(a_{n} - \frac{a_{n}}{b_{m}}\, b_{m}\right)}_{= 0} x^{n}
+ \left(a_{n-1} - \frac{a_{n}}{b_{m}}\, b_{m-1}\right) x^{n-1} + \cdots
$$
has degree at most $n - 1$. (The second coefficient in parentheses might be zero, so the degree of this "partial remainder" might be strictly smaller than $n - 1$.)
Now do induction on the following statement $P_{n}$:
If $f$ is a polynomial of degree an most $n$ in one variable, and if $g$ is a polynomial in one variable, there exist polynomials $q$ and $r$ such that $f(x) = q(x) g(x) + r(x)$ and $\deg r < \deg g$.
As base case, the induction starts with constant polynomials, for which the conclusion is obvious.
The "key technical step" above shows that if $\deg f = k + 1$, then $f$ may be written as a monomial multiple of $g$ plus a polynomial of degree at most $k$, to which the inductive hypothesis may be applied.
Hint: the remainder will be a polynomial of degree (at most) $1$ so:
$$f(x) = (x-1)(x+2)q(x) + ax + b$$
Substitute $x=1,-2$ in the above and you get two equations in $a,b$.
[
EDIT ] For a less conventional approach (justified in the answer
here) note that $(x-1)(x+2)=0 \iff x^2=-x+2$. Repeatedly using the latter substitution:
$$
\begin{align}
3x^5 - 5x^2 + 4x + 1 &= 3 (x^2)^2 \cdot x - 5(x^2) + 4x + 1 \\
&= 3(x^2-4x+4)x - 5(-x+2) + 4x +1 \\
&= 3(-x+2-4x+4)x + 9x -9 \\
&= -15(x^2)+ 18x + 9x - 9 \\
&= -15(-x+2) + 27 x - 9 \\
&= 42 x -39
\end{align}
$$
Best Answer
Observe that \begin{align} (x+5)(q(x) + 1) &= (x+5)q(x) + (x+5) \\ &= (x+5)q(x) + (x+3) + 2 \\ &= f(x) + 2 \\ &> f(x). \end{align} So $(x+5)(q(x) + 1)$ is a multiple of $x+5$ that is greater than $f(x)$.
Whether this is the "first" such multiple of $x+5$ is a matter of interpretation, because for $x=-4$, we have $f(x) < (x+5)q(x) < (x+5)(q(x) + 1)$. I suppose the idea of the exercise was that $q(x)$ is not the quotient in the polynomial division of $f(x)$ by $x+5$; $$ f(x) = (x+5)(q(x) + 1) - 2, $$ and therefore the remainder is $-2$, and the quotient is $q(x) + 1$ which is the other factor in the "multiple" of $q+5$ that you were asked to find.
Coincidence? I think not. Admittedly, it does seem like a rather awkward way to think about polynomial division.