mersenneforum.org Mersenne and Fermat primes, 2 and 9
 Register FAQ Search Today's Posts Mark Forums Read

 2013-05-14, 18:56 #1 Nick     Dec 2012 The Netherlands 110010101112 Posts Mersenne and Fermat primes, 2 and 9 This puzzle is not original, but appropriate for this forum and as far as I can see not yet present here. Let F be a finite field and F* the group formed by its non-zero elements under multiplication. Suppose that the subgroups of F* are totally ordered by inclusion (i.e. for any subgroups A and B of F*, at least one of $A\subset B, B\subset A$ is true). Show that #F=2 or #F=9 or #F is a Fermat prime number (one that's really prime!), or that #F-1 is a Mersenne prime.
2013-05-17, 13:27   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by Nick This puzzle is not original, but appropriate for this forum and as far as I can see not yet present here. Let F be a finite field and F* the group formed by its non-zero elements under multiplication. Suppose that the subgroups of F* are totally ordered by inclusion (i.e. for any subgroups A and B of F*, at least one of $A\subset B, B\subset A$ is true). Show that #F=2 or #F=9 or #F is a Fermat prime number (one that's really prime!), or that #F-1 is a Mersenne prime.
Showing that #F=2 works is trivial; the group is cyclic. There are no
subgroups.

Showing that #F=9 works is just a tiny bit harder. The order of the field
is 8 and there are subgroups of order 1 (trivial) , 2, and 4. Showing
that they are ordered by inclusion can be done by direct contruction.

Showing that #F is a Fermat prime works is also easy. The field order
is 2^2^n and there are subgroups of order 1,2,4, .... Showing inclusion
can be done by direct construction.

Finally, if #F is a Mersenne prime plus 1 is trivial, because now the group
order is prime, hence the group is cyclic and there are no subgroups.

The difficulty is showing the converse. We need to show that if
the group order (#F-1) has an odd prime factor, then ordering by inclusion
can not work. Then, once we know that the group order is either prime
(thus a cyclic group) or a power of 2, the arguments I sketched above
can be applied. We also use the fact that the only successive powers
are 8 and 9 (proved by Mihailescu) and that a finite field has either a
prime or prime power number of elements.

I have not yet figured out the right argument to show that if the group
order has an odd prime factor (and hence a sub-group of odd order by the
Sylow theorem) then inclusion does not work.

2013-05-17, 13:32   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by R.D. Silverman Showing that #F=2 works is trivial; the group is cyclic. There are no subgroups. Showing that #F=9 works is just a tiny bit harder. The order of the field is 8 and there are subgroups of order 1 (trivial) , 2, and 4. Showing that they are ordered by inclusion can be done by direct contruction. Showing that #F is a Fermat prime works is also easy. The field order is 2^2^n and there are subgroups of order 1,2,4, .... Showing inclusion can be done by direct construction. Finally, if #F is a Mersenne prime plus 1 is trivial, because now the group order is prime, hence the group is cyclic and there are no subgroups. The difficulty is showing the converse. We need to show that if the group order (#F-1) has an odd prime factor, then ordering by inclusion can not work. Then, once we know that the group order is either prime (thus a cyclic group) or a power of 2, the arguments I sketched above can be applied. We also use the fact that the only successive powers are 8 and 9 (proved by Mihailescu) and that a finite field has either a prime or prime power number of elements. I have not yet figured out the right argument to show that if the group order has an odd prime factor (and hence a sub-group of odd order by the Sylow theorem) then inclusion does not work.
I think I figured out the last part. I was making it
too hard.

Let G equal the group order.
If G = 2^n * q, where q is an odd prime, then there will be a subgroup
of order 2 and a subgroup of order q. The smaller can not be included
in the latter because 2 does not divide q. If the group order is
G = 2^n * p * q * r * .... then any of the pairs (p,q), (p,r), (q,r) .....
can't be ordered by inclusion because these pairs are co-prime. This also
applies if n = 0.

2013-05-17, 15:07   #4
literka

Mar 2010

26·3 Posts

Quote:
 Originally Posted by R.D. Silverman Showing that #F=2 works is trivial; the group is cyclic. There are no subgroups. Showing that #F=9 works is just a tiny bit harder. The order of the field is 8 and there are subgroups of order 1 (trivial) , 2, and 4. Showing that they are ordered by inclusion can be done by direct contruction. Showing that #F is a Fermat prime works is also easy. The field order is 2^2^n and there are subgroups of order 1,2,4, .... Showing inclusion can be done by direct construction. Finally, if #F is a Mersenne prime plus 1 is trivial, because now the group order is prime, hence the group is cyclic and there are no subgroups. The difficulty is showing the converse. We need to show that if the group order (#F-1) has an odd prime factor, then ordering by inclusion can not work. Then, once we know that the group order is either prime (thus a cyclic group) or a power of 2, the arguments I sketched above can be applied. We also use the fact that the only successive powers are 8 and 9 (proved by Mihailescu) and that a finite field has either a prime or prime power number of elements. I have not yet figured out the right argument to show that if the group order has an odd prime factor (and hence a sub-group of odd order by the Sylow theorem) then inclusion does not work.

Few remarks:
1.
In the first part of a post you were proving something converse to what Nick wrote. Nick wrote a theorem in one direction. So, it is unrelated to Nick's question.

2.
It cannot be done by direct construction. There are groups with subgroups 2,4,8.. without this inclusion property. You are saying that something can be done and you are not doing this.

3.
In second part you called "converse", but it is exactly what Nick wanted.

4.
In additional post (post #3) you wrote that you found an argument. May be it is an argument but a wrong argument.

Since it is written in an unclear way let me state what you wanted to prove:

if the group order has an odd prime factor (and hence a sub-group of odd order by the Sylow theorem) then inclusion does not work.

There is a simple counterexample: The cyclic P group of order 3.

Of course, P has order 3.
Hence, number 3 is a factor of order of P, but P has an inclusion property mentioned by Nick.
Of course, your argument couldn't be right, since you have never used the property that group is a part of a field.

Last fiddled with by literka on 2013-05-17 at 15:08

2013-05-17, 16:24   #5
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by literka Few remarks: 1. In the first part of a post you were proving something converse to what Nick wrote. Nick wrote a theorem in one direction. So, it is unrelated to Nick's question.
Agreed. I took the puzzle as an if and only if.

Quote:
 2. It cannot be done by direct construction. There are groups with subgroups 2,4,8.. without this inclusion property. You are saying that something can be done and you are not doing this.
Direct construction certainly works for GF(3^2)....
Yes, there are groups without this property. But IIRC the multiplicative
sub-group of a field is isomorphic to the additive subgroup of a finite
ring (where the ring is not necessarily a field), and for this representation
the construction is not hard.
Quote:
 4. In additional post (post #3) you wrote that you found an argument. May be it is an argument but a wrong argument. Since it is written in an unclear way let me state what you wanted to prove: if the group order has an odd prime factor (and hence a sub-group of odd order by the Sylow theorem) then inclusion does not work. There is a simple counterexample: The cyclic P group of order 3. Of course, P has order 3. Hence, number 3 is a factor of order of P, but P has an inclusion property mentioned by Nick. Of course, your argument couldn't be right, since you have never used the property that group is a part of a field.
I thought that I had addressed the question of when the group was cyclic.

Since the (multiplicative) group order of F is #F-1, and since #F is prime
or the power of a prime, this group can only be cyclic in the cases I
mentioned.

 2013-05-19, 09:07 #6 Nick     Dec 2012 The Netherlands 3·541 Posts Here is my solution: As a finite field, F has pⁿ elements for some prime number p and some integer n≥1. The group F* formed by its non-zero elements is cyclic, from which it easily follows that the subgroups of F* are totally ordered by inclusion if and only if F* has exactly qm elements for some prime number q and some integer m≥0. So the puzzle reduces to solving pn-1=qm. If m=0 then F has pn=qm+1=2 elements. Suppose n=1 and m≥1. Then q≥2 and qm+1 is prime from which it follows that q is even and m=2k for some integer k≥0 (this is a useful lemma from Hardy & Wright's Introduction to Number Theory). As q is prime, it follows that q=2 and #$F=p=2^{2^k}+1$, a Fermat prime number. Suppose m=1 and n>1. Then p-1 divides p^n-1 which divides q, so p-1 divides the prime q. If p-1=q then n=1, a contradiction, so p-1=1 and thus p=2. Hence #F-1=2n-1=q and #F-1 is a Mersenne prime. Finally, if m>1 and n>1 then, as R. D. Silverman pointed out, we can use the Catalan conjecture (proved by Mihailescu) to conclude that p=m=3 and q=n=2 so #F=9. As was also noted above, the converse is true as well, and is simple to verify.
 2013-05-19, 11:44 #7 literka     Mar 2010 110000002 Posts Of course, proof is complete. Probably here are people, who are not number theory specialists. So, it would be better to show also that there are fields F with #F=9. Hence, to show that we are not talking about empty set. Probably it is something very simple but still worthy to mention.
2013-05-19, 13:30   #8
Nick

Dec 2012
The Netherlands

162310 Posts

Quote:
 Originally Posted by literka Of course, proof is complete. Probably here are people, who are not number theory specialists. So, it would be better to show also that there are fields F with #F=9. Hence, to show that we are not talking about empty set. Probably it is something very simple but still worthy to mention.
The fact that a field with precisely 9 elements exists (and only one if you count isomorphic fields as equal) is indeed a simple consequence of Galois theory.
For a specific model of it, we could take the Gaussian integers modulo 3, i.e. the set of all numbers expressible in the form a+bi where a and b are integers mod 3 and i²=-1 (mod 3).

 Similar Threads Thread Thread Starter Forum Replies Last Post emily Math 34 2017-07-16 18:44 pepi37 Conjectures 'R Us 4 2015-10-09 14:49 michael Math 31 2015-09-04 05:57 ixfd64 Lounge 3 2004-12-27 21:13 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 16:36.

Thu Mar 4 16:36:15 UTC 2021 up 91 days, 12:47, 0 users, load averages: 2.18, 2.18, 2.24