Re: FLTMA: A little group theory


The Dougster wrote:
Chip Eastham wrote:
The Dougster wrote:
Chip Eastham wrote:
The Dougster wrote:
Hello. I have completed the first of three tests in the abstract
algebra course at the CoCo. We are up to cyclic subgroups in Fraliegh's
seventh edition of A First Course in Abstract Algebra.

From FLT we have, by way of contradiction (I think that is how you say
it)

a^n + b^n = c^n

and so

x^p + y^p = z^p where gcd(x,y,z)=1, one of {x,y,z} is even, p is prime,
and x<y<z<(x+y).

I'd like to look at (x^p + y^p) (mod z). This implies x^p == -y^p (mod
z). x^p is the additive inverse of y^p, in addition modulo z.


Hi, Doug:

I don't see what Fermat's Last Theorem has to do with
any of the rest of your post.

In cyclic group notation in our text we write <x> for all the powers of
x modulo some implied z. <x> is the cyclic subgroup generated by x.

The phi function is written phi(n) = | { x | gcd(x,n)=1, 0<x<n } |.
That is, the measure of the set of numbers coprime to n. We have a
theorem in our text that if element a generates G, that is, <a> = G,
then | <a^s> | = n / (gcd(n,s)). Each of <a^s> is a subgroup of G, and
so contains the inverse of element a^s under the group operation, which
we call *. There are phi(n) generators of an arbitrary group isomorphic
to Zn.

For every z, is there an Abelian group, Zz - 0, of numbers from 1 to
z-1 under multiplication modulo z, with associativity, an identity, 1,
in the group, and a muliplicative inverse for every element in the
group?

Your example of multiplication mod n = 5:

For example, from 3^2 + 4^2 = 5^2, with * multiplication modulo 5:

* 1 2 3 4
1 1 2 3 4
2 2 4 1 3
3 3 1 4 2
4 4 3 2 1

Isn't that a group?

Yes, the multiplicative group Z/5Z* is a group of phi(5) = 4 elements.
More generally for prime p, phi(p) = p-1 and Z/pZ* is a group of
order p-1 that is cyclic as noted earlier.


So, for arbitrary n, there is a multiplicative group Z/nZ* consisting
of the phi(n) residues coprime to n. This group is cyclic only in
some special cases. Consider for example the multiplicative
group Z/15Z* which has phi(15) = phi(3)*phi(5) = 2*4 = 8 elements.
This is not cyclic, being in fact Z/2Z X Z/4Z.

I don't follow this. What is the notation Z/nZ*? The integers divided
by the nonzero multiples of n? I can understand that phi(5) is 4, and
that the table above has 4 elements.

More generally Z/nZ* is the multiplicative group of all residues
mod n that are coprime to n. Notice that the condition of x
having a multiplicative inverse mod n:

ax = 1 mod n for some a

is equivalent to the existence of a,b such that:

ax + bn = 1

which is well-known to be equivalent for a nice ring like the integers
to 1 being the greatest common divisor of x and n. I.e. residues
in Z/nZ have multiplicative inverses if and only if they are coprime
to n.

> What is the X? In our text, x is the Cartesian product...

Yes, I'm saying that multiplicative group Z/15Z* is (isomorphic to)
the Cartesian product of abelian (additive) groups Z/2Z and Z/4Z.
My point is that it is an abelian group but not cyclic. To see it,
notice that Z/2Z X Z/4Z is a group of order 8, but no element in
this group has order greater than 4.

Yes, there is some (simple?) notation I am missing to follow this.

I guess I should work out:

* is multiplication modulo 6:

* 1 2 3 4 5
1 1 2 3 4 5
2 2 4 0 2 4

That's not even a group, much less cyclic. Hm. I have answered my own
question. No, there is not such a group for *every* n.

Well, the multiplicative group Z/6Z* has two elements, {1,5}.
It is cyclic but it doesn't have as many elements as you'd
hoped! :-(

Now, you write there is a group of the phi(n) residues coprime to n. 2
is not coprime to 6. Neither are 3 or 4. 5 and 1 are coprime to 6.

* = * mod 6
* 1 5
1 1 5
5 5 1

Hm. In FLT, for every possible x^n + y^n = z^n there *is* a group G
under multiplication modulo z with elements the phi(z) residues of z
coprime to z, containing all possible values of x and y as elements.
This group is not always cyclic, but is always Abelian. Right?

I think I am getting the content but the notation is new to me.

This group is the powers of x and y mod z only if it's cyclic. Right?

I'm with you on the multiplicative group Z/nZ* having order phi(n)
and being Abelian but not always cyclic. Since it is closed with
respect to multiplication, you can take as many powers of the
elements coprime to n as you like & remain in the group. In
fact Euler's generalization of Fermat's "little theorem" tells us
about a shortcut to doing such a computation that amounts to
Cauchy's result for a finite group, that the order of an element
divides the order of the group.

The cases where the multiplicative group Z/nZ* is cyclic are:

n = 2, n = 4, n = p^m, n = 2*p^m

for odd prime p and integer m > 0.

regards, chip

If z is 2, 4, p^m, or 2*p^m, then there is a cyclic group I can call G
containing all possible values of x and y for x^p + y^p = z^p and all
powers of x and y mod z.

Now there are also z^p - x^p = y^p and z^p - y^p = x^p to consider.

Is it true that for a counterexample to FLT, *at least one* of {x,y,z}
must be 2, 4, p^m, or 2*p^m?

I do notice that for all x^2 + y^2 = z^2, at least one of {x,y,z} seems
to always be p^1, but I don't see that that has to be true for the
equation to power p.

Solutions to the case of exponent 2 are call Pythagorean
triples, and an exhaustive parameterization of these has
been known since at least the time of Euclid. Even if we
require x,y,z to be pairwise coprime, it's not true that one
of them must be a prime (though it might seem that way
from looking at the first few cases). For example:

63^2 + 16^2 = 65^2

I see that you want to combine addition and multiplication,
so I'm guessing that you can't work in just Z/nZ*, which is
not closed under addition.

This was not the week to try to quit smoking tobacco! Grrrr....
Thanks. Doug

You go, guy! I've lost too many friends and family to the evil
weed, and the younger you stop smoking the better.

best wishes, chip

Hello, all.

Was out of the house and using my nicotine inhalers, not smoking
tobacco, from 11:30-7:30 yesterday. Started smoking again when I got
back.


What I am looking for is something like this:

From a^n + b^n = c^n in Z we have
x^p + y^p = z^p with (x,y,z)=1, one of {x,y,z) even, p prime, and
x<y<z<(x+y) in Z+.


Doug wrote:

Also,
(x^p + y^p) mod z + (z^p - x^p) mod y + (z^p - y^p) mod x = 0 or
equivalently
(x^p + y^p) mod z * (z^p - x^p) mod y * (z^p - y^p) mod x = 0

Well, these aren't equivalent, even overlooking the use of
"mod" as an operator, which math guys generally avoid.

It seems rather that you should be saying:

(x^p + y^p) = 0 mod z, and
(z^p - x^p) = 0 mod y, and
(z^p - y^p) = 0 mod x

But if we look at sequences with (x,y,z) = 1, one of {x,y,z} even, and
x<y<z<(x+y)

(x^n + y^n) mod z + (z^n - x^n) mod y + (z^n - y^n) mod x or
(x^n + y^n) mod z * (z^n - x^n) mod y * (z^n - y^n) mod x

by hand waving arguments (call them a lemma), we find that n is always
2 or composite, never an odd prime.
So FLT is proved.

I think I'd spend a bit of time trying to search out
a counterexample. You're conjecturing something
stronger than FLT, which implies (though you may
not have realized it) that the above can only occur
if n is a power of 2.

At the point "We find" we need something to show the orders of the
cyclic groups differ. That would show the 0 occurs at composite n,
never at p odd prime.

That's why I wrote all this.

We have x,y,z coprime, but the associated multiplicative groups are of
order phi(x), phi(y), and phi(z). Marsaglia provides that the PRNS
(pseudorandom number sequence) a^n mod m with (a,m) = 1 has a period
dividing phi(m), and an algorithm for finding the period of the PRNS
exists, either from Marsaglia or someone else, and has been discussed
here in sci.math.

Doug asked:

Is this period the order of the element in the associated
multiplicative group?

|<a>| in Z sub phi(m)?

The order of a in multiplicative group Z/mZ*, yes.

I am up to <a> = G ==> | <a^s> | = n / gcd(n,s) in our text. We
actually skipped over section 7, Generating sets, which is interesting
because {x,y} generatese a subgroup H of Z sub z. Or something like
that. We start permutations tomorrow.

Doug

.

Relevant Pages

  • Re: FLTMA: A little group theory
    ... the measure of the set of numbers coprime to n. ... z-1 under multiplication modulo z, with associativity, an identity, 1, ... What is the notation Z/nZ*? ... This group is the powers of x and y mod z only if it's cyclic. ...
    (sci.math)
  • Re: FLTMA: A little group theory
    ... We are up to cyclic subgroups in Fraliegh's ... the measure of the set of numbers coprime to n. ... z-1 under multiplication modulo z, with associativity, an identity, 1, ... What is the notation Z/nZ*? ...
    (sci.math)
  • Re: FLTAA: Field structure p = 2, p>2
    ... Zmn is cyclic when m and n are coprime. ... Z4 (preferably written Z/4Z) is cyclic as is Z/nZ for any natural ... The product A x B of two finite groups is cyclic if and only if A and B ...
    (sci.math)
  • Re: Winograd FFT for a power of two?
    ... powers of two. ... that the transform size needs to be a product of two coprime numbers. ... ASIC/FPGA Design Services ...
    (comp.dsp)