View topic - C 2 • Art of Problem Solving

Peter wrote:

The positive integers $a$ and $b$ are such that the numbers $15a + 16b$ and $16a - 15b$ are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?

We characterize the set
$\mathcal{S} = \{\; (a,b)\;\vert\; 15a + 16b = x^{2},\; 16a - 15b = y^{2}\;\text{for some}\; x,y\in\mathbb{N }\;\}.$
Let $(a,b)\in\mathcal{S}$ . We can find positive integers $x$ and $y$ such that $15a + 16b = x^{2}$ and $16a - 15b = y^{2}$ . After solving the system of equations $15a + 16b = x^{2}$ , $16a - 15b = y^{2}$ , we obtain
$a = \frac { 15x^{2} + 16y^{2}}{15^{2} + 16^{2}} = \frac { 15x^{2} + 16y^{2}}{13\cdot 17},\; b = \frac {16x^{2} - 15y^{2}}{15^...$
Now, we have to work modulo $13$ and modulo $17$ .

Step 1. First, we work modulo $13$ . We need to solve the system of congruences
$15x^{2} + 16y^{2}\equiv 0\; (mod\; 13)\;\;\text{and}\;\; 16x^{2} - 15y^{2}\equiv 0\; (mod\; 13).$
The first equation reads $2x^{2} + 4y^{2}\equiv 0\; (mod\; 13)$ or $x^{2}\equiv - 2y^{2}\; (mod\; 13)$ . The second equation reads $3x^{2} - 2y^{2}\equiv 0\; (mod\; 13)$ or $3x^{2}\equiv 2y^{2}\; (mod\; 13)$ . We apply Gauss Elimination. We compute $3 ( - 2y^{2})\equiv 2y^{2}\; (mod\; 13)$ or $8y^{2}\equiv 0\; (mod\; 13)$ . This implies that $y\equiv 0\; (mod\; 13)$ . Also, we find that $x^{2}\equiv - 2y^{2}\equiv 0\; (mod\; 13)$ so that $x\equiv 0\; (mod\; 13)$ . We conclude that $x\equiv y\equiv 0\; (mod\; 13)$ is the unique solution of the system of congruences.

\textsc{Step 2.} Second, we work modulo $17$ . We need to solve the system of congruences
$15x^{2} + 16y^{2}\equiv 0\; (mod\; 17)\;\;\text{and}\;\; 16x^{2} - 15y^{2}\equiv 0\; (mod\; 17).$
The first equation reads $- 2x^{2} - y^{2}\equiv 0\; (mod\; 17)$ or $2x^{2}\equiv y^{2}\; (mod\; 17)$ . The second equation reads $- x^{2} + 2y^{2}\equiv 0\; (mod\; 17)$ or $x^{2}\equiv 2y^{2}\; (mod\; 17)$ . Hence, we compute $2 ( 2y^{2})\equiv y^{2}\; (mod\; 17)$ or $4y^{2}\equiv 0\; (mod\; 17)$ . This implies that $y\equiv 0\; (mod\; 17)$ . Also, we find that $x^{2}\equiv 2y^{2}\equiv 0\; (mod\; 17)$ so that $x\equiv 0\; (mod\; 17)$ . We conclude that $x\equiv y\equiv 0\; (mod\; 17)$ is the unique solution of the system of congruences.

Combining results from Step 1 and Step 2, we can write $x = 13\cdot 17 u$ and $y = 13\cdot 17 v$ for some positive integers $u$ and $v$ . Now, observe that
$15a + 16b = x^{2},\; 16a - 15b = y^{2}$
becomes
$a = \frac { 15x^{2} + 16y^{2}}{13\cdot 17},\; b = \frac {16x^{2} - 15y^{2}}{13\cdot 17}$
or
$a = 13\cdot 17 (15u^{2} + 16v^{2}) ,\; b = 13\cdot 17 (16u^{2} - 15v^{2}).$
Hence, it follows that the set $\mathcal{S}$ can be represented as
$\mathcal{S} = \{\; (a,b)\;\vert\; a = 13\cdot 17 (15u^{2} + 16v^{2}) ,\; b = 13\cdot 17 (16u^{2} - 15v^{2}), u,v\in\mathbb{N ...$
We therefore conclude that the minimum value is $\left( 13\cdot 17\right)^{2}$ .

Notes

In the solution, we met the systems of congruences. We recall the congruences from Step 1: $15x^{2} + 16y^{2}\equiv 0\; (mod\; 13)$ , $16x^{2} - 15y^{2}\equiv 0\; (mod\; 13)$ . There are many alternative ways to reach $x\equiv y\equiv 0\; (mod\; 13)$ .

Method 1. One may use Brahmagupta-Fibonacci Identity:
$\left( A^{2} + B^{2}\right)\left( X^{2} + Y^{2}\right) = \left( AX + BY\right)^{2} + \left( AY - BX\right)^{2}.$
Indeed, we obtain
$\left({15}^{2} + {16}^{2}\right)\left( a^{2} + b^{2}\right) = \left( 15a + 16b\right)^{2} + \left( 16a - 15b\right)^{2} = x^{...$
Since ${15}^{2} + {16}^{2} = 13\cdot 17$ , we find that $x^{4} + y^{4}$ is divisibly by $13$ . We now apply the following result with $p = 13$ to conclude that $x\equiv y\equiv 0\; (mod\; 13)$ .

Proposition. Let $p$ be a prime with $p\equiv 5\; (mod\; 8)$ . Suppose that $a^{4} + b^{4}$ is divisible by $p$ for some integers $a$ and $b$ . Then, both $a$ and $b$ are divisible by $p$ .

Proof. Assume to the contrary that at least one of them are not divisible by $p$ . Since $p$ divides $a^{4} + b^{4}$ , we see that none of them are divisible by $p$ . Fermat's Little Theorem yields that $a^{p - 1}\equiv b^{p - 1}\equiv 1\; (mod\; p)$ . Since $p\equiv 5\; (mod\;8)$ or since $\frac {p - 1}{4}$ is odd, we have $( - 1)^{\frac {p - 1}{4}} = - 1$ . Since $p$ divides $a^{4} + b^{4}$ , we obtain
$a^{4}\equiv - b^{4}\; (mod\; p).$
Raise both sides of the congruence to the power $\frac {p - 1}{4}$ to obtain
$a^{p - 1}\equiv ( - 1)^{\frac {p - 1}{4}}b^{p - 1}\equiv - b^{p - 1}\; (mod\; p).$
or
$1\equiv a^{p - 1}\equiv - b^{p - 1}\equiv - 1\; (mod\; p).$
This is a contradiction because $p$ is an odd prime. Therefore, both $a$ and $b$ are divisible by $p$ .

Method 2. We now work on the field $\mathbb{Z}/{13\mathbb{Z}}$ . (Since $13$ is prime, we know that the ring $\mathbb{Z}/{13\mathbb{Z}}$ is a field. We identify $\overline{\alpha}\in\mathbb{Z}/{13\mathbb{Z}}$ with $\alpha$ .) The above congruences become
$2x^{2} + 3y^{2} = 0\;\;\text{and}\;\; 3x^{2} - 2y^{2} = 0.$
Of course, Gauss Elimination works. However, we offer an alternative way. Observe that
$\left[\begin{array}{cc}x^{2} & y^{2} \\ - y^{2} & x^{2}\end{array}\right]\left[\begin{array}{c}2 \\ 3\end{array}\righ...$
This implies that $\left[\begin{array}{cc}x^{2} & y^{2} \\ - y^{2} & x^{2}\end{array}\right]$ has zero determinant so that $x^{4} + y^{4} = 0$ . We compute
$x^{12} = \left( x^{4}\right)^{3} = \left( - y^{4}\right)^{3} = - y^{12}$
If $y\neq 0$ , then we also have $x = 0$ . Hence, we obtain $1 = x^{12} = - y^{12} = - 1$ , which is a contradiction. Therefore, we get $y = 0$ and so $x = 0$ .

C 2

Login