# Proof $gcd(2^{2x},2x)=2gcd(2^{x},x)$

How do I proof $$\operatorname{gcd}(2^{2x},2x)=2\operatorname{gcd}(2^{x},x)$$ , I have managed to proof $$\operatorname{gcd}(2^{2x},2x)=2\operatorname{gcd}(2^{2x-1},x)$$ but haven't managed to get anywhere form there.

• You could start by writing $x=2^nc$ where $c$ is coprime to $2$. Feb 12, 2021 at 14:54

Firstly,lets denote with $$v_2(x)$$ a positive integer k, such that $$2^k$$|x and $$2^{k+1}\nmid x$$

Lets denote with d=gcd($$2^{2x-1},x$$).We have that d|$$2^{2x-1}$$ and d|x

Because d|$$2^{2x-1}$$,we can say that d=$$2^a$$,$$a \leq 2x-1$$ where a is a non negative integer.

d|x so $$a \leq v_2(x)$$.(Because if otherwise,$$d \nmid x$$)

Because d is as big as possible,$$a=min(2x-1,v_2(x))$$

$$v_2(x) < 2^{v_2(x)}\leq x \leq2x-1$$ so $$a=v_2(x)$$ so $$d=2^{v_2(x)}$$.

Now if we will denote with $$m=gcd(2^x,x)$$ and do the exact same thing as before, we will find out that $$m=2^{v_2(x)}$$ so $$gcd(2^x,x)=gcd(2^{2x-1},x)$$

Now we can finish the proof with what you have proved by yourself.

All positive integers my be written in the form $$n= 2^kw$$ where $$w$$ is odd.(If $$n$$ is odd then $$k =0$$. If $$n$$ is even than there is a highest power of $$2$$ that divides $$n$$ and the remaining quotient will be odd).

Now the only prime factors $$n=2^kw$$ and $$2^m$$, some power of $$2$$, will in common will be $$2$$ so $$\gcd(2^m,n)= 2^j$$ for some $$j$$. And it's easy to convince ourselves $$\gcd(2^m, 2^kw) = \gcd(2^m, 2^k) = 2^{\min(m,k)}$$.

So let $$x = 2^kw$$

Then $$\gcd(2^{2x}, 2x)= \gcd(2^{2x}, 2^{k+1}w) = 2^{\min(2x,k+1)}=2^{\min(2^{k+1}w, k+1} = 2^{k+1}$$. (Obviously $$k+1 < 2^{k+1} \le 2^{k+1}w$$)

Likewise $$\gcd(2^x, x)= \gcd(2^x, 2^kw) = 2^{\min(x, k)}=2^{\min(2^kw,k)} = 2^k$$ and the result follows.

.....

It may seem tricky but the gist is $$2^{something}$$ is $$2$$ to a higher power than the factor of two that divides $$something$$ itself so $$\gcd(2^x, x) = 2^{the\ highest\ power\ that\ divides\ the\ something}$$

So $$\gcd(2^{huge\ therefore\ ignorable}, 2x)= 2^{one\ more\ power\ than\ the\ highest\ power\ of\ 2\ that\ divides\ x}= 2\cdot 2^{the\ highest\ power\ of\ 2\ that\ divides\ x}=2\gcd(2^{not\ as\ huge\ but\ still\ ignorable}, x)$$

We could just as easily asked you to prove $$\gcd(2^{x^2 + 7x+5}, 6x)=2\gcd(2^{9x-1},7x)$$ for all the obfuscation involved.