Peter wrote: Let $A$ be the set of positive integers of the form $a^2 +2b^2$, where $a$ and $b$ are integers and $b \neq 0$. Show that if $p$ is a prime number and $p^2 \in A$, then $p \in A$. I was about to slay this using either the Thue theorem or properties of $\mathbb{Z}\left[\sqrt{-2}\right]$, as it is absolutely straightforward both of these ways, but then I noticed the "Romania 1997" in the source. Nice problem, I must say, would not some annoying casework mutilate the writeup. Lemma 1. If $w$ is an integer, and if two coprime positive integers $x$ and $y$ are such that $xy$ is a $w$-th power of a positive integer, then both $x$ and $y$ are $w$-th powers of positive integers. Proof of Lemma 1. Let $x=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ be the prime factorization of $x$, where all $p_i$ are distinct primes and all $a_i$ are positive integers for $i\in\left\{1;\;2;\;...;\;k\right\}$. Let $y=q_1^{b_1}q_2^{b_2}...q_l^{b_l}$ be the prime factorization of $y$, where all $q_j$ are distinct primes and all $b_j$ are positive integers for $j\in\left\{1;\;2;\;...;\l\right\}$. Then, $p_i\neq q_j$ for every $i\in\left\{1;\;2;\;...;\;k\right\}$ and every $j\in\left\{1;\;2;\;...;\l\right\}$ (else, the numbers $x$ and $y$ were not coprime!), so that the primes $p_1$, $p_2$, ..., $p_k$, $q_1$, $q_2$, ..., $q_l$ are all distinct. Hence, the number $xy=p_1^{a_1}p_2^{a_2}...p_k^{a_k}\cdot q_1^{b_1}q_2^{b_2}...q_l^{b_l}$ has the prime factorization $xy=p_1^{a_1}p_2^{a_2}...p_k^{a_k}q_1^{b_1}q_2^{b_2}...q_l^{b_l}$ (this sounds stupid now, doesn't it?). But since $xy$ is a $w$-th power of a positive integer, each prime factor in the prime factorization of $xy$ must appear with an exponent divisible by $w$; hence, all integers $a_1$, $a_2$, ..., $a_k$, $b_1$, $b_2$, ..., $b_l$ are divisible by $w$. Therefore, the numbers $x=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ and $y=q_1^{b_1}q_2^{b_2}...q_l^{b_l}$ are $w$-th powers of positive integers (since each prime factor in their prime factorizations appears with an exponent divisible by $w$). Lemma 1 is proven. Now let's solve the problem: Since $p^2\in A$, there exist two integers $u$ and $v$ such that $p^2=u^2+2v^2$ and $v\neq 0$. We can WLOG assume that $u$ and $v$ are both nonnegative (else, we can substitute $-u$ for $u$ or $-v$ for $v$ without changing much). Since $v\neq 0$, the nonnegativity of $v$ yields that $v$ is actually positive. The equation $p^2=u^2+2v^2$ becomes $p^2-u^2=2v^2$, what rewrites as $\left(p-u\right)\left(p+u\right)=2v^2$. Thus, $2\mid\left(p-u\right)\left(p+u\right)$. Since $2$ is prime, this yields that $2$ divides at least one of the integers $p-u$ and $p+u$. But if $2$ divides one of these integers $p-u$ and $p+u$, then $2$ also divides the other one, because $2$ divides the difference $\left(p+u\right)-\left(p-u\right)=2u$ of these integers. Thus, $2$ divides both integers $p-u$ and $p+u$. Hence, $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are integers. We have $p>u$, since $p^2=u^2+2v^2>u^2$ what is because $v$ is positive. The prime $p$ is odd. This is because else we would have $p=2$, so that $4=2^2=p^2=u^2+2v^2$, and thus $4\geq 2v^2$, so that $2\geq v^2$, and thus $v\leq\sqrt2$, so that $v=1$ (since $v$ is a positive integer, and the only positive integer $\leq\sqrt2$ is $1$), so that $4=u^2+2v^2=u^2+2\cdot 1^2=u^2+2$ yields $2=u^2$, what is impossible since $u$ is an integer and $2$ is not a square. Since $p$ is odd, $p^2$ must also be odd. Since $p^2=u^2+2v^2$, this yields that $u^2+2v^2$ is odd, so that $u^2$ is odd, so that $u$ is odd. Thus, $u\neq 0$. Since we know that $u$ is nonnegative, it hence follows that $u$ is positive. We also know that $v$ is positive. Assume that the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ have a common prime divisor $q$. Then, $q$ also divides $\frac{p-u}{2}+\frac{p+u}{2}=p$. Thus, $q$ is a prime divisor of $p$. Since $p$ is a prime, and thus the only prime divisor of $p$ is $p$ itself, this yields $q=p$. Hence, $p$ is a common prime divisor of $\frac{p-u}{2}$ and $\frac{p+u}{2}$. Therefore, $p$ also divides $\frac{p+u}{2}-\frac{p-u}{2}=u$. Since $u$ is positive, this yields $u\geq p$. This contradicts with $p>u$. Hence, our assumption that the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ have a common prime divisor was wrong. Hence, the two integers $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are coprime. Now, we divide the equation $\left(p-u\right)\left(p+u\right)=2v^2$ by $4$ and obtain $\frac{p-u}{2}\cdot\frac{p+u}{2}=\frac{v^2}{2}$. Since $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are integers, this yields that $\frac{v^2}{2}$ is an integer, so that $v^2$ is even, so that $v$ is even, and thus $v=2V$ for some integer $V$. Since $v$ is positive, it follows that $V$ is positive as well. Thus, $\frac{p-u}{2}\cdot\frac{p+u}{2}=\frac{v^2}{2}=\frac{\left(2V\right)^2}{2}=2V^2$. Hence, $2\mid\frac{p-u}{2}\cdot\frac{p+u}{2}$. Since $2$ is a prime, it thus follows that $2$ divides at least one of the numbers $\frac{p-u}{2}$ and $\frac{p+u}{2}$. We will only deal with the case when $2$ divides $\frac{p-u}{2}$; the case when $2$ divides $\frac{p+u}{2}$ is analogous and left to the reader. Since $2$ divides $\frac{p-u}{2}$, the number $\frac{p-u}{2}/2=\frac{p-u}{4}$ is an integer; besides, it is positive (since $p>u$). Now, dividing the equation $\frac{p-u}{2}\cdot\frac{p+u}{2}=2V^2$ by $2$, we get $\frac{p-u}{4}\cdot\frac{p+u}{2}=V^2$. Now, $\frac{p-u}{4}$ and $\frac{p+u}{2}$ are two coprime positive integers (in fact, we know that they are positive integers, and they are coprime because $\frac{p-u}{2}$ and $\frac{p+u}{2}$ are coprime). Since $\frac{p-u}{4}\cdot\frac{p+u}{2}=V^2$ is the $2$-nd power of a positive integer, Lemma 1 thus yields that both $\frac{p-u}{4}$ and $\frac{p+u}{2}$ are $2$-nd powers of positive integers. Hence, there exist positive integers $\lambda$ and $\mu$ such that $\frac{p-u}{4}=\lambda^2$ and $\frac{p+u}{2}=\mu^2$. Thus, $p=\frac{p+u}{2}+2\cdot\frac{p-u}{4}=\mu^2+2\lambda^2$. Since $\lambda\neq 0$ (because $\lambda$ is positive), this yields $p\in A$, and the problem is solved. Darij

That's nice and systematic solution darij grinberg! (7 out of 7 points :smile: ).

Peter wrote: Let $ A$ be the set of positive integers of the form $ a^{2}+2b^{2}$, where $ a$ and $ b$ are integers and $ b\neq 0$. Show that if $ p$ is a prime number and $ p^{2}\in A$, then $ p\in A$. We assume that $ p > 2$. We use \textsc{Thue's Lemma}. Thue's Lemma Let $ p$ be a prime number and let $ \alpha$ be an integer with $ \alpha\not\equiv 0\; (mod\; p)$. Then, the congruence $ \alpha x\equiv y\; (mod\; p)$ admits a solution $ (x, y)$ with $ \vert x\vert ,\vert y\vert\in\left( 0,\sqrt{p}\right)$. Proof Let $ \mathcal{S}=\{ (i,j)\;\vert\; i,j\in\{ 0,\cdots,\lfloor\sqrt{p}\rfloor\}\,\}$ and $ \mathcal{T}=\{0,\cdots, p-1\}$. The key idea is to introduce the function $ f :\mathcal{S}\rightarrow\mathcal{T}$ defined by \[ f(i,j)=\mathbf{r}_{p}\left(\alpha i-j\right),\] where $ \mathbf{r}_{p}(n)$ denotes the remainder in the division of $ n$ by $ p$. Since $ \left\vert\mathcal{S}\right\vert =\left(\lfloor\sqrt{p}\rfloor+1\right)^{2}> p =\left\vert\mathcal{T}\right\vert$, by Pigeonhole Principle, $ f$ is not injective. In other words, we have \[ f\left(i_{1},j_{1}\right)=f\left(i_{2},j_{2}\right)\] or \[ \alpha i_{1}-j_{1}\equiv\alpha i_{2}-j_{2}\; (mod\; p)\] or \[ \alpha\left( i_{1}-i_{2}\right)\equiv j_{1}-j_{2}\; (mod\; p)\] for some \textit{distinct} elements $ \left(i_{1}, j_{1}\right)$ and $ \left(i_{2}, j_{2}\right)$ in $ \mathcal{S}$. Setting $ i = i_{1}-i_{2}$ and $ j = j_{1}-j_{2}$, it becomes \[ \alpha i\equiv j\; (mod\; p).\] Since $ i_{1},j_{1}, i_{2}, j_{2}\in\{ 0,\cdots,\lfloor\sqrt{p}\rfloor\}$, we see that $ \vert i\vert =\vert i_{1}-i_{2}\vert <\sqrt{p}$ and $ \vert j\vert =\vert j_{1}-j_{2}\vert <\sqrt{p}$. It remains to check that both $ i$ and $ j$ are nonzero. Step 1. $ i\neq 0$: Assume to the contrary that $ i$ is zero. Then the congruence $ \alpha i\equiv j\; (mod\; p)$ implies that $ 0\equiv j\; (mod\; p)$. Since $ \vert j\vert <\sqrt{p}< p$, this means that $ j$ is also zero. In other words, we get $ i_{1}= i_{2}$ and $ j_{1}= j_{2}$. This is a contradiction because $ \left(i_{1}, j_{1}\right)$ and $ \left(i_{2}, j_{2}\right)$ are distinct. Step 2. $ j\neq 0$: Assume to the contrary that $ j$ is zero. It follows that $ \alpha i\equiv j\equiv 0\; (mod\; p)$. Since $ \alpha\not\equiv 0\; (mod\; p)$ and since $ p$ is prime, this implies that $ i\equiv 0\; (mod\; p)$. Since $ \vert i\vert <\sqrt{p}< p$, this means that $ i$ is also zero. In other words, we get $ i_{1}= i_{2}$ and $ j_{1}= j_{2}$. This is a contradiction because $ \left(i_{1}, j_{1}\right)$ and $ \left(i_{2}, j_{2}\right)$ are distinct. Now, suppose that $ p^{2}\in A$. Write $ p^{2}= a^{2}+2b^{2}$ for some positive integers $ a$ and $ b$. Reading the equation modulo $ p$ yields $ a^{2}\equiv-2 b^{2}\; (mod\; p)$. Multiplying the inverse of $ b$ modulo $ p$,\footnote{ It's clear that $ b < p$ so that $ b$ is not divisible $ p$.} we get \[ \left( a b^{-1}\right)^{2}\equiv-2\; (mod\; p).\] Taking $ \alpha\equiv a b^{-1}\; (mod\; p)$ in Thue's Lemma, we can find a pair $ (m,n)$ of integers satisfying that $ n\equiv\alpha m\; (mod\; p)$ and $ 0 <\vert m\vert ,\vert n\vert <\sqrt{p}$. After squaring the congruence, we have \[ n^{2}\equiv{\alpha}^{2}{m}^{2}\equiv-2m^{2}\; (mod\; p).\] In other words, $ n^{2}+2m^{2}$ is divisible by $ p$. Since $ 0 <\vert m\vert ,\vert n\vert <\sqrt{p}$ or since $ 0 < n^{2}+2m^{2}< 3p$, this means that $ n^{2}+2m^{2}$ is $ p$ or $ 2p$. In case when $ p = n^{2}+2m^{2}$, it is clear that $ p\in A$. In case when $ 2p = n^{2}+2m^{2}$, we see that $ n$ is even so that $ p = m^{2}+2\left(\frac{n}{2}\right)^{2}\in A$.

$ p^{2} = a^{2} + 2b^{2}$ , has solutions $ a , b$ in integers . We have to prove that $ p$ can be represented in such a form . $ p^{2} = a^{2} + 2b^{2} \equiv 0 \bmod{p}$ $ \implies a^{2} \equiv - 2b^{2} \bmod{p}$ This implies $ - 2b^{2}$ is a quadratic residue $ \bmod{p}$ , so $ \left(\frac { - 2b^{2}}{p} \right) = 1$ $ \left(\frac { - 2b^{2}}{p} \right) = \left(\frac { - 2}{p} \right)\left(\frac {b^{2}}{p} \right) = 1$ $ \implies \left(\frac { - 2}{p} \right) = 1$ ,thus $ - 2$ is a quadratic residue modulo $ p$ . Lemma $ - 2$ is a quadratic residue modulo $ p$ if and only if $ p \equiv 1\bmod{8}$ or $ p \equiv 3 \bmod{8}$ The proof is easy by considering that $ \left(\frac { - 2}{p} \right) = \left(\frac {2}{p} \right)\left(\frac { - 1}{p} \right)$ and $ \left(\frac {2}{p} \right) = ( - 1)^{\frac {p^{2} - 1 }{8}}$ Thus from the lemma it follows that $ p = 8k + 1$ or $ p = 8k + 3$ ,and we know that any prime $ p$ of the form $ 8k + 1$ or $ 8k + 3$ can be represented in the form $ x^{2} + 2y^{2}$ where $ x$ and $ y$ are positive integers . Thus the proof follows . Sorry if the proof is wrong ,or resembles that of Darij

It's not wrong, but have fun with proving the fact that srinath.r wrote: any prime $ p$ of the form $ 8k + 1$ or $ 8k + 3$ can be represented in the form $ x^{2} + 2y^{2}$ where $ x$ and $ y$ are positive integers - it is about ten times as difficult as the original problem. The formula for $ \left(\frac 2 p\right)$ that you are using is not quite a piece of cake either. darij

darij grinberg wrote: It's not wrong, but have fun with proving the fact that srinath.r wrote: any prime $ p$ of the form $ 8k + 1$ or $ 8k + 3$ can be represented in the form $ x^{2} + 2y^{2}$ where $ x$ and $ y$ are positive integers - it is about ten times as difficult as the original problem. The formula for $ \left(\frac 2 p\right)$ that you are using is not quite a piece of cake either. darij You are 100% right , couldnt think of a solution like yours ,yours was really superb and detailed.

This is the $\mathbb{Z}[\sqrt{-2}]$ method that darij mentioned. $a^2+2b^2=p^2$ is given. We work in $\mathbb{Z}[\sqrt{-2}]$ which is a Unique Factorization Domain. We arrive at \[(a+\sqrt{-2}b)(a-\sqrt{-2}b)=p^2\] Notice that $\gcd(a+b\sqrt{-2}, a-b\sqrt{-2})|2a, 2\sqrt{-2}b$. However since $p$ is prime $\gcd(a,b)=1$ therefore $\gcd(a+b\sqrt{-2}, a-b\sqrt{-2})|2\sqrt{-2}=\left(\sqrt{-2}\right)^3$. Notice that $\sqrt{-2}|\gcd(a+b\sqrt{-2}, a-b\sqrt{-2})$ implies that \[\frac{a+b\sqrt{-2}}{\sqrt{-2}}\in \mathbb{Z}[\sqrt{-2}]\] However, this implies that $a\equiv 0\pmod{2}$ which contradicts $p$ being prime. Therefore \[\gcd(a+b\sqrt{-2}, a-b\sqrt{-2})=1\] Since $(a+\sqrt{-2}b)(a-\sqrt{-2}b)$ this implies that $a+b\sqrt{-2}=uz^2, a-b\sqrt{-2}=\bar{u}\bar{z}^2$ where $u$ is a unit in $\mathbb{Z}[\sqrt{-2}]$. However, the units are $\pm 1$ because $\text{norm}\left(x+y\sqrt{-2}\right)=x^2+2y^2=1\iff x=\pm 1$. Since $-1=i^2$ we can write this as $\begin{cases} a+b\sqrt{-2}=z^2\\ a-b\sqrt{-2}=\bar{z}^2 \end{cases}$ By multiplying the two equations above we arrive at $\left(z\bar{z}\right)^2=p^2\implies z\bar{z}=p$. Write $z$ in the form $m+n\sqrt{-2}$ gives us \[p=\left(m+n\sqrt{-2}\right)\left(m-n\sqrt{-2}\right)=m^2+2n^2\]

Is $ \mathbb{Z}[\sqrt{-2}] $ really unique factorization domain? I've heard about $ \mathbb{Z}[i] $ and $ \mathbb{Z}[\omega] $, but i thought that there are problems in the rest. Where could I found out something more about it? Thank you and sorry if my question is stupid

A completely different approach (based on Euler's method to find all rational solutions of some Diophantine equations). Write $a^2 + 2b^2 = p^2$, with $a,b \in \mathbb{N}$, $b \neq 0$, as $X^2 + 2Y^2 = 1$, where $X=a/p$, $Y=b/p$. We will find all rational solutions for this equation. The trivial solution $(X,Y) = (1,0)$ hints to substituting $X = 1-A$, $Y = B$, and so $A^2 + 2B^2 - 2A = 0$. Since we look for rational solutions, take $B=\lambda A$, where $\lambda = d/c \in \mathbb{Q}^*$, $\gcd(c,d)=1$ ($\lambda = 0$ leads to $X=-1$, $b/p = Y = 0$, which is anyways forbidden ($b\neq 0$)). Then $A((1+2\lambda^2)A - 2) = 0$; The case $A=0$ leads to $X=1$, $b/p = Y = 0$, which is anyways forbidden ($b\neq 0$), so assume $A\neq 0$. Then $A = \dfrac {2} {1+2\lambda^2}$, $B = \dfrac {2\lambda} {1+2\lambda^2}$, thus $X = \dfrac {2\lambda^2 - 1} {1+2\lambda^2} = \dfrac {2d^2 - c^2} {c^2+2d^2}$, $Y = \dfrac {2\lambda} {1+2\lambda^2} = \dfrac {2cd} {c^2+2d^2}$. Finally, this yields $(2d^2 - c^2)^2 + 2(2cd)^2 = (c^2+2d^2)^2$, this being the complete parameterized set of solutions for $a^2 + 2b^2 = p^2$ and $\gcd(a,b)=1$. But this is precisely the case, since $p$ being prime we cannot have $\gcd(a,b)>1$ (it will then have to be equal to $p$, and that forces $b=0$, forbidden). We have thus painlessly obtained $p = c^2 + 2d^2$, of the required representation.

@Radar: Yes there are actually quite a lot of Euclidean domains which all can be found here. A nice article online on this topic is here. Private message me your email address and I can share some notes from a class I took, but please do not post them publicly (the teacher is OK with private sharing of the notes).