The Well-Known GCD Trick

by AlastorMoody, Oct 14, 2019, 5:57 AM

Sometimes, with questions involving divisibility, It's often a good idea to invoke the GCD! I don't know if this works always but here are some problems that work!
Switzerland MO Finals 2014 wrote:
Let $a,b\in\mathbb{N}$ such that :
\[ ab(a-b)\mid a^3+b^3+ab \]Then show that $\operatorname{lcm}(a,b)$ is a perfect square.
Solution: Let $\gcd(a,b)=d$ $\implies$ $\begin{cases} a=xd \\ b=yd \\ \gcd(x,y)=1 \end{cases}$, Hence, now we have,
$$ab(a-b)\mid a^3+b^3+ab \implies \frac{x^3d^3 + y^3d^3+xyd^2}{xyd^2(x-y)d} \in \mathbb{Z}$$$$\frac{x^3d+y^3d+xy}{xyd(x-y)} \in \mathbb{Z}$$Now, since, $\gcd(x,y)=1$ and $x \mid xyd(x-y)$ $\implies$ $x \mid x^3d+y^3d+xy \implies x \mid d$. Similarly, $y \mid d$. Using, $\gcd(x,y)=1$ $\implies$ $xy \mid d$. But, $d$ $\mid$ $xyd(x-y)$ $\implies$ $d $ $\mid$ $x^3d+y^3d+xy$ $\implies$ $d $ $\mid$ $xy$ $\implies$ $\boxed{xy=d}$ $\implies$ $\text{lcm} ~ (a,b)$ $=$ $xyd$ $=$ $(xy)^2$
It Turns out that when we're given some divisibility and they ask us to prove a perfect square, we must always (?) invoke GCD (:P)
BWM 2013 P5 wrote:
Let $m,n \in \mathbb{Z}^+$, such,
$$mn | m^2+n^2+m$$Prove, $m$ is a perfect square
Solution: Let $\gcd (m,n)=d$ $\implies$ $\begin{cases} m=ad \\\ n=bd \\\ \gcd (a,b)=1 \end{cases}$
$$\frac{m^2+n^2+m}{mn} =\frac{a^2d^2+b^2d^2+ad}{abd^2} =\frac{a^2d+b^2d+a}{abd} \in \mathbb{Z}$$Since, $a$ divides $abd$ $\implies$ $a ~ | ~ a^2d+b^2d+a $ but since, $\gcd (a,b)=1$ $\implies$ $a ~ | ~ d$ And, Since, $d$ divides $abd$ $\implies$ $d ~ | ~ a^2d$ $+b^2d+$ $a$ $\implies$ $d ~ | ~ a$
$$\implies a=d \implies m=ad=a^2=d^2$$Hence done! $\qquad \blacksquare$
Bosnia-Herzegovina Regional Olympiad 2016 Grade 10 P2 wrote:
Let $a$ and $b$ be two positive integers such that $2ab$ divides $a^2+b^2-a$. Prove that $a$ is perfect square
Solution: Let $\gcd (a,b)=d$ $\implies$ $\begin{cases} a=md \\\ b=nd \\\ \gcd (m,n)=1 \end{cases}$
$$\frac{a^2+b^2-a}{2ab} =\frac{m^2d^2+n^2d^2-md}{2mnd^2} =\frac{m^2d+n^2d-m}{2mnd} \in \mathbb{Z}$$Since, $m$ divides $2mnd$ $\implies$ $m ~ | ~ m^2d+n^2d-m $ but since, $\gcd (m,n)=1$ $\implies$ $m ~ | ~ d$ And, Since, $d$ divides $2mnd$ $\implies$ $d ~ | ~ m^2d$ $+n^2d-$ $m$ $\implies$ $d ~ | ~ m$
$$\implies m=d \implies a=md=m^2=d^2$$Hence done! $\qquad \blacksquare$
Now, This Trick doesnot only work for perfect squares, but also for some higher powers :o Below's an example (excuse the stupid solution, b'coz I am n00b)
Indonesia MO 2010 P4 wrote:
Given that $m$ and $n$ are positive integers with property:
\[(mn)\mid(m^{2010}+n^{2010}+n)\]Show that there exists a positive integer $k$ such that $n=k^{2010}$
Solution: Let $\gcd (m,n)=d$ $\implies$ $\begin{cases} m=ad \\\ n=bd \\\ \gcd (a,b)=1 \end{cases}$, We somehow want to show exactly $b=d^{2009}$
$$\frac{m^{2010}+n^{2010}+n}{mn}=\frac{a^{2010}d^{2009}+b^{2010}d^{2009}+b}{abd} \in \mathbb{Z}$$Since, $b ~ | ~ abd$ $\implies$ $b ~ | ~ a^{2010}d^{2009}+b^{2010}d^{2009}+b$ $\implies$ $b ~ | ~ d^{2009}$ And since, $d ~ | ~ abd$ $\implies$ $d ~ | ~ a^{2010}d^{2009}+b^{2010}d^{2009}+b$ $\implies$ $d ~ | ~ b$, $\implies$ $d^2 ~ | ~ abd$ $\implies$ $d^2 ~ | ~b$ $\implies$ $d^3 ~ | ~ abd$ $\implies$ $d^3 ~ | ~ b$ $\implies$ $d^4 ~ | ~ abd$ $\implies$ $d^4 ~ | ~ b$....similarly, we can show $d^{2008} ~ | ~ abd$ $\implies$ $d^{2009} ~ | ~ abd$ $\implies$ $d^{2009} ~ | ~b$, and since, $b ~ | ~ d^{2009}$ $\implies$ $b=d^{2009}$ $\implies$ $n=bd=d^{2010}$ $\qquad \blacksquare$
Pls Lemme know if there are some other problems involving this trick too :omighty:

Comment

5 Comments

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Amazing!!

by Euler1728, Oct 19, 2019, 3:53 AM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
It's easy to generalise the second and last problems:

If $\exists m,n \in \mathbb{N}$, and for some $k \in \mathbb{N}$, such that $mn \mid m^k+n^k+m$ then $m$ is a perfect $k$th power; in particular, $m=(\gcd(m,n))^k$.

Notice that you can similarly, but not directly from your proof of the last problem, solve this as your proof in part relies on the fact $2010 \equiv 2 \pmod{4}$. Here's a turnaround:

We first take the case $k=1$. Thus $mn \mid 2m+n \implies mn \le 2m+n \implies (m+1)(n-2) \le 2$. Now, since $m,n \in \mathbb{N}$, we find $m=n=1=1^1$. Thus what is required is true.

For $k \ge 2$, the proof starts similarly as your proofs, i.e $m=xd,n=yd$ where $d=\gcd(m,n) \implies x,y$ coprime. Rewriting the expression in terms of $x,y,d$, we see that:
$\frac{x^kd^{k-1}+y^kd^{k-1}+x}{xyd} \in \mathbb{N}$.

Again, at this point we make two observations: $x \mid xyd \mid x^kd^{k-1}+y^kd^{k-1}+x \implies x \mid d^{k-1}$ (as $x,y$ coprime). Let this divisibility be $(*)$.

$d \mid xyd \mid{x^kd^{k-1}+y^kd^{k-1}+x} \implies d \mid x$. Now let $l$ be the highest power of $d$ dividing $x^*$. Thus, $x = d^la, a \in \mathbb{N}$.

Hence, $d^{l+1} \mid xyd=ayd^{l+1} \mid x^kd^{k-1}+y^kd^{k-1}+x$. Here, we have a catch. We know nothing about the relationship between $y$ and $d$, so $l+1 \le k-1 \iff d^{l+1} \mid y^kd^{k-1} \implies d^{l+1} \mid x$. This clearly contradicts the maximality of $l$, hence $l+1 > k-1 \implies l \ge k-1 \implies d^{k-1} \mid x$. Using this and $(*)$, $x=d^{k-1} \implies m=d^k$.
$^*$Since we usually define "highest power" for prime factors, we can also restate $l$ in those terms:
For all primes $p_i$ dividing $d$, let $f_i= \nu_p(x)$. Then $l=\min \{ f_i : i \in \{1,2,3 \cdots \Omega(d) \} \}$. Just unnecessarily rigorising....

by Hexagrammum16, Oct 19, 2019, 7:22 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Oh, the third problem also falls into this category. Noting that the above proof doesn't change, there can be any given natural multiplied with $mn$ in the denominator, and $ \pm m$ in the numerator.

by Hexagrammum16, Oct 19, 2019, 7:26 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Oh, I was wrong about your proof depending mod 4, yours is just induction.

by Hexagrammum16, Oct 19, 2019, 8:02 PM

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Hi Alsotor, nice blog post. Here is a problem involving the GCD trick. I am posting since you asked for some problems :
(JBMO shortlist 2018 N1)
Find all integers $m$ and $n$ such that $m^5 - n^5 = 16mn$

by lilavati_2005, Nov 2, 2019, 5:25 PM

I'll talk about all possible non-sense :D

avatar

AlastorMoody
Shouts
Submit

  • what a goat, u used to be friends with my brother :)

    by bookstuffthanks, Jul 31, 2024, 12:05 PM

  • hello fellow moody!!

    by crazyeyemoody907, Oct 31, 2023, 1:55 AM

  • @below I wish I started earlier / didn't have to do JEE and leave oly way before I could study conics and projective stuff which I really wanted to study :( . Huh, life really sucks when u are forced due to peer pressure to read sh_t u dont want to read

    by kamatadu, Jan 3, 2023, 1:25 PM

  • Lots of good stuffs here.

    by amar_04, Dec 30, 2022, 2:31 PM

  • But even if he went to jee he could continue with this.

    Doing JEE(and completely leaving oly) seems like a insult to the oly math he knows

    by HoRI_DA_GRe8, Feb 11, 2022, 2:11 PM

  • Ohhh did he go for JEE? Good for him, bad for us :sadge:. Hmmm so that is the reason why he is inactive
    Btw @below finally everyone falls to the monopoly of JEE :) Coz IIT's are the best in India.

    by BVKRB-, Feb 1, 2022, 12:57 PM

  • Kukuku first shout of 2022,why did this guy left this and went for trashy JEE

    by Commander_Anta78, Jan 27, 2022, 3:42 PM

  • When are you going to br alive again ,we miss you

    by HoRI_DA_GRe8, Aug 11, 2021, 5:10 PM

  • kukuku first shout o 2021

    by leafwhisker, Mar 6, 2021, 5:10 AM

  • wow I completely forgot this blog

    by Math-wiz, Dec 25, 2020, 6:49 PM

  • buuuuuujmmmmpppp

    by DuoDuoling0, Dec 22, 2020, 10:54 PM

  • This site would work faster if not all diagrams were displayed on the initial page. Anyway I like your problem selection taste.

    by WolfusA, Sep 24, 2020, 7:58 PM

  • nice blog :)

    by Orestis_Lignos, Sep 15, 2020, 9:09 AM

  • Hello everyone, nice blog :)

    by Functional_equation, Sep 12, 2020, 6:22 PM

  • pro blogo

    by Aritra12, Sep 8, 2020, 11:17 AM

120 shouts
Contributors
AlastorMoody • aops29 • Pluto1708 • SenatorPauline
Tags
About Owner
  • Posts: 2125
  • Joined: Oct 11, 2017
Blog Stats
  • Blog created: Nov 19, 2018
  • Total entries: 25
  • Total visits: 12378
  • Total comments: 60
Search Blog
a