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.

$\endgroup$
  • $\begingroup$ If $i$ ande $j$ are switched it looks right, and easy to show. $\endgroup$ – coffeemath Nov 21 '12 at 12:19
  • $\begingroup$ @tlh1987 Because $i>j \implies i-j>0 \implies j-i<0 \implies 3^{j-i} \not\in \mathbb{N}$ $\endgroup$ – badp Nov 21 '12 at 12:22
  • $\begingroup$ @joriki, sorry, there something wrong with the material I have, can I change the question? I am first asked here? $\endgroup$ – tlh1987 Nov 21 '12 at 12:29
  • $\begingroup$ @badp sorry, I swithed the i and j. $\endgroup$ – tlh1987 Nov 21 '12 at 12:30
  • $\begingroup$ @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. $\endgroup$ – joriki Nov 21 '12 at 12:55
8
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ sorry, I switched the i and j, is this still the answer? $\endgroup$ – tlh1987 Nov 21 '12 at 12:31
  • $\begingroup$ @tlh1987, please find the edited answer. $\endgroup$ – lab bhattacharjee Nov 21 '12 at 12:33
  • $\begingroup$ 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. $\endgroup$ – LarsH Nov 21 '12 at 16:24
  • 1
    $\begingroup$ @LarsH, $a\mid b$ means $b$ is divisible by $a$. Nothing wrong in clarifying doubt. $\endgroup$ – lab bhattacharjee Nov 21 '12 at 16:26
  • $\begingroup$ 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 $. $\endgroup$ – LarsH Nov 21 '12 at 16:50
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ thanks! Your answer is very clear! $\endgroup$ – tlh1987 Nov 21 '12 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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