Re: FLTMA: A little group theory


The Dougster wrote:
There is a probem with FLTMA1.exe, at
ftp://users.aol.com/DGoncz/Education/NVCC.

I compute a quotient, then take the power. It doesn't work out.

I call the quotients qxiyz for quotient of x divided by y mod z,
qyixz similarly, and so qzixy and qxiyx. I call the inverse y mod z
iyz, and so
ixz, ixy, and iyx.

I find (x * iyz)^n mod z =/= qxiyz^n mod z

I was confused about how Chip Eastham got to (x/y)^n == -1 mod z but it
seemed right, and I think I understand it now, but working out y * iyz
= 1 mod z to solve for iyz, and computing qxiyz = (x * iyz) mod z
before looking at the powers qxiyz^n mod z just doesn't seem to work.

Have I made one too many substitutions and lost the validity of the
modular arithmetic?

Most likely it's a typo but I am not seeing it.

A couple of points. First, for some values of x,y,z there
will not be a solution for (x/y)^n = -1 mod z, so your code
will have to report these failures "nicely". This contrasts
with congruences (z/y)^n = 1 mod x and (z/x)^n = 1 mod y
which are always solvable, resp. by some divisors of
phi(x) and phi(y). Ie. elements of a multiplicative group
must have an order.

What I noted about cases when (x/y)^n = -1 mod z does
have a solution is that then n is half the order of (x/y) in
Z/zZ*.

The converse is not true, though. Consider the residue
in Z/15Z. The order of residue 4 is 2, but clearly half that
order does not give a power of 4 equal to -1 in Z/15Z.
In fact you can run through all possible powers of 4 in
Z/15Z without getting to -1.

So my recommendation for solving (x/y)^n = -1 mod z
is to compute the order of (x/y) in Z/zZ* just as you
would for the other two congruences. If this order is
not even, you are done in that there is no solution.
If the order is even, you must verify whether or not
half the order gives (x/y)^n = -1 mod z.

Finally we have three simultaneous congruences
for the exponents n (assuming the third condition
here can be satisfied at all):

n is a multiple of the order of (z/y) in Z/xZ*
n is a multiple of the order of (z/x) in Z/yZ*
n is an odd multiple of half the order of (x/y)
in Z/zZ* (if a solution exists)

regards, chip

.

Relevant Pages

  • Re: FLTMA: A little group theory
    ... I compute a quotient, then take the power. ... n is a multiple of the order of in Z/xZ* ... Something very close to that, if m divides n, which I think I've seen ...
    (sci.math)
  • Re: |[IRL] Didnt we already win this fight?
    ... the government (welfare, unemployment insurance, whatever) because I'm ... Health insurance (at least until we have some sort of sane single ... I think that multiple marriage has acquired a bad reputation because ... women with a reasonably equitable power balance in a committed, ...
    (rec.games.frp.dnd)
  • Re: Is the BBC deliberately degrading FM?
    ... You are comparing apples to oranges. ... If you use multiple parallel ... guard bands is not inefficient. ... Note that that is AVERAGE power ...
    (alt.radio.digital)
  • Re: Is the BBC deliberately degrading FM?
    ... You are comparing apples to oranges. ... If you use multiple parallel ... Sorry, but you're just looking for excuses because you said that OFDM "IS inarguably inefficient", when in fact OFDM is nothing of the sort, ... has identical average power efficiency to 8-VSB with the same error correct ...
    (alt.radio.digital)
  • Power Of The Day -- Virgo
    ... You have the power of neatness. ... your final challenge total is a multiple of 5, ... Choose one player to either fill his hand to 7 cards or discard ... Virgo only wins the challenge for multiples of 10. ...
    (rec.games.board.ce)