When does n | (2^m -1) for arbitrary odd n?
September 21, 2005 12:22 PM Subscribe
I'm an algebraist, and I need help with a difficult number theory problem involving Mersenne Numbers. Difficult Number Theorists, please help me!
posted by CrunchyFrog to science & nature (9 answers total)
I'm into abstract algebra rather than number theory. I'm reading a paper in which the author assumes the existance of "a primitive nth root of unity in GF(2^m) that is an appropriate extension of GF(2)" for an arbitrary odd number, n. I'm not sure if this is always possible.
Let me put this into number theoretic terms. In order for it to be possible, n must divide 2^m - 1, that is, it must be a factor of a Mersenne Number (with non-prime powers allowed).
I know that this is a major open problem if we are restricted to Mersenne Numbers of the form 2^p - 1 with p prime; it is currently not known whether there are any such Mersenne Numbers that are multiples of 9, 25, 49, or any square. (On the other hand, 2^6 - 1 = 63, a multiple of 9.)
I know that this is always possible if n is a prime, since Fermat's Little Theorem says 2^(n-1) - 1 = 0 (mod n) for any prime.
But is it the case for arbitrary odd numbers, without restricting the powers to primes? I'm having trouble searching for it, since 2^p - 1 is a more common definition of Mersenne Number than 2^n - 1. The paper I'm reading assumes that it's true without footnoting it, which makes me think it's a commonly known theorem in number theory.