1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory

  1. Oct 25, 2009 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    3. 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.
  2. jcsd
  3. Oct 26, 2009 #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.
  4. Oct 26, 2009 #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
    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]
    [tex]2^m \equiv 1 \pmod {2^m -1}[/tex]
    to show:
    [tex]2^{n-m}\equiv -1 \pmod{2^m -1}[/tex]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook