mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2013-05-14, 18:56   #1
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·751 Posts
Default 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.
Nick is offline   Reply With Quote
Old 2013-05-17, 13:27   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Nick View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-05-17, 13:32   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-05-17, 15:07   #4
literka
 
literka's Avatar
 
Mar 2010

2×83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
literka is offline   Reply With Quote
Old 2013-05-17, 16:24   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by literka View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-05-19, 09:07   #6
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

5DE16 Posts
Default

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.
Nick is offline   Reply With Quote
Old 2013-05-19, 11:44   #7
literka
 
literka's Avatar
 
Mar 2010

2468 Posts
Default

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.
literka is offline   Reply With Quote
Old 2013-05-19, 13:30   #8
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·751 Posts
Default

Quote:
Originally Posted by literka View Post
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).
Nick is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 20:09.

Sat Nov 28 20:09:07 UTC 2020 up 79 days, 17:20, 3 users, load averages: 2.82, 2.14, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.