C 2

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

w

0 users

TOPICS

No tags match your search

M

No tags match your search

M

C 2

G H J

Reveal topic tags

modular arithmetic

system of equations

Quadratic Residues

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#1 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10, UpvoteFarm

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?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1444 posts

#2 h May 25, 2007, 12:24 AM • 2 Y

Y by Adventure10, UpvoteFarm

The answer is $231361$ :
$a = 14911,$
$b = 481.$

$15 \cdot 14911 + 16 \cdot 481 = 231361 = 481^2,$
$16 \cdot 14911 - 15 \cdot 481 = 231361 = 481^2.$

Now, let us prove it.
We have :
$E_1 : 15a + 16b = x^2,$
$E_2 : 16a - 15b = y^2.$

$E_1^2 + E_2^2 \implies 481(a^2+b^2) = x^4 + y^4.$

So $x^4 + y^4 = 0 \mod 13 \cdot 37.$

But, this implies $x^4 + y^4 = 0 \mod 13$ and $x^4 + y^4 = 0 \mod 37$ that is, since these are primes, and taking $x$ and $y$ to be non-zero in $\mathbb{Z}/13\mathbb{Z}$ and $\mathbb{Z}/37\mathbb{Z}$ :
$\left(\frac xy \right)^4 = -1 \mod 13$ and $\left(\frac xy \right)^4 = -1 \mod 37.$

But, this is impossible, which implies that $x$ and $y$ are both divisible by $13$ and $37,$ hence $x = 481u$ and $u = 481v,$ hence $a^2 + b^2 = 481^3(u^2+v^2).$

The possible minimum for $\min(u, v)$ is $1.$
But, $1^2 + 31^2 = 2 \cdot 481 \implies 481^2 + (31 \cdot 481)^2 = 481^3(1^2 + 1^2).$

And, (today's a lucky day

), this necessary condition happens to be sufficient, giving the result announced in the very beginning of this post.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

91 posts

#3 h Sep 11, 2007, 4:25 PM • 2 Y

Y by Adventure10, UpvoteFarm

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^{2} + 16^{2}} = \frac {16x^{2} - 15y^{2}}{13\cdot 17}.$
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^{4} + y^{4}.$
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}\right] = \left[\begin{array}{c}0 \\ 0\end{array}\right].$
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$ .

This post has been edited 1 time. Last edited by ideahitme, Aug 20, 2008, 3:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2 posts

#4 h Dec 8, 2007, 1:48 PM • 3 Y

Y by Adventure10, UpvoteFarm, Mango247

Hi Ideahitme,

I'am sorry to say this but it seems to me that there is something wrong in your solution

Namely,

15^2 + 16^2 = 481

but

481 = 13 x 37

( and not as you write 13 x 17)

Thus we work modulo 13 and 37.

So, in Step 2 we consider

15x^2 + 16 y ^2 = 0 mod 37
and
16x^2 - 15y^2 = 0 mod 37

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3615 posts

Peter

#5 h Dec 12, 2007, 11:51 PM • 2 Y

Y by Adventure10, UpvoteFarm

mathmanman wrote:

$\left(\frac xy \right)^4 = - 1 \mod 13$ and $\left(\frac xy \right)^4 = - 1 \mod 37.$

It took me really long to realize these were fractions and not L\'egendre symbols.

Just posting this for the next person.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1677 posts

#6 h Feb 13, 2008, 1:54 AM • 3 Y

Y by UpvoteFarm, Adventure10, Mango247

$15a + 16b = x^2,16a - 15b = y^2\Rightarrow (15^2 + 16^2)a = 15x^2 + 16y^2$
Now $15^2 + 16^2 = 481 = 13\cdot 37$ so we need the congruences
$15x^2 + 16y^2\equiv 0\pmod{p}$
for each of $p = 13,37$ . In each case, if $p$ divides $x$ , then $p$ divides $y$ as well. Otherwise, we get
$(4yx^{ - 1})^2\equiv - 15\pmod{p}$
We can check (using QR for example, or the long way...

) that -15 is not a square modulo either prime, so we necessarily find that 481 divides both $x,y$ . But in this case, if $x = 481m,y = 481n$ , then there is always an integer solution for $a,b$ , namely
$a = 481(15m^2 + 16n^2),b = 481(16m^2 - 15n^2)$
In particular, there's a positive integer solution for $m = n = 1$ , that is, $x = y = 481$ , for $a = 31\cdot 481,b = 481$ . Since $x,y$ positive and divisible by 481, the minimum is $\boxed{481}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#7 h May 24, 2022, 10:07 AM • 1 Y

Y by UpvoteFarm

Let $15a+16b=m^2$ and $16a-15b=n^2.$
Sum up their squares to get $m^4+n^4=481(a^2+b^2)=13\cdot 37(a^2+b^2).$ So $13, 37 \mid m^4+n^4.$

Claim: $13, 37\mid m+n.$
Proof. Assume the contrary that $13\nmid m+n.$ The case with 37 is similar. So we have $m^4\equiv -n^4\pmod{13} \implies m^{12}\equiv- n^{12} \pmod{13}.$ By Fermat's we get the contradiction that $2\equiv 0 \pmod{13}.$ $\blacksquare$

Let $m=481x, n=481y.$ So $a=481(15x^2+16y^2) \text{ and } b=481 (16x^2-15y^2).$ For the least, set $x=y=1,$ to get $a=14911 \text{ and }b=481 \implies b^2=231361.$

This post has been edited 1 time. Last edited by ZETA_in_olympiad, May 24, 2022, 10:07 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a