3. MORE PROPERTIES OF ADMISSIBLE ARRAYS
11
In other words, for 1 j /J,,
Sj:={X\jx=Jh (3.8)
We identify Z/(r) with {j e Z | 0 j r} and let TT : Z - Z/(r) be the natural
map which takes an integer to its congruence class in Z/(r).
The crucial observation is the following: Suppose that Ai and A2 are integers
with 1 Ai, A2 m 4-1 and that l\ and I2 are integers with
0 Z i and 0 l2 .
rj\1 rj\2
Then we have
7r(77Al-i + hrjXi) = 7r(rjx2-i + hrjx2) if and only if Ai = A2 and h = /2. (3.9)
If
7r(r7Al_i+/irJAi) =7r(77A2-i4-/2rjA2)
and we know that Ai = A2, then (for l\ and I2 as above) it is easy to see that l\ = h
Thus to prove Eq. (3.9), it suffices to prove that if Ai ^ A2, 1 Ai, A2 m + 1,
then
7r(77Al-i + hrjXl) ^
TT(T)X2-I
+ krjx2) mod r. (3.10)
Equation (3.10) will follow if we can prove that
r/Ai-i ^ Vx2-i mod gcd(rjXi,rjX2). (3.11)
We can assume that l A i A 2 m + l. However,
A
2
- I
i=Xi
Our assumptions imply that
g c d O ^ P A i + i ) ! ^ and gcd(pA2-i,PA2)|rjA2.
Therefore, it follows that
gcd(pAi,PAi+i,... ,PA2)|gcd(riXi,rJA2). (3.13)
Equations (3.12) and (3.13) and the definition of an admissible array imply Eq.
(3.11) and hence Eq. (3.10). Thus Eq. (3.9) follows.
To use the observation that led to Eq. (3.9) we define, for each A with 1 A
ra + 1,
Tx = {rjx-i + lrjx | 0 I } ,
so |TA| = r/rjx. Equation (3.9) shows that Ta nTp = 0 for 1 a (3 ra + 1 and
that
ra+l
A=l
is one-to-one. Therefore it follows that
ra+l M
U^ = U( U
TX).
A=l j=l lAm+l,j
A
= j
Previous Page Next Page