MathLinks Forum LaTeX Help AoPS Classes Books Classroom MathLinks Contest Math Resources

The time now is Sat Nov 21, 2009 1:29 am
All times are UTC + 2		 View posts since last visit
View unanswered posts
C 2
View previous topicView next topic
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Arithmetic in Zn » Quadratic Residues
 
 
6 Posts • Page 1 of 1
Author Message
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium
To rate posts you must be logged in
#1
C 2
IMO 1996/4
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?

PostPosted: Fri May 25, 2007 2:24 am
mathmanman
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 19 Jul 2005
Posts: 1438
Location: France
France
To rate posts you must be logged in
#2
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 Smile ), this necessary condition happens to be sufficient, giving the result announced in the very beginning of this post.

PostPosted: Fri May 25, 2007 2:24 am
ideahitme
Hodge Conjecture
Hodge Conjecture

Offline
Joined: 28 Nov 2003
Posts: 85
To rate posts you must be logged in
#3
Re: C 2
IMO 1996/4
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.
_________________
It gives me the same pleasure when someone else proves a good theorem as when I do it myself. <E. Landau>

PostPosted: Tue Sep 11, 2007 6:25 pm
Last edited by ideahitme on Wed Aug 20, 2008 5:33 pm; edited 1 time in total
Chan-Nor
New Member
New Member

Offline
Joined: 07 Dec 2007
Posts: 2
To rate posts you must be logged in
#4
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


Very Happy Wink

PostPosted: Sat Dec 08, 2007 3:48 pm
Peter
Birch & Swinnerton Dyer
Birch & Swinnerton Dyer


Offline
Joined: 05 May 2004
Posts: 5202
Location: Ghent
Belgium
To rate posts you must be logged in
#5
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.
_________________
Boo!

PostPosted: Thu Dec 13, 2007 1:51 am
scorpius119
Navier-Stokes Equations
Navier-Stokes Equations

Offline
Joined: 01 Sep 2004
Posts: 1678
Location: ..., PA
United States
To rate posts you must be logged in
#6
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... Rolling Eyes ) 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}.

PostPosted: Wed Feb 13, 2008 3:54 am
Display posts from previous:   Sort by:   
6 Posts • Page 1 of 1
Home » Forum » Olympiad Section » Number Theory » PEN » Official PEN problems » Arithmetic in Zn » Quadratic Residues
 
View previous topicView next topic
Jump to:  


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum
You cannot post calendar events in this forum

Created and Maintained by Valentin Vornicu - (c) AoPS Inc. 2004-2008