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