1
$\begingroup$

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$).
$\endgroup$
  • $\begingroup$ Hint: The equation $ax+by=c$ is solvable if and only if $gcd(a,b)$ divides $c$. $\endgroup$ – MrMazgari Nov 20 '15 at 3:13
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.