Determining the truth of $\forall \; n \in Z, \exists \; a,b \in Z$ : $n=4a+5b$ $\implies$ $n^2 = 5a+4b-1$ The question at proving $\forall n \in Z,$ : ($\exists a,b \in Z$ $n=4a+5b$) $\implies$ ($\exists a,b \in Z$ $n^2 = 5a+4b-1$) originally asked one thing but then it was corrected to ask something quite different. I had already started answering the original question, and finished answering it but then deleted the answer. As I believe the original question is quite interesting, I'm asking it here, along with providing my answer.
The original question was asking to prove

$\forall \; n \in Z, \exists \; a,b \in Z$ : $n=4a+5b$ $\implies$ $n^2 = 5a+4b-1$

Although as Matthew Daly's comments indicate

Given $n$, if you choose $a$ and $b$ such that the first equation is not true, then the implication is true because a false premise implies any consequent.

I, instead, considered the implication of it saying that for each integer $n$, there always exists integers $a,b$ such that they satisfy both of the following $2$ equations simultaneously.
$$n = 4a + 5b \tag{1}$$
$$n^2 = 5a + 4b - 1 \tag{2}$$
The OP originally suggested

I tried assuming that the LHS is true and squaring $4a+5b$ and tried to make it equal to the RHS but I am not sure if that's the right way.

This is one way to try, but I don't see any way to finish the solution. This is because you get $n^2 = 16a + 40ab + 25b^2 = 5a + 4b - 1$, giving a mixture of terms with $a$, $b$, $ab$, $a^2$ and $b^2$. The OP ended with

Which proof technique would work the best?

I believe an approach to check is to do some sort of manipulation of the equations, and then check one or a few relatively small moduli to determine how to limit the potential solutions, or even possibly show there are no solutions.

If $n=4a+5b$ and $n^2+1=5a+4b$, then $n^2+n+1=9(a+b)$, which implies $9$ divides $n^2+n+1$. This in turn implies $9$ divides $4n^2+4n+4=(2n+1)^2+3$. But this is impossible, since if $9$ divided $(2n+1)^2+3$, then $3$ would have to divide $2n+1$, in which case $(2n+1)^2+3$ leaves remainder $3$ when divided by $9$.
