8
$\begingroup$

Prove that if $a$ and $b$ are odd, coprime numbers, then $\gcd(2^a +1, 2^b +1) = 3$.

I was thinking among the lines of:

Since $a$ and $b$ are coprime numbers, $\gcd(a,b)=1$. Then there exist integers $x$ and $y$ such that, $ax+by=1$.

Then, $a=(1-by)/x$, $b=(1-ax)/y$

So if I write $2^a+1$ as:

$2^{(1-by)/x}+1$

Then can I say that the above expression is equivalent to 0 (mod 3)?

  • 3
    You can show that $2^a+1$ and $2^b+1$ are multiples of $3$ simply enough: since $a=2k+1$, then $2^a+1 = 2(2^{2k})+1 = 2(4^k)+1$, and since $4\equiv 1\pmod{3}$, then $2^a+1 \equiv 2(4^k)+1 \equiv 2(1)+1 = 0\pmod{3}$. Same with $2^b+1$. But the fact that they are both divisible by $3$ only tells you the gcd is a *multiple* of $3$, it doesn't tell you the gcd *is* $3$.2011-11-02
  • 0
    Good point, I was thinking of that at first, but your right, it doesn't prove that gcd is 32011-11-02
  • 0
    http://en.wikipedia.org/wiki/Coprime#Generating_all_coprime_pairs2011-11-02

4 Answers 4