How can I continue,in order to show that 2^b-1 does not divide 2^a+1?

  • MHB
  • Thread starter evinda
  • Start date
In summary, the conversation discusses how to prove that $2^b-1$ does not divide $2^a+1$ when $a,b \geq 3$, and provides two cases to consider: when b is a factor of a and when b is not a factor of a. It also explains how to continue the proof in the second case by showing that $2^b-1$ is not a factor of $2^a+1$.
  • #1
evinda
Gold Member
MHB
3,836
0
Hi! :)
I am looking at the following exercise:
If $a,b \geq 3$,prove that $2^b-1$ does not divide $2^a+1$.
That's what I have tried so far:
We suppoe that $2^b-1|2^a+1$.
We know that $2^b-1|2^b-1$.
So,we get that $2^b-1|2^a+2^b$.
But how can I continue? Do,I have to show that $(2^b-1,2^a+2^b)=1$ ?
I have tried to do this,like that: Let $(2^b-1,2^a+2^b)=d>1$,so $d$ has a prime divisor,$p$.
$p|d,d|2^b-1,d|2^a+2^b \Rightarrow p|2^b-1,p|2^a+2^b$ ,but I don't know how I could continue... :confused:
 
Mathematics news on Phys.org
  • #2
evinda said:
Hi! :)
I am looking at the following exercise:
If $a,b \geq 3$,prove that $2^b-1$ does not divide $2^a+1$.
That's what I have tried so far:
We suppoe that $2^b-1|2^a+1$.
We know that $2^b-1|2^b-1$.
So,we get that $2^b-1|2^a+2^b$.
But how can I continue? Do,I have to show that $(2^b-1,2^a+2^b)=1$ ?
I have tried to do this,like that: Let $(2^b-1,2^a+2^b)=d>1$,so $d$ has a prime divisor,$p$.
$p|d,d|2^b-1,d|2^a+2^b \Rightarrow p|2^b-1,p|2^a+2^b$ ,but I don't know how I could continue... :confused:

Your statement is false, if a = b then $2^b - 1$ DOES divide $2^a - 1$...
 
  • #3
evinda said:
Hi! :)
I am looking at the following exercise:
If $a,b \geq 3$,prove that $2^b-1$ does not divide $2^a+1$.
That's what I have tried so far:
We suppoe that $2^b-1|2^a+1$.
We know that $2^b-1|2^b-1$.
So,we get that $2^b-1|2^a+2^b$.
But how can I continue? Do,I have to show that $(2^b-1,2^a+2^b)=1$ ?
I have tried to do this,like that: Let $(2^b-1,2^a+2^b)=d>1$,so $d$ has a prime divisor,$p$.
$p|d,d|2^b-1,d|2^a+2^b \Rightarrow p|2^b-1,p|2^a+2^b$ ,but I don't know how I could continue... :confused:

There are 2 cases
case 1
b is a factor of a say a = mb

then $2^b-1$ is a factor of $2^{mb} - 1$ so $2^b-1$ is not a factor of $2^a + 1$ as remainder = 2
case 2
b is not a factor of a so a = mb + c where c < b

$2^a+ 1 = 2^{mb+c} + 1$
= $2^c ( 2^{mb}- 1) + 2^c + 1$
now $2^b$ devides $2^c ( 2^{mb}- 1)$ but as c < b
$2^c + 1 < 2^b-1 as 2^c + 2 < 2^{c+1}$

so it does not devide
 

FAQ: How can I continue,in order to show that 2^b-1 does not divide 2^a+1?

How can I prove that 2^b-1 does not divide 2^a+1?

To prove that 2^b-1 does not divide 2^a+1, you can use the proof by contradiction method. Assume that 2^b-1 divides 2^a+1, then it follows that 2^a+1 = k(2^b-1) for some integer k. Rearranging this equation, we get 2^a = k(2^b-1) - 1. However, this is impossible since the left side of the equation is always even while the right side is always odd. Therefore, our assumption was incorrect and we can conclude that 2^b-1 does not divide 2^a+1.

Can I use induction to prove that 2^b-1 does not divide 2^a+1?

No, induction cannot be used to prove that 2^b-1 does not divide 2^a+1. Induction is used to prove statements for all natural numbers, but in this case, we are dealing with specific values of a and b. Therefore, we cannot use induction to prove this statement.

Are there any counterexamples to show that 2^b-1 does not divide 2^a+1?

Yes, there are several counterexamples to show that 2^b-1 does not divide 2^a+1. One example is when a = 4 and b = 3. Plugging in these values, we get 2^4+1 = 16+1 = 17, and 2^3-1 = 8-1 = 7. Clearly, 17 is not divisible by 7, so this is a counterexample to the statement.

Can I use modular arithmetic to prove that 2^b-1 does not divide 2^a+1?

Yes, modular arithmetic can be used to prove this statement. One approach is to use the fact that for any integer n, n^m ≡ 1 (mod m) for all positive integers m. So, if we can show that 2^a ≡ 1 (mod 2^b-1), then we can conclude that 2^a+1 ≡ 2 (mod 2^b-1), which means 2^b-1 cannot divide 2^a+1.

Is there a general formula or rule for determining if 2^b-1 does not divide 2^a+1?

No, there is no general formula or rule for determining if 2^b-1 does not divide 2^a+1. The proof of this statement relies on the specific values of a and b, so there is no one-size-fits-all method for determining if the statement is true. However, you can use the proof by contradiction method or other mathematical techniques to determine if a specific case is true or false.

Similar threads

Back
Top