The last digit of the number $x^2 +xy+y^2$ is zero (where $x$ and $y$ are positive integers). Prove that two last digits of this numbers are zeros.
Problem
Source:
Tags: quadratics, Divisibility Theory
14.09.2007 15:24
$ (x+1)(y+1)=x+xy+y+1=x^{2}+xy+y^{2}+1=1(mod 2)$. So $ x=y=0(mod 2)$. So $ x^{2}+xy+y^{2}=0(mod 4)$. $ 4(x^{2}+xy+y^{2})=(2x+y)^{2}+3y^{2}$. Since $ (3/5)=-1, 2x+y=y=0(mod 5)$. Therefore, $ x^{2}+xy+y^{2}=0(mod 25)$. from $ x^{2}+xy+y^{2}=0(mod 4),(mod 25)$ we conclude $ x^{2}+xy+y^{2}=0 (mod 100)$
15.09.2007 13:57
Peter wrote: The last digit of the number $ x^{2}+xy+y^{2}$ is zero (where $ x$ and $ y$ are positive integers). Prove that two last digits of this numbers are zeros. The above proof has a straighfoward generalization. Let $ \left(\frac{a}{p}\right)$ denote the Legendre symbol. We first prove two facts. Lemma. Let $ p$ be an odd prime with $ p>3$. Then, we obtain \[ \left(\frac{-3}{p}\right) =\begin{cases}1, & p\equiv 1\; (mod\; 3) ,\\ -1, & p\equiv-1\; (mod\; 3).\\ \end{cases}\] Proof Using well-known properties of Legendre symbol, we compute \[ \left(\frac{-3}{p}\right) =\left(-1\right)^{\frac{p-1}{2}}\left(\frac{3}{p}\right) =\left(-1\right)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(-1\right)^{\left(\frac{3-1}{2}\right)\left(\frac{p-1}{2}\right)}=\left(\frac{p}{3}\right).\] Proposition Let $ p$ be a prime with $ p\equiv-1\; (mod\; 3)$ and let $ f(x,y)=x^{2}+xy+y^{2}$. Whenever $ f(x,y)$ is divisible by $ p$ for some pairs $ (x,y)$ of integers, both $ x$ and $ y$ are divisible by $ p$. Hence, $ f(x,y)$ is divisible by $ p^{2}$. Proof Simple parity arguments kill the case $ p=2$. Now assume that $ p\equiv-1\; (mod\; 3)$. Suppose that $ p\;\vert\; f(x,y)$ for some integers $ x$ and $ y$. In the view of the identity \[ f(x,y)=\left( x+\frac{y}{2}\right)+\frac{3}{4}y^{2}=\frac{1}{4}\left( (2x+y)^{2}+3y^{2}\right) ,\] we have \[ (2x+y)^{2}\equiv-3y^{2}\; (mod\; p).\] We first show that $ y$ is divisibly by $ p$. Assume to the contrary that $ y\not\equiv 0\; (mod\; p)$. Multiplying the inverse of $ y$ modulo $ p$, we obtain \[ (2xy^{-1}+1)^{2}\equiv-3\; (mod\; p).\] Since $ p\equiv-1\; (mod\; 3)$, we find that $ p\neq 3$ so that $ 2xy^{-1}+1\not\equiv 0\; (mod\; p)$. Hence, it says that $ -3$ is a quadratic residue modulo $ p$. Since $ p\equiv-1\; (mod\; 3)$, we apply Lemma 1.1 to obtain \[ \left(\frac{-3}{p}\right)=-1.\] This means that $ -3$ is a quadratic nonresidue modulo $ p$. This is a contradiction. We therefore conclude that $ y\equiv 0\; (mod\; p)$. It follows that $ 0\equiv f(x,y)\equiv x^{2}+xy+y^{2}\equiv x^{2}\; (mod\; p)$ so that $ x\equiv 0\; (mod\; p)$. Now, here goes the solution. Since the last digit of $ x^{2}+xy+y^{2}$ is zero, we find that $ x^{2}+xy+y^{2}$ is divisibly by $ 2\cdot 5$. Applying Proposition, we conclude that $ x^{2}+xy+y^{2}$ is divisibly by $ 2^{2}\cdot 5^{2}$ so that two lastdigits of $ x^{2}+xy+y^{2}$ are zeros.