Why is the following G.C.D equal to $1$: $ \gcd(3^s, 2^n-3^{(j-i)}2^m),\quad s> j >i \geq 0, $ and all variables are natural numbers.
Why the following G.C.D is $1$
2
$\begingroup$
elementary-number-theory
-
0@tlh1987: When you edit the question in a way that makes an existing answer or comment appear wrong, please mark the edit as such. Thanks. – 2012-11-21
2 Answers
8
The only prime factor of $3^s$ is 3 as $s\ge 1$
But $2^n-3^{(j-i)}2^m\equiv2^n\pmod 3$ as $3\mid 3^{j-i}$ as $j>i$
So, $2^n-3^{(j-i)}2^m\equiv2^n\equiv(-1)^n\not\equiv 0 \pmod 3$
So, $3^s,2^n-3^{(j-i)}2^m$ can not have any common prime factor, hence $(3^s,2^n-3^{(j-i)}2^m)=1$
-
0@LarsH, may have$a$look in to the Notations in http://books.google.co.in/books?id=V52HIcKguJ4C&printsec=frontcover&dq=inauthor:%22Herbert+S.+Zuckerman%22&hl=en&sa=X&ei=CAitUPG_JoizrAeC_4DgDg&ved=0CDAQ6AEwAA#v=onepage&q&f=false – 2012-11-21
7
Laws of GCD:
- $\gcd(x,y) = \gcd(x,x-y)$
- for $a$ coprime to $y$: $\gcd(x,y) = \gcd(x,ay)$
We can derive general formula using the laws of GCD:
$\gcd(3^a,2^b) = 1$
$\gcd(3^a,2^b-3^a) = 1$
$\gcd(3^a,2^{b+c}-2^c 3^a) = 1$
$\gcd(3^{a+d},2^{b+c}-2^c 3^a) = 1$
now put $a+d = s$, $b+c = n$, $a = j-i$, $c = m$ to get the special result.
-
1thanks! Your answer is very clear! – 2012-11-21