![]() |
![]() |
#1 |
Dec 2012
The Netherlands
3·541 Posts |
![]()
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 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. |
![]() |
![]() |
![]() |
#2 | |
Nov 2003
22·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 (#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. |
|
![]() |
![]() |
![]() |
#3 | |
Nov 2003
746010 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 co-prime. This also applies if n = 0. |
|
![]() |
![]() |
![]() |
#4 | |
Mar 2010
26×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 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 |
|
![]() |
![]() |
![]() |
#5 | |||
Nov 2003
22·5·373 Posts |
![]() Quote:
Quote:
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:
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. |
|||
![]() |
![]() |
![]() |
#6 |
Dec 2012
The Netherlands
162310 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 # 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. |
![]() |
![]() |
![]() |
#7 |
Mar 2010
3008 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. |
![]() |
![]() |
![]() |
#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 | |
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
Distribution of Mersenne primes before and after couples of primes found | emily | Math | 34 | 2017-07-16 18:44 |
Generalized Fermat numbers (in our case primes) | pepi37 | Conjectures 'R Us | 4 | 2015-10-09 14:49 |
Special Form of Mersenne and Fermat Number Factors | michael | Math | 31 | 2015-09-04 05:57 |
supercomputers and Fermat/double-Mersenne numbers | ixfd64 | Lounge | 3 | 2004-12-27 21:13 |
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods | optim | PrimeNet | 13 | 2004-07-09 13:51 |