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!
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.
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.
Response by poster: That's it! The page mentions Euler's Totient theorem, which says if n is a positive integer and a is coprime to n, then a^(phi(n)) = 1 (mod n), or in other words, n divides a^(phi(n)).
Exactly what I needed! Now I can get back to writing my dissertation.
posted by CrunchyFrog at 2:27 PM on September 21, 2005
Exactly what I needed! Now I can get back to writing my dissertation.
posted by CrunchyFrog at 2:27 PM on September 21, 2005
Response by poster: That is, n divides a^(phi(n)) - 1
posted by CrunchyFrog at 2:28 PM on September 21, 2005
posted by CrunchyFrog at 2:28 PM on September 21, 2005
Is this something other than the fact that the multiplicative group of a finite field is cyclic? That's how I'm reading it.
(More generally, a finite subgroup of the multiplicative group of a field is cyclic. Example: roots of unity in the complex numbers. Proof: a finite abelian group is cyclic iff for all n, there are at most n elements whose nth power is the identity, which is easily seen from the classification of finite abelian groups. That "at most" statement holds in a field by trying to factor x^n - 1.)
On preview: it doesn't look like Euler's totient theorem is getting you the primitive root of unity you wanted. Whereas the above theorem does.
posted by Aknaton at 2:34 PM on September 21, 2005
(More generally, a finite subgroup of the multiplicative group of a field is cyclic. Example: roots of unity in the complex numbers. Proof: a finite abelian group is cyclic iff for all n, there are at most n elements whose nth power is the identity, which is easily seen from the classification of finite abelian groups. That "at most" statement holds in a field by trying to factor x^n - 1.)
On preview: it doesn't look like Euler's totient theorem is getting you the primitive root of unity you wanted. Whereas the above theorem does.
posted by Aknaton at 2:34 PM on September 21, 2005
Aknaton is right and faster than I, drat him. This is just the fact that the multiplicative group is cyclic. In particular, there is a primitive nth root of 1 in GF(q) for any n relatively prime to q. If n is not relatively prime to q, it just generates the cyclic subgroup GF(q')x for some q' dividing q.
posted by gleuschk at 2:54 PM on September 21, 2005
posted by gleuschk at 2:54 PM on September 21, 2005
Ah, I took to long to write my answer. Just adjoin a primitive nth root of unity to GF(2). By the classification of finite fields, the result is GF(2^m) for some m, and by construction it has the root you need.
posted by samw at 2:55 PM on September 21, 2005
posted by samw at 2:55 PM on September 21, 2005
Oops, I was o'erhasty in my annoyance at Aknaton. Replace "relatively prime to" by "not a divisor of".
posted by gleuschk at 3:13 PM on September 21, 2005
posted by gleuschk at 3:13 PM on September 21, 2005
gleuschk, don't you mean "for any n dividing q-1"?
posted by Aknaton at 11:34 AM on September 22, 2005
posted by Aknaton at 11:34 AM on September 22, 2005
Oh, I don't even know what I meant any more. At this point, if I could withdraw all my comments from this thread, I would -- I ahve the distinct impression I misunderstood the question.
posted by gleuschk at 7:59 PM on September 23, 2005
posted by gleuschk at 7:59 PM on September 23, 2005
This thread is closed to new comments.
posted by cerebus19 at 2:04 PM on September 21, 2005