2
$\begingroup$

Let $a<b$ be positive integers such that $ab+1 = r^2$ for some $r \in \mathbb{N}.$ If $m_1 = 2a(r+b)+1$ and $m_2 = 2b(r+a)+1.$ I want to find the possible values of $\gcd(m_1,m_2).$ I had taken some examples in the range $a,b\in\{1,2,\dots 1000\},$ and found the corresponding values as $\gcd(m_1,m_2) = 1.$ Is $\gcd(m_1,m_2) = 1$? If yes, how to prove it? If no, provide a counter example.Only thing that I could see is $\gcd(a,r)=\gcd(b,r) = 1.$

$\endgroup$
6
  • $\begingroup$ Have you tried using the Euclidean Algorithm to find the gcd of $m_1$ and $m_2$? $\endgroup$ May 21 at 6:18
  • 2
    $\begingroup$ @AlratranaSuna Your title uses $2b(r + b) + 1$ for the second $\gcd$ value, but your text indicates it's supposed to be $2b(r + a) + 1$ instead. Please update your question so both are shown as the correct value. $\endgroup$ May 21 at 6:24
  • $\begingroup$ @AtratranaSuna Note I've posted an answer showing the $\gcd$ is always $1$ for the second $\gcd$ being either $2b(r + a) + 1$ or $2b(r + b) + 1$. Nonetheless, you should still update your question to indicate which one you had intended. $\endgroup$ May 21 at 7:39
  • $\begingroup$ Does this answer your question? How to show the coprimality? . As Dietrich Burde's answer there indicates, that question's $m_1$ is the same as your $m_1$, and similarly with $m_2$ (the version in your question text). You originally made a mistake there and then fixed it. However, even though it was closed, you should have added more details there, like you did in this question, and then tried to get it reopened rather than post a basically duplicate question here instead. $\endgroup$ May 21 at 8:34
  • 1
    $\begingroup$ @JohnOmielan, yes I should have done that, thanks for pointing it. $\endgroup$ May 21 at 9:42

3 Answers 3

3
$\begingroup$

$\!\!\!\begin{align} \bmod \:\!d\!=\!{\rm gcd}\!:\ &{-}2\color{darkorange}a(\color{#4bf}{r\!+\!b})\equiv 1 \equiv 2\:\!\color{#0a0}r\:\!(r\!+\!a),\, \ {\rm by}\ \ \color{darkorange}a\color{#4bf}b\equiv r^2\!-1\:\ \small\text{(cf. comments)}\\[.2em] {\rm thus}\ \ \ \ &{-}2\color{#c00}b(r\!+\!a)\equiv 1\:\!\Rightarrow\, \smash{\overset{\overset{\color{#0a0}{\Large\updownarrow}}{\phantom{"}}}{\color{#0a0}r}}\equiv \frac{1}{2(r\!+\!a)}\equiv-\color{#c00}b\Rightarrow \color{#4bf}{r\!+\!b}\equiv 0\Rightarrow 0\equiv 1\Rightarrow\:\! \bbox[4px,border:1px solid #c00]{d\mid 1}\end{align}$

$\endgroup$
4
  • $\begingroup$ Surprised that I am the only one to upvote your answer and Aqua's answer. $\endgroup$ May 23 at 12:55
  • $\begingroup$ @BillDubuque, thank you so much. But, can you just little elaborate how $2r(r+a) \equiv 1?$ $\endgroup$ May 26 at 8:40
  • 1
    $\begingroup$ @Atr We used $\,ab = r^2-1\,$ to replace $\,\color{#c00}{ab}$ by $\,\color{#0a0}{r^2-1}\,$ in $\,m_1\,$ i.e. in extreme detail: $$\begin{align} m_1 &= 2a(\color{#4bf}{r+b})+1\\ &= 2ar+2\color{#c00}{ab}+1\\ &= 2ar+2(\color{#0a0}{r^2\!-1})+1\\ &= 2r(a+r)-1\end{align}\qquad\qquad\qquad\qquad\qquad $$ Therefore the above implies that $\,2r(a+r)\equiv 1\!\iff\! m_1\equiv 0\!\iff\! -2a(\color{#4bf}{r+b})\equiv 1.\,$ So all $\,3\,$ prior congruences are true here because the middle one is, i.e. $\:d\mid m_1\Rightarrow m_1\equiv 0\pmod{\!d}.\ \ $ $\endgroup$ May 26 at 9:13
  • $\begingroup$ @BillDubuque hank you so much <3, that clears all the doubts. $\endgroup$ May 27 at 5:30
1
$\begingroup$

We are given that $ab+1=r^{2}$.

Note

$$2a(r+b)+1 = 2ar + 2ab+1 = 2ar+2r^2-1$$

$$2b(r+a)+1= 2br+2r^2-1$$

We claim that the gcd of the above two quantities is $1$.

$\textbf{For proof by contradiction}$ suppose that there is some prime $p$ that divides both $2ar+2r^2-1$ and $2br+2r^2-1$. Then note that $ p \not \div 2r, p \not \div a, p \not \div b$.

If $p \div 2r^2-1$, then $p|a$ and $p|b$, but $(ab, 2r^2-1) = (r^2-1,2(r^2-1)+1) = 1$ $\Rightarrow$ Thus $p \not \div 2r^2-1$

From $2ar+2r^2-1 \equiv 0 \mod p$ we get $a \equiv (1-2r^2)(2r)^{-1}\mod p $

From $ab = r^2 -1$ we get $b \equiv (r^2-1)(a)^{-1} \equiv (2r^3-2r)(1-2r^2)^{-1} \mod p$

Note that we also have $a \equiv b \mod p$ as $2ar+2r^2-1 \equiv 2br+2r^2-1 \mod p$. Thus $$(1-2r^2)(2r)^{-1} \equiv (2r^3-2r)(1-2r^2)^{-1} \mod p$$ $$ \Rightarrow (1-2r^2)^2 \equiv 4r^4-4r^2 \mod p$$ $$\Rightarrow 1 \equiv 0 \mod p$$ Which is impossible.

$\endgroup$
1
$\begingroup$

If there is a prime $p$ such that $p$ divides both then clearly $p\ne2$ and divides their difference $$p\mid 2r(a-b)$$ So we have 2 possibilities:

  • If $p\mid r$ then $p\mid 2ab+1$ and $p\mid ab+1$ so $p\mid 2(ab+1)-(2ab+1)=1$. A contradiction.

  • If $p\mid a-b$ then we get $p\mid 2ar+2a^2+1$. But $p\mid a^2+1-r^2$ so $p\mid a^2+2ar+r^2$ and thus $p\mid a+r$ and now also $p\mid 2b(a+r)$. But then $p\mid 1$. A contradiction.

So there is no such $p$ and thus a conclusion.

$\endgroup$
4
  • $\begingroup$ +1 : Very nice. I looked at this for 30 minutes, and couldn't crack it. In fact, I had to really focus, just to understand your answer. Then, I figured it out. You didn't really derive this result, someone else did. However, you are from the future. So, you invented a time machine and then traveled back to this alternative timeline to claim the credit for what someone else in your original timeline discovered. $\endgroup$ May 21 at 8:18
  • $\begingroup$ @user2661923 Truly from the future: there exists a very short and simple proof - see my answer. $\endgroup$ May 23 at 12:01
  • $\begingroup$ I could not get the last point as how $p|1?$ $\endgroup$ May 26 at 8:50
  • 1
    $\begingroup$ @Atr $\,p\,$ divides both $\,2b(r+a)+1\,$ and $\,2b(r+a)\,$ so it divides their difference $1.\,$ Said equationally: $\,2b(r+a)\equiv 0\Rightarrow 1\equiv -2b(r+a)\equiv 0\,\pmod{\!p}\,$ like the final inference in my proof that $\color{#4bf}{r+b}\equiv 0\Rightarrow 1\equiv -2a(\color{#4bf}{r+b})\equiv 0\,\pmod {\!d}\ \ $ $\endgroup$ May 26 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.