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

Question

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.

Answer 1

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.

I hope this helps.If you have any questions please ask and I will answer you.

Answer 2

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.