Find all pairs $(p,q)$ of prime numbers, such that $2p-1$, $2q-1$, $2pq-1$ are perfect square. F. Petrov, A. Smirnov
Problem
Source:
Tags: number theory proposed, number theory
19.04.2014 14:11
dear mathlinkers, Who can give complete solution?
22.04.2014 21:30
This problem appears to be too much difficult.
13.10.2017 19:39
So there exist odd positive integers $x,y,z$ that $p=\frac{x^2+1}{2},q=\frac{y^2+1}{2}$ and $pq=\frac{z^2+1}{2}=\frac{(x^2+1)(y^2+1)}{4}$. We get that $$pq=\left( \frac{z+1}{2}\right)^2+\left( \frac{z-1}{2}\right)^2=\left( \frac{x+y}{2}\right)^2+\left( \frac{xy-1}{2}\right)^2=\left( \frac{x-y}{2}\right)^2+\left( \frac{xy+1}{2}\right)^2.$$Not hard to see that product of two prime numbers can be written as sum of two squares in at most two ways. So we get that $\{ z+1,z-1\} =\{ x+y,xy-1\}$ or $\{ z+1,z-1\} =\{ x-y,xy+1\}$ or $\{ x+y,xy-1\} =\{ x-y,xy+1\} $ (note that $z+1>z-1$ and $xy+1>x>x-y$). Hence $|xy-x-y-1|=2$ or $|xy-x+y-1|=2$ or $x+y=xy+1,xy-1=x-y$. The rest is easy.
21.05.2019 04:32
ThE-dArK-lOrD wrote: Not hard to see that product of two prime numbers can be written as sum of two squares in at most two ways. Whoops I found this to be quite nontrivial and fun to prove, so I'll write a proof of that here. First, we'll prove that primes can be expressed in at most one way. Lemma. Every prime can be expressed in at most one way as a sum of two squares. Proof. Suppose, for contradiction, that $a^2 + b^2 = c^2 + d^2 = p$, for some prime $p$ and some positive integers $a, b, c, d$ where $\{a, b\} \neq \{c, d\}.$ Then, we know that $p \equiv 1$ (mod $4$), and so WLOG let's say that $a, c$ are even and $b, d$ are odd. We know that $a \neq c, b \neq d$. Observe that $(a-d)(a+d) = (c-b)(c+b)$, so that we have odd integers $x = a-d, y = a+d, z = c-b, w = c+b$ with $xy = zw$, $x \neq z$, $y \neq w$. Hence, by the Four Number Theorem, there exist odd positive integers so that $x = \alpha \beta, y = \gamma \delta, z = \alpha \gamma, w = \beta \delta.$ However, we know that $p = \frac{(2a)^2 + (2b)^2}{4} = \frac{(x+y)^2 + (z-w)^2}{4} = \frac{x^2 + y^2 + z^2 + w^2}{4},$ where we used that $xy = zw.$ Therefore, we have that $p = \frac{x^2 + y^2 + z^2 + w^2}{4} = \frac{(\alpha^2 + \delta^2)(\beta^2 + \gamma^2)}{4} = \frac{\alpha^2 + \delta^2}{2} \cdot \frac{\beta^2 + \gamma^2}{2}.$ However, we cannot have $\alpha = \delta = 1$ since that would give us $y=z, x=w \Leftrightarrow a+d = c-b, c+b = a-d$ which is absurd. We get a similar absurdity if $\beta = \gamma = 1$, and so the lemma is proven now since $\frac{\alpha^2 + \delta^2}{2}, \frac{\beta^2 + \gamma^2}{2} >1$ and multiply to $p$, a clear contradiction. $\blacksquare$ With a similar tactic, we can now finish the proof. Again, suppose that $a^2 + b^2 = c^2 + d^2 = pq$, where $a, c$ are even and $b, d$ are odd. We then have that $(a-c)(a+c) = (b-d)(b+d)$, and so we can set $x, y, z, w$ to be even integers corresponding to $a-c, a+c, d-b, d+b$. We again have $xy = zw$ and $pq = \frac{x^2 + y^2 + z^2 + w^2}{4} = \frac{x}{2}^2 + \frac{y}{2}^2 + \frac{z}{2}^2 + \frac{w}{2}^2.$ Now, apply the Four Number Theorem on $\frac{x}{2}^2, \frac{y}{2}^2, \frac{z}{2}^2, \frac{w}{2}^2$ to factor $\frac{x}{2}^2 + \frac{y}{2}^2 + \frac{z}{2}^2 + \frac{w}{2}^2$ as a product of two sums of squares. However, we are now happy, since we know from the lemma that there are only two ways to pick $x, y, z, w$ up to symmetry (e.g. $y, x, w, z$ is the exact same thing). $\square$
04.02.2020 11:41
Another interesting result (which can also be proved elementary techniques) is: If natural $n$ can be expressed as the sum of two squares in two different ways, ie. $n=a^2+b^2=c^2+d^2,$ then $n$ can be written as the product of two sums of squares, ie. $n=(w^2+x^2)(y^2+z^2).$
04.02.2020 12:41
There is more complicated one : https://artofproblemsolving.com/community/c6t177f6h2000319_pqrs2_p2_q2_r2_s2_are_squares_of_integer Anyway, here is my solution : WLOG, suppose that $p\geq q$. Suppose that $2pq-1=x^{2}$, $2p-1=y^{2}$, and $2q-1=z^{2}$ for some $( x,y,z) \in \mathbb{N}^{3}$. If $q=2$, then $3=z^{2}$, impossible. Henceforth, suppose that $q >2$. $( x+y)( x-y) =x^{2} -y^{2} =2p( q-1)$. Since $x+y\equiv x-y\pmod 2$, we must have $2\mid x+y,x-y$. So we have $( x+y) /2\cdotp ( x-y) /2=p( q-1) /2$. Note that we must have that either $2p \mid x+y$ $\quad$ or $\quad$ $2p \mid x-y$. Since $x^{2} < x^{2} +1=2pq\leq 2p^{2}$, we have $x\leq p\sqrt{2}$. Since $0< x-y< x< 2p$, we must have $2p\mid x+y$. Since $y^{2} +1=2p >y^{2}$, we have $y< \sqrt{2p}$. So we have $2p\leq x+y< p\sqrt{2} +\sqrt{2p}$. It follows that $\left( 2-\sqrt{2}\right) p< \sqrt{2p}$, which implies $\sqrt{p} < 1+\sqrt{2} < 5/2$. So we must have $p< 25/4< 7$. If $p=3$, then $5=y^{2}$, impossible. So we must have $p=5$. If $q=3$, then $5=z^{2}$, impossible. So we must have $q=5$. Conversely, $( p,q) =( 5,5$) satisfies the condition : $2pq-1=7^{2}$, $2p-1=2q-1=3^{2}$. Hence the answer is $( p,q) =( 5,5)$.
04.02.2020 17:23
Pathological wrote: ThE-dArK-lOrD wrote: Not hard to see that product of two prime numbers can be written as sum of two squares in at most two ways. Whoops I found this to be quite nontrivial and fun to prove, so I'll write a proof of that here. First, we'll prove that primes can be expressed in at most one way. Perhaps what the ThE-dArK-lOrD had in mind was to use unique factorization over $\mathbb{Z}[i]$, which yields a simple proof.
04.02.2020 23:01
using @above: Quote: A prime number $p$ can be written as sum of squares in at most one way. We use Gaussian integers. Suppose $N(\alpha)=p$ for some gaussian $\alpha,$ and $N(\cdot)$ denotes norm. Then, if $\alpha = \beta \cdot \gamma,$ we have $N(\alpha) = N(\beta)N(\gamma)=p,$ but then one of $N(\beta)$ or $N(\gamma)$ must be one and other is $p,$ so this means $\alpha$ has no nontrivial gaussian factors, so it is gaussian prime. Now, suppose $p=a^2+b^2=c^2+d^2.$ We then have $N(a+bi)=N(a-bi)=N(c+di)=N(c-di)=p,$ so all of $a+bi,a-bi,c+di,c-di$ are gaussian prime. It then follows by unique factorization that either $a+bi=u(c+di),$ or $a-bi=u(c-di),$ where $u$ is a gaussian unit (ie. $1,-1,i,-i$) We can check in each case that they give the same $a^2+b^2=c^2+d^2.$
17.08.2021 18:49
Let $2p-1=a^2,2q-1=b^2,2pq-1=c^2$ for some $(a,b,c) \in \mathbf{Z}^+$ Then $p|a^2+1$ and $p|c^2+1$,hence $p|c+a$ or $p|c-a$ Since $a,c,p \in \mathbf{2Z+1}$,$2p \le a+c$ and with a similar argument $2q \le b+c$ Or in other words,$c \ge 2p-a$ and $c \ge 2p-b$ But then,$2q-1=c^2>(2p-a)(2q-b)=4pq-2pb-2qa+ab$ which becomes $2q+1+ab \le 2qb+2qa$ Note that $pq<pb+qa$,hence $1<\frac{b}{q}+\frac{a}{p}<\sqrt{\frac{2}{q}}+\sqrt{\frac{2}{p}}$ By the symmetry,assume that $p \le q$ and the previous inequality yeilds $p,q \le 7$,and testing all possibilities we get $(p,q)=(5,5)$ to be the only solution.
10.03.2024 18:01
Here is my solution. We have, $2p - 1 = a^2, 2q - 1 = b^2, 2pq - 1 = c^2 (a,b,c \in \mathbb{Z}^+)$ WLOG, $p\ge q$, then $a \ge b$ Minus 2 equation we have, $c^2-a^2 = 2pq - 2p = 2p(q-1) = (c-a)(c+a)$ We have two cases Case 1: $c-a \vdots p$ We have $c^2 = 2pq - 1 \le 2p^2 - 1 < 4p^2$ then $c < 2p$ $c^2 = 2pq - 1 > 2p -1 = a^2$ then $c>a$ So $0 < c-a < c < 2p$. So we have $c-a = p$ Then we have $c+a = 2(q-1)$. Adding two equation, we have $2c = p + 2(q-1)$ then $p$ is even so $p=2$ We have $c = q$. Subsitute back, we have $2pq - 1 = q^2$ then $q(2p-q)=1$, but we have $q(2p-q) = q(p+p-q) \ge 2.2 = 4 > 1$ (contradiction) Case 2: $ c+a \vdots p $ We have $a^2 = 2p -1 < p^2$ so $a<p$ Then we have $0<c+a < 2p + p = 3p$. We have 2 cases: Cases 2a: $c+a=p$ Subsitute back we have, $c-a = 2(q-1)$ Add two equation we have $2c = p + 2(q-1)$ so $p$ is even then $p=2$. So $c=a=1$. Then $p = 1$ (contradiction) Cases 2b: $c+a = 2p$ Subsitute back we have $c-a = q-1$ Add two equation, we have $2c = 2p+q-1$ From $2pq - 1= c^2$ we have $8pq - 4 = 4c^2 = (2p+q-1)^2 \Leftrightarrow 4p^2 - 4p(q+1) + q^2-2q+5=0 (1)$ The short discriminate of this equation is $\triangle = 16(q-1)$. Because this equation have integer solution so the discriminate is a square , then $q-1 = k^2 (k \in \mathbb{Z}^+) $ Subtracting, we have $q = b^2 - k^2 = (b-k)(b+k)$ Since $0<b-k < b+k $ then $b-k = 1, b+k = q$ so $k= \dfrac{q-1}{2}$ then $q - 1 = (\dfrac{q-1}{2})^2$ then $(q-1)(q-5)=0$. Because $q>2$ so $q=5$ Subsititute back to (1) we have $4p^2 - 24p + 20 = 0 \Leftrightarrow 4(p-1)(p-5)=0 \Leftrightarrow p=5$ So the answer is $(p,q)=(5,5)$
10.03.2024 18:52
10.03.2024 19:10
could you use Thue's lemma?
10.03.2024 19:52
Hey, can you show me how to proof "the product of two prime number can written as sum of two square in at most two ways"??