Subject: A Magic Phrase ... and A Cautionary Tale
To: SPRING-8430-L@lists.ufl.edu (POST Number Theory 1)
Fcc: ~squash/Mail/outgoing.mail
--text follows this line--
Dear Rumpelstiltskin Number Theorists and Fairy-tale Fanciers
How to spin a phrase into Gold? Here is the phrase:
"R times one-over-R mod M ...is Magic!"
i.e,
"R times [one-over-R mod M] ...is Magic!"
In symbols:
R · <1/R>_M = Magic.
/--------------------------------------------------------\
EXAMPLE:
We want to find a ring-iso from
Z_{14} × Z_5 × Z_{33} --> Z_{2310} ,
where 14·5·33 = 2310.
Lets get the SECOND magic-number; call it G.
We compute the corresponding reduced-product:
R := 14·33 =note= 462 .
We now think "R times one-over-R mod M ... is Magic!", ie.
we compute R · <1/R>_M .
Before LBolting, we might as well reduce mod 5. I.e,
462 =5= 2.
Gosh, 2 is so small that I don't need LBolt. By inspection, the
mod-5 mult-inv of 2 is -2. [You could use 3, if you prefer
non-negative residues]. I'll use symmetric-residues, so
<1/R>_5 = <1/2>_5 = -2.
Thus
G = R · <1/R>_M .
More precisely,
G =2310= R · <1/R>_M .
We can let G := R · <1/R>_5 = 462·[-2] = -924.
Of course, we can alter G mod 2310 if we want to.
So
G := -924 + 2310 =note= 1386
is fine. We could go totally bonkers and use
G := -924 + 1000*2310 =note= 2309076
for the second magic-number. However, I can't imagine why
we would want to...
\________________________________________________________/
Summarizing, we compute as follows:
M1 := 14; M2 := 5 ; M3 := 33.
And
U := 14 * 5 * 33 = 2310.
The reduced products are
R1 := 1 * 5 * 33 = 165 ;
R2 := 14 * 1 * 33 = 462 ;
R3 := 14 * 5 * 1 = 70 .
Now R1 =M1= -3 . So <1/R1>_M1 means the mod-14 reciprocal of -3.
Using symm-residues,
<1/R1>_M1 = <1/[-3]>_{14} = -5.
So the first magic number is
R1 * <1/R1>_M1 = 165 * -5
= -825 =U= 1485.
For the second, R2 =M2= 462 =5= 2. So
<1/R2>_M2 = -2,
thus
R2 * <1/R2>_M2 = 462 * -2
= -924 =U= 1386
... [Computation of third magic number left to reader.]
================================================================
A Cautionary Tale:
My lisp code compute the Magic-numbers to be
(init-moduli 14 5 33) =>= (-825 -924 -560)
and indeed the second magic-number is -924.
Suppose instead that this
Z_{14} × Z_5 × Z_{63} --> Z_{4410}
was the ring-iso that I wanted to compute. And I
REMEMBERED to check that
14·5·63 indeed equals 4410.
Good for me!
So I run my algorithm and see
(init-moduli 14 5 63) =>= Error: "MODULI not pairwise coprime"
Darn it! I FORGOT TO CHECK that the moduli-set is
PAIRWISE-coprime.
Of course, I don't need to check this at the beginning. If
I want, I can simply start computing the Magic-numbers.
I'll catch the error at some point when I try to compute
one of the
<1/R>_M
inverses. I'll LBolt and see
n: r_n q_n s_n t_n
/-------------------------------\
0: R -- 1 0
1: M q1 0 1
2:
... ...
K: 7 ? ? ?
K+1: 0 infty ? ?
\-------------------------------/
The "0" in row-[K+1] tells me that row-K is the Gcd-row.
Yet the Gcd(R,M) isn't 1 (which is what we need), but is,
in the example above, 7.
This tells me that this particular modulus M is *not*
coprime with at least one of the other moduli.
That's All, Folks.