20130514, 18:56  #1 
Dec 2012
The Netherlands
3·541 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 nonzero 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 is true). Show that #F=2 or #F=9 or #F is a Fermat prime number (one that's really prime!), or that #F1 is a Mersenne prime. 
20130517, 13:27  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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 (#F1) 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 subgroup of odd order by the Sylow theorem) then inclusion does not work. 

20130517, 13:32  #3  
Nov 2003
7460_{10} Posts 
Quote:
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 coprime. This also applies if n = 0. 

20130517, 15:07  #4  
Mar 2010
2^{6}×3 Posts 
Quote:
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 subgroup 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 20130517 at 15:08 

20130517, 16:24  #5  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Quote:
Yes, there are groups without this property. But IIRC the multiplicative subgroup 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:
Since the (multiplicative) group order of F is #F1, and since #F is prime or the power of a prime, this group can only be cyclic in the cases I mentioned. 

20130519, 09:07  #6 
Dec 2012
The Netherlands
1623_{10} 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 nonzero 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 q^{m} elements for some prime number q and some integer m≥0. So the puzzle reduces to solving p^{n}1=q^{m}. If m=0 then F has p^{n}=q^{m}+1=2 elements. Suppose n=1 and m≥1. Then q≥2 and q^{m}+1 is prime from which it follows that q is even and m=2^{k} 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 #, a Fermat prime number. Suppose m=1 and n>1. Then p1 divides p^n1 which divides q, so p1 divides the prime q. If p1=q then n=1, a contradiction, so p1=1 and thus p=2. Hence #F1=2^{n}1=q and #F1 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. 
20130519, 11:44  #7 
Mar 2010
300_{8} 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. 
20130519, 13:30  #8  
Dec 2012
The Netherlands
3×541 Posts 
Quote:
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). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
Generalized Fermat numbers (in our case primes)  pepi37  Conjectures 'R Us  4  20151009 14:49 
Special Form of Mersenne and Fermat Number Factors  michael  Math  31  20150904 05:57 
supercomputers and Fermat/doubleMersenne numbers  ixfd64  Lounge  3  20041227 21:13 
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods  optim  PrimeNet  13  20040709 13:51 