Number Theory Homework: Prove ((2^m)-1) Not Divisor of ((2^n)+1)

In summary, the conversation discusses the proof that if M and N are positive integers greater than 2, then ((2^m)-1) is not a divisor of ((2^n)+1). The user suggests defining a set T of all (m,n) such that (2^m-1) divides (2^n+1). The WOP cannot be applied here since it only applies to subsets of positive integers. The user then suggests considering the least element in T and using modular arithmetic to show that (m,n-m) is also in T, leading to a contradiction
  • #1
halvizo1031
78
0

Homework Statement



If M and N are positive integers >2, prove that ((2^m)-1) is not a divisor of ((2^n)+1)



Homework Equations





The Attempt at a Solution



Is this correct? I use the well-ordering principle.

Let T be the set of all M,N positive integers greater than 2 such that ((2^m)-1)/((2^n)+1). Assume T is non-empty, then by the WOP, T must contain a smallest L element, call it((2^k)-1)/((2^L)+1). but (2^(k+1)-1)/(2^(L+1)+1) is in T. So, ((2^k)*(2^1)-1)/((2^L)*(2^1)+1). Thus, I have a contradiction.
 
Physics news on Phys.org
  • #2
Please use standard notation and don't skip steps. As written, your proof makes very little sense. Are you defining T as [tex]\{(m,n) : m,n>2 \text{ and } (2^m-1) \,|\, (2^n+1)\}[/tex]? If so, you can't use the WOP because the WOP only applies to subsets of the positive integers. Also, "must contain a smallest L element, call it((2^k)-1)/((2^L)+1)" makes absolutely no sense.
 
  • #3
I'm not really sure what you're doing so I'm going to give you some advice that resembles what I think you're trying.

Consider (as foxjwill suggested):
[tex]T = \{(m,n) \in \mathbb{Z}^2 | m,n > 2 \textrm{ and } 2^m-1 | 2^n +1\}[/tex]
Let (m,n) be the least element in T in the lexicographic ordering. If [itex]m\geq n[/itex] you should fairly be able to show a contradiction. So assume m<n, now
[tex]\frac{2^n+1}{2^m-1}[/tex]
is an integer by assumption so:
[tex]\frac{2^{n-m}(2^m)+1}{2^m-1}=\frac{2^{n-m}(2^m-1)+2^{n-m}+1}{2^m-1}=2^{n-m} + \frac{2^{n-m}+1}{2^m-1}[/tex]
is an integer. Using this you should be able to show [itex](m,n-m) \in T[/itex].

The same thing can be done in modular arithmetic (but in your original post you seemed to prefer fractions), by using:
[tex]2^n \equiv -1 \pmod {2^m-1}[/tex]
and
[tex]2^m \equiv 1 \pmod {2^m -1}[/tex]
to show:
[tex]2^{n-m}\equiv -1 \pmod{2^m -1}[/tex]
 

1. How do you prove that ((2^m)-1) is not a divisor of ((2^n)+1)?

The proof for this statement involves using the properties of modular arithmetic and the fact that for any positive integer n, 2^n is always congruent to either 1 or 2 modulo 3. By considering the possible cases and using contradiction, you can show that ((2^m)-1) cannot divide ((2^n)+1).

2. Can you explain the concept of modular arithmetic in relation to this problem?

Modular arithmetic is a system in which numbers are considered to be equivalent if they leave the same remainder when divided by a given number (called the modulus). In this problem, we use the fact that for any positive integer n, 2^n is always congruent to either 1 or 2 modulo 3, which is crucial in proving the statement.

3. What are the possible cases to consider when proving this statement?

There are three possible cases to consider: m is even and n is odd, m is odd and n is even, and m and n are both odd. By considering each case and using the properties of modular arithmetic, we can show that ((2^m)-1) cannot divide ((2^n)+1).

4. Is this statement always true for all values of m and n?

No, this statement is not always true for all values of m and n. It is only true when the conditions of the proof hold, which is when m is even and n is odd, m is odd and n is even, or m and n are both odd.

5. What are some real-world applications of number theory and modular arithmetic?

Number theory and modular arithmetic have many practical applications in fields such as computer science, cryptography, and physics. For example, they are used in data encryption algorithms, digital signatures, and error correction codes. In physics, modular arithmetic is used in the study of periodic phenomena, such as the motion of celestial bodies.

Similar threads

  • Calculus and Beyond Homework Help
Replies
20
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
9
Views
867
  • Calculus and Beyond Homework Help
Replies
4
Views
462
  • Calculus and Beyond Homework Help
Replies
30
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
452
  • Calculus and Beyond Homework Help
Replies
18
Views
2K
Back
Top