Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $a$ and $b$ be two positive integers, such that neither $a$ nor $b$ is divisible by a perfect square. Is there be a simplified formula for

$$\gcd(a+b,\text{lcm}(a,b)) ?$$ and is there a way to find if this result is divisible by a perfect square or not?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Let $a=\prod p_i\prod q_j$ and $b=\prod p_i\prod r_k$ where $p_i,q_j,r_k$ are distinct primes.

So, $lcm(a,b)=\prod p_i\prod q_j \prod r_k$ and $\gcd(a,b)=\prod p_i$

So, $\gcd(a+b, lcm(a,b))=\gcd(\prod p_i(\prod q_j+ \prod r_k),\prod p_i\prod q_j \prod r_k)$ $=\prod p_i\gcd(\prod q_j+ \prod r_k,\prod q_j \prod r_k)$

Now, $\gcd(\prod q_j+ \prod r_k,\prod q_j)=\gcd(\prod r_k,\prod q_j)=1$ as $q_j,r_k$ are distinct primes.

Similarly, $\gcd(\prod q_j+ \prod r_k,\prod r_k)=1$

Consequently, $\gcd(\prod q_j+ \prod r_k,\prod q_j \prod r_k)=1$

$\gcd(a+b, lcm(a,b))=\prod p_i=\gcd(a,b)$

share|improve this answer

Lemma: If $\gcd(x,y)=1$ then $z=\gcd(x+y, lcm(x,y))=1$. Proof: If $p$ divides $z$, then $p|x+y, lcm(x,y)$. Since $p|lcm(x,y)$ we have either $p|x$ or $p|y$. Together with $p|x+y$ we find that necessarily $p|x,y$, i.e. $p|\gcd(x,y)=1$. This establishes the lemma. $\blacksquare$

Let $g=\gcd(a,b)$. Now you can just write $$\gcd(a+b, lcm(a,b)) = g\gcd(\frac{a}{g}+\frac{b}{g}, \frac{lcm(a,b)}{g}) = g\gcd(\frac{a}{g}+\frac{b}{g}, lcm(\frac{a}{g},\frac{b}{g}))$$ (we've used the fact that both $\gcd$ and $lcm$ are homogeneous: $\gcd(cx,cy)=c \cdot \gcd(x,y), lcm(cx,cy)=c \cdot lcm(x,y)$)

And, by the lemma, since $\frac{a}{g}, \frac{b}{g}$ are coprime by construction, we have that this expression equals $g\cdot 1=\gcd(a,b)$.

So if $a,b$ are both squarefree, so is $\gcd(a,b)$, which is the value in question.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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