6
$\begingroup$

I have discovered some exercise type conjectures which I can't prove and this is one of them:

Given positive integers $a,b$, then $$ \frac{\gcd(a+b,ab)}{\gcd(a,b)}\ \bigg|\ \gcd(a,b)$$

Can this be proved or disproved?


From time to time, when testing my growing math packages BigZ and Forthmath, I recognize some patterns which I can't prove or disprove (or even have the ambition to). I post them here with the hope that it will not annoy too much. I hope you can bear with it.

$\endgroup$
  • 2
    $\begingroup$ You must tell us what you've tried, what made you come up with these conjectures.. etc. if you want to reopen your question. $\endgroup$ – clathratus Mar 21 '19 at 15:27
  • 1
    $\begingroup$ @clathratus Be aware that many users don't share that opinion (esp. since it often leads to actions detrimental to the enrichment of the site). $\endgroup$ – Bill Dubuque Mar 23 '19 at 17:01
4
$\begingroup$

Write $\gcd(a,b)=d$, then $a=da',b=db'$ and thus $\frac{\gcd(a+b,ab)}{d}=\gcd(a'+b',a'b'd)$ where $\gcd(a',b')=1$. Notice now that $\gcd(a'+b',a'b')=1$ since $a'(a'+b')-a'b'={a'}^2$ and thus $\gcd(a'+b',a'b')|{a'}^2 \implies \gcd(a'+b',a'b')|a'$ and $\gcd(a'+b',a'b')|a'+b' \implies \gcd(a'+b',a'b')|a',b' \implies \gcd(a'+b',a'b')=1$. This means that $\gcd(a'+b',a'b'd)=\gcd(a'+b',d)$ and thus it divides $d$ by definition. So your conjecture is indeed true.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You obtain $\gcd(a'+b',a'b')|a'^2. $ By interchanging $a',b'$ we also have $\gcd (a'+b',a'b')|b'^2.$ So $\gcd (a'+b',a'b')$ is a common divisor of the co-prime pair $a'^2,b'^2.$........+1 $\endgroup$ – DanielWainfleet Aug 19 '18 at 5:27
3
$\begingroup$

Taking $D=(a,b)$, then $a=DA$ and $b=DB$, $(ab,a+b)=D(A+B,ABD)$ and $(A,B)=1$. So you want to know if $(ab,a+b)/D$ divides $D$, i.e. $(A+B,ABD)|D$? well, let's see if the prime common divisors between $A+B$ and $ABD$ are divisor of $D$ as well.

If $p$ is a prime common divisor of $A+B$ and $ABD$, by Gauss lemma, $p|A$ or $p|B$ or $p|D$. If $p|A$ or $p|B$ there is a contradiction with the coprimality of $A$ and $B$ $p$ cause if $p|A$ then $p|(A+B)-A=B$. So $p|D$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I like how "¿" is used by non-hispanophone mathematicians as well :) $\endgroup$ – Bart Michels Aug 18 '18 at 21:18
  • $\begingroup$ @barto haha I'm spanish native speaker indeed, it got mixed up :P $\endgroup$ – user258738 Aug 19 '18 at 1:32
2
$\begingroup$

https://en.wikipedia.org/wiki/P-adic_order

Let $h = \gcd(a+b, ab)$ and $g = \gcd(a,b).$

For each prime factor $p$ including $2,$ two cases:

(I) $$ a = p^k u, b = p^j v $$ with $k > j$ and $u,v \neq 0 \pmod p.$ Then $p$-adic valuation $\nu_p(g) = j.$ Next $\nu_p(ab) = k+j$ while $\nu_p(a+b) = j.$ Put together, $\nu_p(g) = \nu_p(h).$

(II) $$ a = p^k u, b = p^k v $$ with $u,v \neq 0 \pmod p.$ Then $p$-adic valuation $\nu_p(g) = k.$ Next $\nu_p(ab) = 2k$ while $\nu_p(a+b) \geq k.$ Then $$ k \leq \nu_p(h) \leq 2k $$

Put together, $\nu_p(h) \leq 2\nu_p(g).$

In either case, combining all primes, $$ h | g^2 $$

Oh, note that we do have $g | h$ and can write $$ \frac{h}{g} \; | \; g $$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Recall $(a,b) = (a\!+\!b,{\rm lcm}(a,b))\,$ so $\,(a\!+\!b,ab)\mid (a,b)^2\! = (a\!+\!b,{\rm lcm}(a,b))^2$ by $\,ab\mid {\rm lcm}(a,b)^2$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let $m=\gcd(a,b)$. Now $m\mid a$ and $m\mid b$, so $m^2\mid ab$. Let $a=a_1m$, $b=b_1m$, for some positive integers $a_1$, $b_1\ge1$, then $a+b=ma_1+mb_1=m(a_1+b_1)$, so $m\mid a+b$.

There are three cases to consider:

Case 1: If $m\nmid(a_1+b_1)$ then $\gcd(a+b,ab)=m$, and we have $$\frac{\gcd(a+b,ab)}{\gcd(a,b)}=\frac{m}{m}=1\mid\gcd(a,b)=m$$ and the conjecture is true in this case.

Now we need to check whether $m^2\mid a+b=m(a_1+b_1)$, which is equivalent to $m\mid(a_1+b_1)$.

Case 2: If $a_1+b_1=mc$, for some integer $c\ge1$, then $m\mid(a_1+b_1)$, and so $m^2\mid a+b=m(a_1+b_1)$. In this case $\gcd(a+b,ab)=m^2$ (note we cannot have $\gcd(a+b,ab)>m^2$ as $\gcd(a,b)=m$, therefore $m^3\nmid ab$), and we have $$\frac{\gcd(a+b,ab)}{\gcd(a,b)}=\frac{m^2}{m}=m\mid\gcd(a,b)=m$$ and the conjecture is true in this case.

Consider lastly the case:

Case 3:

Let us assume $$m<\gcd(a+b,ab)=\gcd(m(a_1+b_1),m^2a_1b_1)=m\gcd(a_1+b_1,ma_1b_1)<m^2$$ which simplifies to $$1<\gcd(a_1+b_1,ma_1b_1)<m$$ We cannot have $m\mid(a_1+b_1)$, as then $\gcd(a_1+b_1,ma_1b_1)=m$, a contradiction. Further simplification gives $$1<\gcd(a_1+b_1,a_1b_1)<m$$ Let $p$ be s.t. $1<p<m$ and $\gcd(a_1+b_1,a_1b_1)=p$. Then $p\mid a_1+b_1$ and $p\mid a_1b_1$, then $p\mid a_1$ or $b_1$. If $p\mid a_1$ then $p\mid a_1+b_1$ implies $p\mid(a_1+b_1)-a_1=b_1$, a contradiction since $\gcd(a_1,b_1)=1$.

So $\gcd(a_1+b_1,a_1b_1)=1$, and it follows $\gcd(a+b,ab)$ can take no value in $(m,m^2)$.

The conjecture is true.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I may misunderstand, but $a=35$ and $b=63$ gives $\frac{\gcd(a+b,ab)}{\gcd(a,b)}=7$. $\endgroup$ – Lehs Aug 24 '18 at 23:26
  • $\begingroup$ @Lehs Thanks. I started off with the two conditions $m/m$ and $m^2/m$ to check and foolishly forgot to add $a_1+b_1$ as well as factor. $\endgroup$ – Daniel Buck Aug 25 '18 at 0:20

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.