Re: FLTMA: A little group theory


The Dougster wrote:
Chip Eastham wrote:
The Dougster wrote:

In such group of numbers coprime to modulus m, there will be a
generator a, such that the powers of a, { a^n | n is in Z } are
precisely the elements of the group. How many generators will there be?
Well, there are phi(m) elements in the group. There are phi^2(m) or
phi(phi(m)) generators coprime to phi(m).

We sorted through this earlier. The (multiplicative) group
of residues coprime to modulus m is not generally cyclic
and doesn't have a generator except in special cases.
[See earlier msg for a list of these and references.]

Thanks for reminding me, Chip. That was way wrong. IF this group is
cyclic, there are
phi(phi(m)) generators, correct?

Yes, a cyclic group of order phi(m) has phi(phi(m)) generators,
the number of residues mod phi(m) coprime to phi(m).

Let me check to see if I am hearing you. There are groups of order
phi(m) that are cyclic, and there are multiplicative groups of the same
order, with elements coprime to m but they aren't always cyclic. That
is, if a group is of this second type, it need not be of the first type.

Right.

In every case, the group is finitely generated, no?

Right, the multiplicative group Z/mZ* is finite, so as Gerry
points out, clearly finitely generated. In fact if you know
the prime factorization of m, you can write down the
structure of Z/mZ* corresponding to the representation
theory of finite abelian groups, ie. as a direct sum of
cyclic abelian groups, etc.

If this group isn't cyclic, there might be a cyclic subgroup of this
group containing x and y within which the argument relating even or odd
z, shared factors, and differing periods would apply. That cyclic
subgroup might even be the one generated by x and y. I don't know. We
skipped that chapter!

[snip]

I'm not sure where you're going here. Let me try to
sketch what I think you are interested in without
broaching the question of whether Z/mZ* is cyclic.

Generally the elementary approach to FLT fixes an
exponent n > 2 and tries to prove that no solutions
x,y,z (xyz > 0) exist. In your case, the approach is
more a matter of fixing x,y,z > 0 such that:

x < y < z < x+y, (x,y,z) = 1, and xyz is even

and showing that no odd exponent n satisfies:

z^n = y^n mod x
z^n = x^n mod y
x^n = -y^n mod z

From the above we can deduce some of the
other results you want:

x > 1
x,y,z are pairwise coprime

Thus the set of exponents n for which:

z^n = y^n mod x

will form a cyclic subgroup of Z/phi(x)Z,
because the above can be rewritten:

(z/y)^n = 1 mod x

Thus the exponents n which satisfy
this are simply the integer multiples
of the multiplicative order of (z/y) in
Z/xZ*. We know this order divides
phi(x), and we can rule out this order
being 1 (because 0 < z - y < x, so
z/y is not already 1 mod x).

Similarly the exponents n for which:

z^n = x^n mod y

are simply the integer multiples of the
multiplicative order of (z/x) in Z/yZ*.
This order must divide phi(y) and we
can again rule out this order being 1
(again because 0 < z - x < y, so z/x
is not already 1 mod y).

So far, so good. Combining the first
two constraints on the exponent n:

z^n = y^n mod x
z^n = x^n mod y

we get that n is a multiple of both
orders, ie. a multiple of their least
common multiple. Note that for n
odd to be a solution, we need both
orders to be odd.

The third constraint with its minus
sign is a bit trickier. It can be
rewritten:

(x/y)^n = -1 mod z

There are two possibilities. One
is that there is no such exponent,
as for example when:

x = 5, y = 6, z = 7

Then (x/y) = 2 mod z, and since
the multiplicative order of 2 is 3
in Z/7Z*, there is no solution of:

2^n = -1 mod 7

The other possibility is that there
is a solution, in which case it
necessarily happens that order
of (x/y) in Z/zZ* is even, and the
only solutions are congruent to
half that order mod that order.

For example consider:

x = 4, y = 5, z = 7

Then (x/y) = -2 mod z, and:

(-2)^n = -1 mod 7

whenever n = 3 + 6k.

Exercise for the reader:

Consider x = 7, y = 10, z = 13
and determine the exponents
which respectively satisfy each
constraint:

(z/y)^n = 1 mod x
(z/x)^n = 1 mod y
(x/y)^n = -1 mod z

and show that collectively the
exponents which satisfy all
three constraints are the odd
multiples of 6.

regards, chip

.

Relevant Pages