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

Question

I am trying to prove $\forall n \in Z,$ : ($\exists a,b \in Z$ $n=4a+5b$) $\implies$ ($\exists a,b \in Z$ $n^2 = 5a+4b-1$)

Which proof technique would work the best?

Answer 1

Accumulating selected comments into an answer . . .

Fix $n\in Z$.

Let $P,Q$ be the statements \begin{align*} P&=\exists a,b \in \mathbb{Z}\;(n=4a+5b)\\[4pt] Q&=\exists a,b \in \mathbb{Z}\;(n^2=5a+4b-1)\\[4pt] \end{align*} The goal is to prove $P\implies Q$.

A key observation is that the variables $a,b$ in the statement $P$ are independent of the variables $a,b$ in the statement $Q$.

For example, leaving $P$ unchanged, if we change the variable names in $Q$ to $a',b'$ instead of $a,b$, the new statement $Q'$ would be equivalent to $Q$.

Next, recall that a statement of the form $P\implies Q$ is true unless $P$ is true and $Q$ is false.

Typically, to directly prove a statement of the form $P\implies Q$, one starts by assuming $P$, and then, based on that assumption, one proceeds to prove $Q$.

But if we can prove $Q$ without assuming $P$, that already suffices to prove $P\implies Q$.

And in fact, as discussed in the comments, $Q$ is true, all by itself.

I outlined one way to prove $Q$, and Bill Dubuque outlined another.

$\bullet\;\;$My version:

I'll assume you have Bezout's theorem: If $A,B\in\mathbb{Z}$ are such that $\gcd(A,B)=1$, the equation $AX+BY=1$ has a solution in integers $X,Y$.

Noting that if $AX+BY=1$, then $A(NX)+B(NY)=N$, we get the corollary: If $A,B\in\mathbb{Z}$ are such that $\gcd(A,B)=1$, then for all $N\in\mathbb{Z}$, the equation $AX+BY=N$ has a solution in integers $X,Y$.

As a consequence, since $\gcd(5,4)=1$, every integer is expressible as $5a+4b$ for some $a,b\in\mathbb{Z}$.

From that, it follows easily that every integer is expressible as $5a+4b-1$ for some $a,b\in\mathbb{Z}$. In particular, $n^2$ is so expressible. Therefore $Q$ is true.

$\bullet\;\;$Bill Dubuque's version (admittedly simpler):

From the identity $m=5(m)+4(-m)$, it follows that every integer can be expressed as $5a+4b$ for some $a,b\in\mathbb{Z}$. In particular, $n^2+1$ is so expressible. Therefore $Q$ is true.