Yes, your inference is correct. Essentially it is a special case of the well-known discriminant test. Namely, if a quadratic $\rm\:f(x)\in R[x]\:$ has a root in a ring R, then its discriminant is a square in R. Said contrapositively, if the discriminant is not a square in R, then the quadratic has no root in R.
The proof by completing the square works in any ring R (so in $ \mathbb Z/89 = $ integers mod $89$), viz.
$$\rm\: \ \ 4a\:(a\:x^2 + b\:x + c = 0)\:\Rightarrow\: (2a\:x+b)^2 =\: b^2 - 4ac $$
When learning about (modular) arithmetic in new rings it is essential to keep in mind that, like above, any proofs from familiar concrete rings (e.g. $\mathbb Q,\mathbb R,\mathbb C)$ will generalize to every ring if they are purely ring theoretic, i.e. if the proof uses only universal ring properties, i.e. laws that hold true in every ring, e.g. commutative, associative, distributive laws. Thus many familar identities (e.g. Binomial Theorem, difference of squares factorization) are universal, i.e. hold true in every ring.
This is one of the great benefits provided by axiomatization: abstracting the common properties of familiar number systems into the abstract notion of a ring allows one to give universal proofs of ring theorems. It is not necessary to reprove these common ring properties every time one studies a new ring (such reproofs occurred frequently before rings was axiomatized).
My first post here, so please excuse me if I'm not doing this right.
In response to Stefan4024's post above, $5^4 = 625$. You erroneously wrote $5^3 = 625.$
To solve the problem, you only need to lift twice.
After finding $x = \pm 2 ~(\text{mod } 5)$ or $x = 2, 3$ to be the solutions of $f(x) = 0 ~(\text{mod }5)$, the solutions can be lifted $(\text{mod }5^2)$ or $(\text{mod }25).$
After that, just a single lift to (mod $5^4$) or (mod $625$) is required. This is because one can lift a solution (mod $p^k$) to (mod $p^{m+k}$) as long as m is less than or equal to $k$. In the first lift (from $5$ to $25$), $m = k = 1$, and in the second lift (from $25$ to $625$), $m = k = 2$.
Doing this for both solutions $x = 2$ and $x = 3 ~(\text{mod }5)$ gives the respective solution sets for $f(x) = 0 ~(\text{mod }625)$ as :
$$x = 162 + 625n$$
and
$$x = 463 + 625n$$
where $n$ can take any integer value.
The solutions can be expressed more compactly as:
$$x = 162 \text{ or } 463 ~~(\text{mod }625)$$
Best Answer
Edit: The original modulus was $89$. We keep the original calculation. A small appended modification deals with $101$.
The given congruence has a solution if and only if the congruence $$16x^2+40x-72\equiv 0\pmod{89}$$ has a solution. (We multiplied through by $8$ as a preparation to completing the square.)
This congruence has a solution if and only if $$(4x+5)^2-25-72\equiv 0\pmod{89}$$ has a solution. Equivalently, we want to find out whether $(4x+5)^2\equiv 8\pmod{89}$ has a solution.
The congruence $w^2\equiv 2\pmod{89}$ has a solution. We can see this from the fact that the Legendre symbol $(2/89)$ is equal to $1$, since $89$ is of the shape $8k+1$.
Since for any $w$, the congruence $4x+5\equiv w\pmod{89}$ has a solution, our original congruence does.
Added: For the new modulus of $101$, we arrive in the same way at the congruence $w^2\equiv -4\pmod{101}$. We have $(-4/101)=(-1/101)$. But $101$ is of the form $4k+1$, so $(-1/101)=1$, and thus the congruence has a solution.