text: # Why the following G.C.D is $1$
  
  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.
  
  • If $i$ ande $j$ are switched it looks right, and easy to show. – coffeemath Nov 21 '12 at 12:19
  • @tlh1987 Because $i>j \implies i-j>0 \implies j-i<0 \implies 3^{j-i} \not\in \mathbb{N}$ – badp Nov 21 '12 at 12:22
  • @joriki, sorry, there something wrong with the material I have, can I change the question? I am first asked here? – tlh1987 Nov 21 '12 at 12:29
  • @badp sorry, I swithed the i and j. – tlh1987 Nov 21 '12 at 12:30
  • @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. – joriki Nov 21 '12 at 12:55
  
  ## 2 Answers
  
  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$
  
  • sorry, I switched the i and j, is this still the answer? – tlh1987 Nov 21 '12 at 12:31
  • @tlh1987, please find the edited answer. – lab bhattacharjee Nov 21 '12 at 12:33
  • 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. – LarsH Nov 21 '12 at 16:24
  • @LarsH, $a\mid b$ means $b$ is divisible by $a$. Nothing wrong in clarifying doubt. – lab bhattacharjee Nov 21 '12 at 16:26
  • 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$. – LarsH Nov 21 '12 at 16:50
  
  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.
  
  • thanks! Your answer is very clear! – tlh1987 Nov 21 '12 at 12:44
explanation: The document contains a math question about the greatest common divisor (GCD) of two specific expressions and an explanation of why the GCD is 1. It also includes comments and a discussion about the conditions and a correction to the original question. The document also contains two answers that provide detailed explanations and proofs.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Why the following G.C.D is $1$
  
  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.
  
  • If $i$ ande $j$ are switched it looks right, and easy to show. – coffeemath Nov 21 '12 at 12:19
  • @tlh1987 Because $i>j \implies i-j>0 \implies j-i<0 \implies 3^{j-i} \not\in \mathbb{N}$ – badp Nov 21 '12 at 12:22
  • @joriki, sorry, there something wrong with the material I have, can I change the question? I am first asked here? – tlh1987 Nov 21 '12 at 12:29
  • @badp sorry, I swithed the i and j. – tlh1987 Nov 21 '12 at 12:30
  • @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. – joriki Nov 21 '12 at 12:55
  
  ## 2 Answers
  
  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$
  
  • sorry, I switched the i and j, is this still the answer? – tlh1987 Nov 21 '12 at 12:31
  • @tlh1987, please find the edited answer. – lab bhattacharjee Nov 21 '12 at 12:33
  • 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. – LarsH Nov 21 '12 at 16:24
  • @LarsH, $a\mid b$ means $b$ is divisible by $a$. Nothing wrong in clarifying doubt. – lab bhattacharjee Nov 21 '12 at 16:26
  • 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$. – LarsH Nov 21 '12 at 16:50
  
  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.
  
  • thanks! Your answer is very clear! – tlh1987 Nov 21 '12 at 12:44
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document contains a math question about the greatest common divisor (GCD) of two specific expressions and an explanation of why the GCD is 1. It also includes comments and a discussion about the conditions and a correction to the original question. The document also contains two answers that provide detailed explanations and proofs.
  
  Label: question-and-answer