Let $A=\{a^2+13b^2 \mid a,b \in\mathbb{Z}, b\neq0\}$. Prove that there a) exist b) exist infinitely many $x,y$ integer pairs such that $x^{13}+y^{13} \in A$ and $x+y \notin A$. (proposed by B. Bayarjargal)
Problem
Source: Mongolia TST 2011 Test 3 #1
Tags: quadratics, modular arithmetic, Ring Theory, Diophantine equation, number theory unsolved, number theory
01.12.2011 12:44
Are there anybody can solve it?
01.12.2011 18:34
A possible direction to proceed, it might be too hard to prove the very last part though. $x \in A \implies \left(\frac{-13}{x}\right) = 1$ (note this is not a Jacobi symbol, it's just an abuse of notation here to show $-13$ is a quadratic residue modulo $x$). Use the fact that $x^{13} + y^{13} \not \equiv x + y \pmod{52}$ sometimes. It is not hard to show using quadratic reciprocity that $\left(\frac{13}{p}\right) = 1$ iff $p \equiv 1,3,4,9,10,12 \pmod{13}$ or $p=2$. Then $\left (\frac{-13}{p}\right) = 1$ iff $p \equiv 1, 7, 9, 11, 15, 17, 19, 29, 31, 35, 47, 49 \pmod{52}$ or $p=2$. Note that these numbers are closed under multiplication under $\mathbb{Z}_{52}$. Thus let's find $x,y$ such that $x+y$ is odd first of all, secondly $x+y$ is not one of the numbers listed above but $x^{13} + y^{13}$ is. WLOG let $x$ be odd, $y$ be even. Then it's easy to show $x^{13} \equiv x \pmod{52}$, however if $4 \nmid y$, then we know $y^{13} \not \equiv y \pmod{52}$. For instance, $2^{13} \equiv 28 \pmod{52}$. Then if we let $x \equiv 3 \pmod{52}$, then $x^{13} + y^{13}$ is the product of quadratic residues modulo $52$, however $x+y$ is not. Thus if we can show for infinitely many $m,n$, $(3 + 52m)^{13} + (2 + 52n)^{13} = a^2 + 13b^2$ then we'd be done. Take note that obviously the $2,3$ can be replaced by any numbers $x,y$ which satisfy $x+y$ is not a product of values where $-13$ is a quadratic residue while $x^{13} + y^{13}$ is. Regardless of if this method works or not, I'd like to see the official solution of this. We have $\mathbb{Z}[\sqrt{-13}]$ can't be extended to make a UFD in a simple way so it's incredibly hard to determine if a number can be expressed in the form $a^2 + 13b^2$ :
05.12.2011 15:27
Lemma . $ x \in A \Leftrightarrow x.13^2 \in A$
) According to the lemma it's enough to find one example that $ x^{13}+y^{13}\in A $ and $ x+y\notin A $ because we can construct infinitely many examples with $(x,y) \rightarrow (169x,169y)$ . ${13}^{13} + {12}^{13} = (6697725)^2 +13(5298830)^2$ But $13+12=a^2 + 13b^2$ has got only one solution in which $a=5 ,b=0$ so $\notin A$ .
05.12.2011 17:50
@mahanmath I understand how to prove the lemma, it's extremely easy, but how in the world did you find that pair
26.11.2014 23:28
This is also a Spanish Mathematical Olympiad problem
27.11.2014 01:13
Bacteria wrote: Let $A=\{a^2+13b^2| a,b \in\mathbb{Z}, b\neq0\}$. Prove that there a) exists b) exists infinitely many $x,y$ integer pairs such that $x^{13}+y^{13} \in A$ and $x+y \notin A$. (proposed by B. Bayarjargal) a) $(a^2+13b^2)(c^2+13d^2)=(ac+13bd)^2+13(ad-bc)^2$ or take the pell equation $x^2-dy^2=1$ and it is well known that iff $d$ no square then there are infinetely so take the pell $x^2-2y^2=1$ with fundamental solution $(3,2)$ then $x^2+13y^2=15y^2+1=611$ so there are infinetely integers at that form.
27.11.2014 01:18
b) we must find one solution for equation $x^2+13y^2=z^{13}+w^{13}$ so take $(x,y,z,w)=(1224,86,3,1)$
27.11.2014 20:28
@codyj: you're right, here's the link: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=3549455&sid=9e8a6e70821d9dde5cafcb89b01bfb27#p3549455 @Αρχιμήδης 6:About a) - I absolutely don't understand it. OR at least not the $ 15y^2+1=611 $ part or how is it important or how is it true or why $x+y\notin A$. About b) - how did you find the numbers? i understand that $(z,w)=(3,1)$ is one of the first thing you try, but how the hell did you find the $x$ and $y$. I don't see a way other then using a computer...