Number theory

1. Oct 25, 2009

halvizo1031

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. Oct 26, 2009

foxjwill

Please use standard notation and don't skip steps. As written, your proof makes very little sense. Are you defining T as $$\{(m,n) : m,n>2 \text{ and } (2^m-1) \,|\, (2^n+1)\}$$? 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. Oct 26, 2009

rasmhop

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):
$$T = \{(m,n) \in \mathbb{Z}^2 | m,n > 2 \textrm{ and } 2^m-1 | 2^n +1\}$$
Let (m,n) be the least element in T in the lexicographic ordering. If $m\geq n$ you should fairly be able to show a contradiction. So assume m<n, now
$$\frac{2^n+1}{2^m-1}$$
is an integer by assumption so:
$$\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}$$
is an integer. Using this you should be able to show $(m,n-m) \in T$.

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