2
$\begingroup$

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.

  • 0
    If $i$ ande $j$ are switched it looks right, and easy to show.2012-11-21
  • 0
    @tlh1987 Because $i>j \implies i-j>0 \implies j-i<0 \implies 3^{j-i} \not\in \mathbb{N}$2012-11-21
  • 0
    @joriki, sorry, there something wrong with the material I have, can I change the question? I am first asked here?2012-11-21
  • 0
    @badp sorry, I swithed the i and j.2012-11-21
  • 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 2

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
    sorry, I switched the i and j, is this still the answer?2012-11-21
  • 0
    @tlh1987, please find the edited answer.2012-11-21
  • 0
    Excuse my ignorance... what does the bar in $j>i,3\mid 3^{j-i}$ mean? I thought it meant "such that," but I can't parse it in a way that makes sense with a 3 before it.2012-11-21
  • 1
    @LarsH, $a\mid b$ means $b$ is divisible by $a$. Nothing wrong in clarifying doubt.2012-11-21
  • 0
    Thanks, that clears it up. I also had to look up the notation $(2,3) = 1$. Apparently that's short for $ \gcd(2,3) = 1 $.2012-11-21
  • 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=false2012-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.

  • 1
    thanks! Your answer is very clear!2012-11-21