Number theory

  • #1

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.
 

Answers and Replies

  • #2
354
0
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
430
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]
 

Related Threads on Number theory

  • Last Post
Replies
5
Views
862
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
762
  • Last Post
Replies
3
Views
975
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
717
Top