THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Interim Engineering Report REDUNDANCY IN RESIDUE NUMBER SYSTEMS T.R.N. Rao ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1963

TABLE OF CONTENTS Page NOTATIONS v SUMMARY vii I. INTRODUCTION 1 II. REDUNDANCY IN WEIGHTED SYSTEMS 2 III. ACKNOWLEDGEMENTS 13 REFERENCES 14 iii

NOTATIONS < ml,m2,...,mn > = least common multiple of the integers mlm2,...,mn ZM = integers modulo M = [0,1,2,...,M-l} |x|mi = residue of X with respect to modulo mi or X x- i mod mi 0 < i < mi (ml,m2,m3,.. y,mn) = the greatest common divisor of the integers mlm2, ~ mn XIY = X divides Y XfY = X does not divide Y v

SUMMARY This paper investigates the conditions for a finite, redundant residue system using the moduli ml,m2,... mn to represent integers modulo M. It is proved that for a general residue system (without any restriction on moduli) it is necessary and sufficient that M be a proper divisor of the product of moduli in order that the system be redundant and weighted. It is also proved that for a residue system if M = < mi, m2,... mn > there exist exactly d sets of digit weights for the system where d is called the factor of redundancy and is given as n 7cmi mlm2... m i= d = < mlm2...,m n > M vii

I. INTRODUCTION There has been a great deal of interest in the problem of residue number systems. In spite of the advantage of not having carry propagation in addition, residue systems pose considerable difficulty in the determination of sign, magnitude and division. Much of the work has been done on only the case of residue number systems with moduli pairwise relatively prime. Such a system is non-redundant and has the algebraic structure of an R-space,1 or can be given the structure of a Z-module. For a more general case of a nonredundant weighted number system, there is significant work on the necessary and sufficient conditions on the permissible digit weights of non-redundant weighted systems by H. L. Garner.3 It was shown that the p matrix representation of the digit weights modulo the corresponding modulus |pi Im can be arranged to have a lower diagonal form, with the diagonal elements relatively prime to the corresponding modulus, only when it is a mixed base system. Redundancy in number systems can be introduced in several ways. However, if a redundant system is linear4 and homogeneous, then it is possible that we can obtain the conditions on the digit weights. Very commonly we obtain a redundant weighted system by choosing a weighted system N of cardinality larger than M and forming a map ~: N + ZM. The notation here is 4 the same as in the earlier technical note, where N is a system of representation, satisfying: 1

(1) N = D1 x D2 x *. x Dn Di =[0, 1, 2,... mi-l), Di is called the ith digit set and mi the ith modulus. any element x e N is of the form (x1, x2... Xn) where xi e Di (2) (i) N is closed under the operation addition x,y E N -—.x + y e N. (ii) 0 = (0, 0,...,0) E N such that x + 0 = 0 + x = x, x E N (3) a mapping Cw: N + ZM such that w(x + y) = I u(x) + o(y) M 4 we recall the definition of a weighted system from the Technical Report, as a number system whose weighing function c is linear and homogeneous. II. REDUNDANCY IN WEIGHTED SYSTEMS n In redundant systems,N representing ZM(M < 1 mi); d: N + ZM can be written sometimes more conveniently as a composition of two mappings * and f such that Z = |f N + Zimi f ~ZTmi + ZM { is a non-redundant (1-1) transformation and is linear and homogeneous. N representing Z.mi will be a non-redundant, linear, homogeneous function,. It is sufficient that f is a ring homomorphism, and the same arithmetic structure as in the non-redundant case can be retained in the redundant system also. In that case, the pi of the non-redundant system of digit weights remain virtually the same as the digit weights of the redundant system except that 2

IPi M replaces pi. If there are no arithmetic restrictions placed on the redundant system (i.e., for example, if carry propagation to both left and right is permitted), then f need not be linear. Some of these notions can be understood from the results obtained below. RESIDUE SYSTEM Lemma 1. For a residue system N with moduli ml, m2,...,mn, we have: Pi, P2,-.',Pn c ZM are the digit weights if and only if (1) Pimi = 0 (mod M) n (*) (2) Z i = 1 (mod M) J Proof. Let pi, P2,...,p be the digit weights, and if ( is the weight function Z(1, o, 0,...,0) = pi (0O,..., 1,...0) = Pi ith place Adding (0, O,...,1,...,0)mi times, we have /(O,,0...,mi,0,..., 0) = 0 = |miPilM =0 for i=l,2,n Since 1 -1 mod mi for i = 1,2,...,n (1,1,,1,...,1) = 1 n /(1,1,...,1) = L2 PiI = 1 5

Assume pi c ZM such that pjimi - O(mod M) i = 1,2,...,n Z pi - l(mod M) for any X e ZM let X = xi mod mi C-aimOX = IPiXilM X Xi mod m i = 1.. X = kimi + Xi for some integers ki XpL = k1m1lp + xlp1 Xp2 = k2m2p2 + X2p2 Xpn = knmnpn + XnPn Adding |X(p + P2 +.+n) IM - kiPi + Xi Pi M |v PI X = xi P i i=l P, P2...... Pn are a set of digit weights of the system N. By using the lemma we may be able to check whether any set of numbers can be called the digit weights if the set satisfies the two conditions of (*). NOTE: In a more general case of a residue system, (1,1,...,1) may not represent 1 E ZM. Here the conditions (*) are modified by a new set of conditions (**) given below~ IL

mii = O mod M, i = 1,2...,n (**) (Pl,P2, —,Pn,M ) = 1 It is easy to prove that for such a system the following Lemma 2 can be substituted for the earlier one. Lemma 2. PlP2, —Pn is a set of digit weights for the residue system N with moduli ml1m2,.. mnmi i - 0 mod M i(**) (Pl,P2,...,PnM) = 1 The following theorems are for residue systems which have a representation (1,1,...,1) for 1, and so use Lemma 1. However, they can all be proved equally well by using Lemma 2. Theorem 1. A necessary and sufficient condition that a congruence n ki mi - l(mod M) where M = < mlm2...mn > is solvable for kl,... kn is that (M/ml, M/m2,... M/mn, M) = 1. Then there are exactly d sets of solutions to kl, k2,...,kn, such that 0 < ki < mi - 1 and mm2... mn d =M 5

Proof. Let M12 =) m1m2 (ml, m2) = di2, M = 12 dl2 (M12, m3) = d13, M = mlm2m3 (M13, m4) = d14, m=ldm2m3 (Mzs, m4) = dz4, m44 = d12dl3d14 mEm2 ~~~ mn (MI n-i, mn) = d n, M Mm = --- in,~ dl2d13.... din d in the theorem is now obtained by -mm2''' m d =mlm2 m3 = d12dl3.. din The first part of the theorem stating the necessary and sufficient condition for solvability is well established and proved in most of the textbooks on number theory.5 However, we will show that (M/ml, M/m2,..., M/mn, M) = Let (M/ml, M/m2,..., M/mnn M) = d then (M/(mLd),M/(m2d),..., M/(mnd), M/d) = 1 / Mi M/ (R/ml, R/m2..., /mn, M/d) = 1 So mil M/d for i = 1,2,...n. M/d is a common multiple of ml, m2,..., mn. 6

The least common multiple, M divides all common multiples of ml,m2,...,mn M.'. M d which is impossible unless d = 1. We have proved (M/, M/m,.. M/mM/mn, M) = 1 n i = 1 mod M mi i=l l + k2 + +kn = l(mod M) From the definition of d12,... dln we have M M M M ml m2 m mn- m2.. mn mlm3..... mn mm2.. mn-n \d12 -d d2d13dn d2dl3..n dln dln using the formulas (1), (2) and (3) given below (1) If (ml, m2) = dl2 then -- d ) = M d( dl2 dl2 (2) (t ) = ); (ta, tb) = t(a,b) (3) (x1, X2,... Xn) = ( (((x x2), x), x4)..., xn We have m2 * mn mlm3... mn m_... mn di2...din d12... din d13... dln m3... mn mm2m4.... mnn \ d3... dn d12d3... din dl4... dln 7

because (M12 m3\= 1; (M12, m3) = d1; M = M 2 \ 3 d13 dl2 Continuing the process, we get mn-1 mn m1m2...... mn-2in mn dln-ldln dl2d3.... din din because mnn-l Min-i 1 k dl,n-1 dl,n-1 M M, M = mn M M M M kl + k + + kn- n + kn l(mod M) in1 in2 n-'M~in-n in From the above two equations and from we have M min 1 and kn M- l l(mod mn/dn) n mn kn has exactly one solution mod mn/dn; however, it has dln solutions mod mn or 0 < kn < mn-i. Now substituting for kn one of the di,n possible values we obtain a congruence in n-l variables 8

M +M M M kl + k2 + kn- n - (1 - kn mn) (mod M) This equation is divisible on both sides by mn din and dividing thus we have Mln-l M1,n- + Mn- Cn- (mod Mn- i) mi m2 mnRepeating the same step (Ml Mn- M, n-i M,nn 1 = mn-1 ml m2 mn-2 dl,n-1 we can show that kni has exactly dl,n-_ solutions modulo mni and kn_2 has dl,n-2 and so on. This proves that we have a total of din dl,n-1 dln-2... d12 = d solutions for kl, k2,..., kn. Such that 0 < ki < mi - 1. Hence the theorem is proved. From the above theorem we have 7 ki Mi = l(mod M) which has d sets of solutions for kl,..,kn. Such that ki Zmi Now applying the conditions on the digit weights of a residue system N with the operating moduli mi, m2... mn (1) mi Pi = 0 mod M 9

(2) Pi - 1 mod M Pi ZM ki c Zmi we have Pi = ki M/mi n n p. = ki M/mi 1 mod M which has d sets of solutions for kl... kn, 0 < ki < mi. Thus we have proved the theorem stated below. Theorem 2. For a residue system N with moduli ml, m2,.... mn representing integers modulo M where M = < mi, m2,..., mn >, there are exactly mlm2... mn d = M sets of digit weights. EXAMPLE: Let us take a residue system N with moduli 6, 10, 21 representing Z210 which has 6. lo. 21 d = 210 = 6; m = 6, m2 = 10, m3 = 21. The six sets of digit weights are given below. Pi P2 P3 0 21 190 35 126 50 pi + P2 + P3 - l(mod 210) 175 126 120 70 21 120 mlpl - m2P2 - m3p3 0(mod 210) 105 126 190 140 21 50 Theorem 3. mi, m2,..., mn are the moduli of a residue system N. N can represent integers modulo M, if and only if M is a divisor of <ml, m2,...,mn > 10

Proof. If N is a residue system, then 3 pi, P2,..., pn ZM such that (1) Pimi - 0 mod M n (2) Pi 1 mod M 1 for any i if (mi, M) = 1 Pimi - 0 mod M =ki M M Pimi (M,mi) 1 *'. M/pi Pi = ci M for some integer Ci O(mod M.) This means for any modulo that is relatively prime to M its digit weight is zero. Such digits exist in the system as purely redundant digits. As sume there are r such bits where 0 < r < n. If r = n then Pi = 0 for i = 1,2,...n and E Pi - O(mod ) which contradicts condition (2). Now reordering the moduli so that the last r moduli mn-r+i, mn-r+2,..., mn are the ones that are relatively prime to M. Let (M, mi) = di for i = 1,2,..., n-r and M r = M.' > 1 di >1. 11

Then applying condition (1) we have Pimi - O(mod M) = kiM Dividing by di p. mi k M di i di mi M. Let mi = m = di such that (m'i, M'i) = 1 ki M Pi m' M ci i for some integer ci for i = 1,2,...n-r. i di Applying condition (2) we have n-r ci M - CM = 1 This equation has solutions for pi if and only if M M M )=i. ( d d2' d_ ) This is possible only if M = < d, d2,... dnr > m' M i m mn''' which implies that M \< ml m2,..., mnr > 12

and also divides < mi, m2,..., n > Now, if M < m, m2,..., mn > it is necessary to prove the following claim. Claim. N represents ZM. If we can show that 3 Pi, P2,..., Pn such that (1) Pimi = mod M n (2) ) Pi - 1 mod M, then we will have the proof completed. i=l We know that N with moduli ml, m2,..., mn represents Zt where t = < mi, m2,..., mn>. Let pi, P2... Pn C Zt be the digit weights of the weight functions n:N - Zt. Since M|t we have pimi = 0 mod t pimi - O(mod t) - Pimi O(mod M) Pi - l(mod t) -- Pi - l(mod M) so IPIM **, |'IPnlM are the digit weights for the system N + ZM. III. ACKNOWLEDGEMENTS I am grateful to Professor H. L. Garner for his guidance, and to Mr. R. F. Arnold for useful discussions in this area. 13

REFERENCES 1. D. P. Rozenberg, The algebraic properties of the residue number systems. IBM No. 61-907-176. 2. R. F. Arnold, Linear number systems, Information Systems Lab., The Univ. of Mich., Tech. Note ORA, 04879-8-T, Oct., 1962. 3. H. L. Garner, Finite non-redundant number system weights, Information Systems Lab., The Univ. of Mich, Tech. Note ORA, 04879-2-T, May, 1962. 4. T.R.N. Rao, Computer number systems, linear and non-linear categories, Information Systems Lab., The Univ. of Mich., Tech. Note, ORA, 04879-6-T, September, 1962. 5. LeVeque, Theory of numbers, Vol. 1, Addison Wesley Publishing Co. 14

UNIVERSITY OF MICHIGAN 3 9015 03695 5949