Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 2

up vote 8 down vote accepted

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$

share|improve this answer
    
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
    
thanks! I got it! –  tlh1987 Nov 21 '12 at 12:41
    
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
1  
@LarsH, $a\mid b$ means $b$ is divisible by $a$. Nothing wrong in clarifying doubt. –  lab bhattacharjee Nov 21 '12 at 16:26

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.

share|improve this answer
1  
thanks! Your answer is very clear! –  tlh1987 Nov 21 '12 at 12:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.