# Proving relatively prime using GCD definition

I'm stuck on proving a few facts. My thoughts for each question are below, what do you guys think?

1. Let a and b be positive integers. Prove that $2^a$ and $2^b-1$ are relatively prime by showing that there are integers $x$ and $y$ such that $(2^a)X+ (2^b-1)Y=1$.

Let $d=gcd(2a+1, 4a^2+1)$, then $d$ divides $2a+1$ and d divides $4a^2+1$ and d is positive (By the definition of gcd). But now I am stuck with where to go. I wanted to use the division principle to show that there is an $x$ and a $y$ such that $ax+by=1$ but I have no idea what $x$ and $y$ to use that are dependent on $a$ that will cancel out both a dependent terms in $2a+1$ and $4a^2+1$. Any ideas?

1. Similar to that of question one, except I have $2^c$ and $2^c-1$. I want to prove it in the same way, is it possible? I want to use the division rules and definition of the gcd ( i.e. if $s=gcd(a,b)$ then $s$ divides $a$ and $s$ divides $b$, $s>0$).
• Hint: The equation $ax+by=c$ is solvable if and only if $gcd(a,b)$ divides $c$. – MrMazgari Nov 20 '15 at 3:13

## 1 Answer

Theorem: The equation $ax+by=c$ is solvable if and only if $gcd(a,b)$ divides $c.$

Now, to answer your questions, it is immediate that gcd$(2^a,2^b-1)=1,$ since $2^a$ is even and $2^b-1$ is odd. Hence, by the above theorem, there exist integers $x$ and $y$ such that $$2^a\cdot x+(2^b-1)\cdot y=1.$$

Exactly which integers these are depend on $a$ and $b$, but the fact that they exists is all you need here.

The second part is very similar to the above.