Let $n$ be a positive integer. Prove that every prime $p > 2$ that divides $(2-\sqrt{3})^n + (2+\sqrt{3})^n$ satisfy $p=1 (mod3)$
Problem
Source: Israel 2018 Olympic Revenge
Tags: prime numbers, Divisibility, number theory, Divisors
naman12
22.03.2020 05:13
Did you mean $p>2$. Otherwise $p=2\mid (2-\sqrt{3})+(2+\sqrt{3})$.
shalomrav
23.03.2020 09:10
Bump....
nukelauncher
23.03.2020 09:47
Suppose for sake of contradiction that $p$ is an odd prime such that $p\equiv 2\pmod3$ and $p\mid (2-\sqrt3)^n+(2+\sqrt3)^n$. (The case $p=3$ can be easily eliminated.)
Case 1: $p\equiv 1\pmod4$.
In this case, we have \[\left(\frac3p\right) =\left(\frac p3\right)=\left(\frac23\right)=-1.\]Thus, 3 is not a QR modulo $p$. We also have $\left(\frac{-1}p\right)=1$, i.e. -1 is a QR modulo $p$. Then we have \[(2-\sqrt3)^n+(2+\sqrt3)^n\equiv 0\pmod p\iff (2-\sqrt3)^n\equiv -(2+\sqrt3)^n\pmod p\iff (2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p.\]Consider the equation $x^2+1=0$ in $\mathbb{F}_p\left[\sqrt 3\right]$. Since $-1$ is a QR, there exists 2 roots of $x^2+1=0$ in $\mathbb{F}_p$. However, $x^2+1=0$ also has the roots $(2-\sqrt3)^n$ and $(2+\sqrt3)^n$, so this is a breach of Lagrange's theorem ($x^2+1$ is degree 2 but has 4 roots), i.e. $\mathbb{F}_p\left[\sqrt 3\right]$ is not a field. However, this is a contradiction to 3 being a QNR modulo $p$.
Case 2: $p\equiv 3\pmod4$.
In this case, we have \[\left(\frac3p\right) =-\left(\frac p3\right)=-\left(\frac23\right)=1.\]Thus, 3 is a QR modulo $p$. We also have $\left(\frac{-1}p\right)=-1$, i.e. -1 is not a QR modulo $p$. But as before, we reach the equation \[(2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p\]which is a contradiction to $-1$ being a QNR (since $(2-\sqrt3)^n, (2+\sqrt3)^n\in \mathbb{F}_p$ as 3 is a QR and they are "square roots" of -1).
shalomrav
23.03.2020 17:18
Great solution! Previously i didn't understand your solution because i didn't notice $2-\sqrt{3} = (2+\sqrt{3} )^{-1}$
Mathhunter1
23.03.2020 19:12
nukelauncher wrote:
Suppose for sake of contradiction that $p$ is an odd prime such that $p\equiv 2\pmod3$ and $p\mid (2-\sqrt3)^n+(2+\sqrt3)^n$. (The case $p=3$ can be easily eliminated.)
Case 1: $p\equiv 1\pmod4$.
In this case, we have \[\left(\frac3p\right) =\left(\frac p3\right)=\left(\frac23\right)=-1.\]Thus, 3 is not a QR modulo $p$. We also have $\left(\frac{-1}p\right)=1$, i.e. -1 is a QR modulo $p$. Then we have \[(2-\sqrt3)^n+(2+\sqrt3)^n\equiv 0\pmod p\iff (2-\sqrt3)^n\equiv -(2+\sqrt3)^n\pmod p\iff (2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p.\]Consider the equation $x^2+1=0$ in $\mathbb{F}_p\left[\sqrt 3\right]$. Since $-1$ is a QR, there exists 2 roots of $x^2+1=0$ in $\mathbb{F}_p$. However, $x^2+1=0$ also has the roots $(2-\sqrt3)^n$ and $(2+\sqrt3)^n$, so this is a breach of Lagrange's theorem ($x^2+1$ is degree 2 but has 4 roots), i.e. $\mathbb{F}_p\left[\sqrt 3\right]$ is not a field. However, this is a contradiction to 3 being a QNR modulo $p$.
Case 2: $p\equiv 3\pmod4$.
In this case, we have \[\left(\frac3p\right) =-\left(\frac p3\right)=-\left(\frac23\right)=1.\]Thus, 3 is a QR modulo $p$. We also have $\left(\frac{-1}p\right)=-1$, i.e. -1 is not a QR modulo $p$. But as before, we reach the equation \[(2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p\]which is a contradiction to $-1$ being a QNR (since $(2-\sqrt3)^n, (2+\sqrt3)^n\in \mathbb{F}_p$ as 3 is a QR and they are "square roots" of -1).
This is a beautiful solution , but I had to fix a little bit. In Case 1, $(2+\sqrt 3)^n$ should be a different value with the root in $\mathbb{F}_p$. So, when we let $(2+\sqrt 3)^n = a + b \sqrt 3$ , we should show that $p$ doesn't divide $b$. as $p \vert (2-\sqrt{3})^n + (2+\sqrt{3})^n= 2a$ , we only need to show that $gcd(a, b) = 1$. $(2+\sqrt{3})^n = a+ b \sqrt 3 \;, (2-\sqrt{3})^n = a - b \sqrt 3 \Rightarrow a^2 - 3b^2 = 1$ , which guarantees $gcd(a, b) = 1$ .
shalomrav
23.03.2020 19:52
Mathhunter1 wrote: nukelauncher wrote:
Suppose for sake of contradiction that $p$ is an odd prime such that $p\equiv 2\pmod3$ and $p\mid (2-\sqrt3)^n+(2+\sqrt3)^n$. (The case $p=3$ can be easily eliminated.)
Case 1: $p\equiv 1\pmod4$.
In this case, we have \[\left(\frac3p\right) =\left(\frac p3\right)=\left(\frac23\right)=-1.\]Thus, 3 is not a QR modulo $p$. We also have $\left(\frac{-1}p\right)=1$, i.e. -1 is a QR modulo $p$. Then we have \[(2-\sqrt3)^n+(2+\sqrt3)^n\equiv 0\pmod p\iff (2-\sqrt3)^n\equiv -(2+\sqrt3)^n\pmod p\iff (2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p.\]Consider the equation $x^2+1=0$ in $\mathbb{F}_p\left[\sqrt 3\right]$. Since $-1$ is a QR, there exists 2 roots of $x^2+1=0$ in $\mathbb{F}_p$. However, $x^2+1=0$ also has the roots $(2-\sqrt3)^n$ and $(2+\sqrt3)^n$, so this is a breach of Lagrange's theorem ($x^2+1$ is degree 2 but has 4 roots), i.e. $\mathbb{F}_p\left[\sqrt 3\right]$ is not a field. However, this is a contradiction to 3 being a QNR modulo $p$.
Case 2: $p\equiv 3\pmod4$.
In this case, we have \[\left(\frac3p\right) =-\left(\frac p3\right)=-\left(\frac23\right)=1.\]Thus, 3 is a QR modulo $p$. We also have $\left(\frac{-1}p\right)=-1$, i.e. -1 is not a QR modulo $p$. But as before, we reach the equation \[(2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p\]which is a contradiction to $-1$ being a QNR (since $(2-\sqrt3)^n, (2+\sqrt3)^n\in \mathbb{F}_p$ as 3 is a QR and they are "square roots" of -1).
This is a beautiful solution , but I had to fix a little bit. In Case 1, $(2+\sqrt 3)^n$ should be a different value with the root in $\mathbb{F}_p$. So, when we let $(2+\sqrt 3)^n = a + b \sqrt 3$ , we should show that $p$ doesn't divide $b$. as $p \vert (2-\sqrt{3})^n + (2+\sqrt{3})^n= 2a$ , we only need to show that $gcd(a, b) = 1$. $(2+\sqrt{3})^n = a+ b \sqrt 3 \;, (2-\sqrt{3})^n = a - b \sqrt 3 \Rightarrow a^2 - 3b^2 = 1$ , which guarantees $gcd(a, b) = 1$ . Why we should prove that? we know $(2-\sqrt{3})^{n} * (2+\sqrt{3})^n = 1$ so obviously $(2+\sqrt{3})^n $ is not $0 \pmod p$
nukelauncher
23.03.2020 20:57
shalomrav wrote: Mathhunter1 wrote: nukelauncher wrote:
Suppose for sake of contradiction that $p$ is an odd prime such that $p\equiv 2\pmod3$ and $p\mid (2-\sqrt3)^n+(2+\sqrt3)^n$. (The case $p=3$ can be easily eliminated.)
Case 1: $p\equiv 1\pmod4$.
In this case, we have \[\left(\frac3p\right) =\left(\frac p3\right)=\left(\frac23\right)=-1.\]Thus, 3 is not a QR modulo $p$. We also have $\left(\frac{-1}p\right)=1$, i.e. -1 is a QR modulo $p$. Then we have \[(2-\sqrt3)^n+(2+\sqrt3)^n\equiv 0\pmod p\iff (2-\sqrt3)^n\equiv -(2+\sqrt3)^n\pmod p\iff (2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p.\]Consider the equation $x^2+1=0$ in $\mathbb{F}_p\left[\sqrt 3\right]$. Since $-1$ is a QR, there exists 2 roots of $x^2+1=0$ in $\mathbb{F}_p$. However, $x^2+1=0$ also has the roots $(2-\sqrt3)^n$ and $(2+\sqrt3)^n$, so this is a breach of Lagrange's theorem ($x^2+1$ is degree 2 but has 4 roots), i.e. $\mathbb{F}_p\left[\sqrt 3\right]$ is not a field. However, this is a contradiction to 3 being a QNR modulo $p$.
Case 2: $p\equiv 3\pmod4$.
In this case, we have \[\left(\frac3p\right) =-\left(\frac p3\right)=-\left(\frac23\right)=1.\]Thus, 3 is a QR modulo $p$. We also have $\left(\frac{-1}p\right)=-1$, i.e. -1 is not a QR modulo $p$. But as before, we reach the equation \[(2-\sqrt3)^{2n}\equiv (2+\sqrt3)^{2n}\equiv -1\pmod p\]which is a contradiction to $-1$ being a QNR (since $(2-\sqrt3)^n, (2+\sqrt3)^n\in \mathbb{F}_p$ as 3 is a QR and they are "square roots" of -1).
This is a beautiful solution , but I had to fix a little bit. In Case 1, $(2+\sqrt 3)^n$ should be a different value with the root in $\mathbb{F}_p$. So, when we let $(2+\sqrt 3)^n = a + b \sqrt 3$ , we should show that $p$ doesn't divide $b$. as $p \vert (2-\sqrt{3})^n + (2+\sqrt{3})^n= 2a$ , we only need to show that $gcd(a, b) = 1$. $(2+\sqrt{3})^n = a+ b \sqrt 3 \;, (2-\sqrt{3})^n = a - b \sqrt 3 \Rightarrow a^2 - 3b^2 = 1$ , which guarantees $gcd(a, b) = 1$ . Why we should prove that? we know $(2-\sqrt{3})^{n} * (2+\sqrt{3})^n = 1$ so obviously $(2+\sqrt{3})^n $ is not $0 \pmod p$ Mathhunter1 is right. He is saying that I should have elaborated on why $(2\pm\sqrt3)^n\not\in\mathbb{F}_p$.
TheUltimate123
24.03.2020 03:05
Let $\textstyle K=(2-\sqrt3)^n+(2+\sqrt3)^n$. Consider: \begin{align*} K&=\left(\frac{\sqrt6-\sqrt2}2\right)^{2n}+\left(\frac{\sqrt6+\sqrt2}2\right)^{2n}.\\ L&:=2^nK=\left(\sqrt3-1\right)^{2n}+\left(\sqrt3+1\right)^{2n}. \end{align*}We are limiting $p$ that divide $L$. Binomial theorem settles $p=3$, so for contradiction $p>3$ divides $L$ and $p\equiv2\pmod3$. Note that \[\left(\frac3p\right)=(-1)^{\frac{p-1}2}\left(\frac p3\right)=-(-1)^{\frac{p-1}2}=-\left(\frac{-1}p\right).\]If $p\equiv3\pmod4$, then $3$ is a quadratic residue and $L$ is the sum of two squares in $\mathbb F_p$, impossible by Christmas. Now we will assume $p\equiv1\pmod4$. Work in $\mathbb F_{p^2}$, the $\mathbb F_p$-splitting field of $X^2-2X-2$. Then \[-1=\left(\frac{\sqrt3+1}{\sqrt3-1}\right)^{2n}=\left(2+\sqrt3\right)^{2n}\]Thus $\textstyle(2+\sqrt3)^n=\pm1$. But note that \[\left(2+\sqrt3\right)^n\left(2-\sqrt3\right)^n=1\implies\left(2-\sqrt3\right)^n=\left(2+\sqrt3\right)^n\]absurd since $K=0$.