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

Question

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.

Answer 1

Simpler: $\bmod 9\!:\ \underbrace{\overbrace{n^2\equiv \color{#0a0}{-n}-1}^{\textstyle \color{#0a0}{-n}\equiv 5a\!+\!4b}}_{\textstyle (n\!-\!4)^2\equiv\color{#c00}{-3}} \:$ has no roots by $\,\overbrace{\text{its discriminant $\,\color{#c00}{-3}\not\equiv c^2\,$ is nonsquare}}^{\textstyle 9\mid c^2\!+\!3\,\Rightarrow\, 3\mid c\,\Rightarrow\, 9\mid 3}$.

Answer 2

The system of $2$ equations to be satisfied simultaneously are

$$n = 4a + 5b \tag{1}\label{eq1}$$

$$n^2 = 5a + 4b - 1 \tag{2}\label{eq2}$$

To solve them, I'll first simplify by eliminating a variable. As the $n$ and $n^2$ are not linearly related, I'll eliminate the $a$ variable instead by taking $4$ times \eqref{eq2} and subtracting $5$ times \eqref{eq1} to get

$$4n^2 - 5n = (16b - 4) - 25b \implies 4n^2 - 5n + 4 = -9b \tag{3}\label{eq3}$$

Thus, the LHS must be a multiple of $9$, i.e.,

$$4n^2 - 5n + 4 \equiv 0 \pmod 9 \tag{4}\label{eq4}$$

This also means the LHS is a multiple of $3$, so checking it modulo $3$ first gives

$$4n^2 - 5n + 4 \equiv n^2 - 2n + 1 = (n - 1)^2 \equiv 0 \pmod 3 \tag{5}\label{eq5}$$

Since this means $n \equiv 1 \pmod 3$, you only need to check $n \equiv 1, 4, 7 \pmod 9$ in \eqref{eq4}, with each giving a result of $4n^2 - 5n + 4 \equiv 3 \not\equiv 0 \pmod 9$. Thus, for all integers $n$, there are no integers $b$ which allow \eqref{eq3} to be true, so there are no solutions to \eqref{eq1} and \eqref{eq2}.

Answer 3

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$.