CONGRUENCES, PRIMITIVE ROOTS, INDICES FOR THE FIELD byW i l l i a m Haddock Simons A Thesis submitted f o r the Degree o f M A S T E R OF A R T S i n the Department of M A T H E M A T I C S THE UNIVERSITY OF BRITISH COLUMBIA April, 1937 TABLE OF CONTENTS Section I. II. III. IV. V. VI* VII. Title Page Congruences of c o n d i t i o n . 1 E q u i v a l e n t congruences. 3 System of congruences. 3 Congruences i n one unknown. 5 Congruence of f i r s t degree i n one unknown. 5 Integer having c e r t a i n r e s i d u e s . 7 D i v i s i b i l i t y of one polynomial by another with r e s p e c t to a prime modulus, common VIII. IX* X. XI. XII. XIII* d i v i s o r s , common m u l t i p l e s * 10 U n i t , a s s o c i a t e d , and primary polynomials. 11 Prime polynomials. 12 D i v i s i b i l i t y of polynomials. 14 Congruence o f two polynomials with respect to a double modulus* 15 Unique f a c t o r i z a t i o n theorem* 16 R e s o l u t i o n of a polynomial i n t o i t s prime factors. XIV i 21 General congruence o f >t th degree i n one unknown* XV. The congruence ^,^^1 22 / O j ^*^^oc 2 4 XVI* Analogue t o Wilson's theorem i n 25 XVII. Common r o o t s o f two congruences. 26 M u l t i p l e r o o t s o f a congruence. 26 XVIII. XIX. XX. XXI. XXII. XXIII. XXIV. XXV. XXVI. Congruences i n one unknown with composite moduli. 27 Residue of powers. 30 Primitive roots. 36 Indices. 38 S o l u t i o n of congruences by means of indices. 41 Binomial congruences. 42 P r i m i t i v e roots o f a given prime. 43 The congruence ^ tt~. 46 INTR ODUG T l ON In h i s t e x t , "The Theory of Numbers and A l g e b r a i c Numbers", L. H. Reid s t a t e s , without p r o o f , that r e l a t i o n s may be proved true i n the f i e l d field of r a t i o n a l numbers. thesis t o investigate this certain /^V*0 as i n the I t i s the purpose o f t h i s statement and to supply p r o o f s wherever they may d i f f e r from those f o r the f i e l d Before doing t h i s * however, i t w i l l be necessary to c o l l e c t together c e r t a i n d e f i n i t i o n s and r e s u l t s necessary i n l a t e r developments. 1. Numbers of &u) ; Any number of r a t i o n a l fractional function of form c< = a + U When b =o -4 with r a t i o n a l co- An i n t e g e r of ~&u) i s a number o f £u) of the efficients. sub f i e l d isa where CL and b are r a t i o n a l integers. we o b t a i n the r a t i o n a l i n t e g e r s which are a of . <3- b~c found by p u t t i n g The number f o r ~c i n any number c< c< and i s denoted by <=*c ' . i s the product of i s c a l l e d the conjugate of The norm of any number °<i and i t s conjugate »< \ and i s a p o s i t i v e r a t i o n a l number; The norm of the product o f numbers o f £w)ls equal t o the product of the norms o f i t s f a c t o r s . -y^ [_c*(9 r-- ---] - ^ ±. H Thus ~^[Y] . L. H. Reid, l o c . c i t . , Chapter 5, S 15, p . 190. II. 2. Divisibility: An i n t e g e r <*< of Hu) i s said to be d i v i s i b l e by an integer ^3. i f there e x i s t s an integer f <>< - such that An i n t e g e r of i n t e g e r of the f i e l d — * are u n i t s of units, ± We which i s a d i v i s o r of every i s c a l l e d a unit of iu). then they must d i v i d e is a unit. f Evidently I f there be any / and, conversely, units any d i v i s o r of / therefore f i n d that i n I j ±" other there are four • F a c t o r i z a t i o n i s unique f o r i n t e g e r s of 4 (*•). 3* Congruences i n $ ( * ) : Two integers .<=xf ^3 i of $(*) are s a i d to be congruent with r e s p e c t modulusif to the their difference i s d i v i s i b l e b y . We then write - (3 =• or The fundamental laws of a d d i t i o n , s u b t r a c t i o n , m u l t i p l i c a t i o n , and f i e l d gu) K/-^ - d i v i s i o n o f congruences apply as i n the r a t i o n a l f i e l d . I f the i n t e g e r s of p u t t i n g two according i t may The i n the are d i v i d e d i n t o c l a s s e s , integers i n the same or d i f f e r e n t c l a s s e s as they are congruent or incongruent, mod ^pc , be proved that there are ~k S.jx'] such c l a s s e s . system of i n t e g e r s formed by taking one c l a s s i s c a l l e d a complete residue from each system, mod^# , i . e., the set i s such that no two are congruent, mod^/4 . } III. Therefore the *x, [ ,/] i n t e g e r s s\ / I . *-»•«• -/ system, mod ^jlc , where^/* - "»»<- ^f ' form a complete r e s i d u e + As s p e c i a l cases we have (a) When^x= -jz>-tx^ and prime to each other, When jo and ^ the being r a t i o n a l integers l } — ">/ " ?a + system^ mod^u. • form a complete residue (b) t » >*e. , a r a t i o n a l i n t e g e r , the i n t e g e r s of 7? (•*•) , |*>~ I - / ( lj *j form a complete residue 4. '"^l ' system, mod^/jl * The ^ - f u n c t i o n ; i s an i n t e g e r of •> As i n 1? , CpCyt.)^ where , i s defined as the number o f i n t e g e r s i n a reduced residue system, raodyU. . i n later work we w i l l make use of the theorem that i f S, } be the d i f f e r e n t d i v i s o r s o f y O t , then We need a l s o Fermat's Theorem, that i f ^ . be any i n t e g e r of £(<) and c< any i n t e g e r prime to /a. , then Notation. In the work which follows the unknown i n the field w i l l be represented Integers of the f i e l d the Greek alphabet. by the complex v a r i a b l e , f-- w i l l be denoted by l e t t e r s of In p a r t i c u l a r , the Greek w i l l be used to denote a prime of letter7f~ } I. Congruences of C o n d i t i o n . In the study of congruences we deal only with relations stating -c), a congruence between d e f i n i t e i n t e g e r s of that the d i f f e r e n c e o f two i n t e g e r s i s d i v i s i b l e by a t h i r d i n t e g e r . In congruences of c o n d i t i o n certain of the q u a n t i t i e s are unknown and the congruence i s true only f o r p a r t i c u l a r values of these unknowns. In the f i e l d we d e f i n e a p o l y n o m i a l i n the undetermined c o e f f i c i e n t s ^,, ^ i n t e g r a l f u n c t i o n of r a t i o n a l numbers. the ^ ; -— Jk^ as a r a t i o n a l ) whose c o e f f i c i e n t s are In the work which f o l l o w s , however, £u) c o e f f i c i e n t s are i n t e g e r s of the f i e l d unless a statement i s made to the c o n t r a r y . A polynomial, J- (fr>?L> > ) i s s a i d t o be i d e n t i c a l l y congruent t o zero, modyU , i f a l l i t s c o e f f i c i e n t s are congruent t o zero, mod where the Two polynomials . i s the c o e f f i c i e n t o f , / ^ ) , CpC},, i n j-^i>"' > >^ i d e n t i c a l l y congruent to each other, m o d , ) J J^)' are i f their d i f f e r e n c e i s i d e n t i c a l l y congruent to zero mod^u. . 1- = : i s the symbol f o r " i d e n t i c a l l y congruent to" while ^ i s the symbol f o r "congruent t o " and i s used when the congruence expresses a r e l a t i o n between d e f i n i t e integers. This implies t h a t the c o e f f i c i e n t s and tjPty)—; If * f^) be any / K , X. i n t e g e r s of fay moa^*, and then ^ ^ ^ ^ . - - ^ i m o d fc*. That ; y/O, ( . in must be congruent, mod^t • <r° A> °*i> (0 s h a l l have a set o f v a l u e s such that (1) holds i s expressed and of by i s c a l l e d a congruence of c o n d i t i o n , and amy integers ; ; ^ such that set o f (1). i s true i s c a l l e d a s o l u t i o n of ( 2 ) . I f c*' ^ i } o<r^ .^ such that be two c^. £ET s e t s of s o l u t i o n s j-^x^(yU (* s * ™ - ) . then e v i d e n t l y f t * ' — ' Z * - * ' - ™ ^ and and hence i f ; ''/^- - — i S a ,<=<^ '' 1 so a i s a s o l u t i o n of (2) then s o l u looked upon as i d e n t i c a l . may be considered least one ' i t o n » These, however, are In order that two solutions as d i s t i n c t i t i s necessary that at value of one unknown s h a l l be incongruent to the corresponding value of the unknowns i n the solution. second Hence i n order to f i n d the s o l u t i o n s o f congruence of c o n d i t i o n i t i s s u f f i c i e n t f o r the unknowns the n^y/} system, m o d y u . any to s u b s t i t u t e values of a complete residue II, Equivalent Congruences, Two congruences <p, •and are > '>---/ <V 0-> s a i d to be equivalent i f every s o l u t i o n o f the f i r s t i s a s o l u t i o n of the second, and i f every s o l u t i o n o f the second i s a s o l u t i o n of the f i r s t . Thus, we may add to ( 1 ) , term by term, the terms of any i d e n t i c a l congruence, thus obtaining a congruence equivalent to (1), By means of t h i s we may transpose a l l terms from one side of a congruence to the other side obtaining an equivalent congruence o f the form We may a l s o reduce the c o e f f i c i e n t s o f the terms o f the polynomial t o t h e i r smallest absolute values, mod yu. . A l s o , we may m u l t i p l y or d i v i d e both members o f a congruence by an integer prime to the modulus and obtain an equivalent congruence, III, System of Congruences, Equivalent Systems. Instead of a s i n g l e congruence, we may have a system of congruences i n j and r e q u i r e that these be s a t i s f i e d simultaneously f o r values of . By a s o l u t i o n of such a system of congruences we mean a set of values ^ ^ J^. which s a t i s f y a l l the congruences 4. of the system simultaneously. a n d ^ y the — a r Two s o l u t i o n s considered d i f f e r e n t when and only when e congruences < } . =7% V/= are not a l l true simultaneously. Two systems of congruences are s a i d to be equivalent when each s o l u t i o n o f the f i r s t system i s a s o l u t i o n o f the second and each s o l u t i o n o f the second i s a s o l u t i o n o f the first. Example: Solve the system of congruences; M u l t i p l y the 3rd congruence by Btj-i, then by / subtract from the 1st and 2nd r e s p e c t i v e l y * and Then M u l t i p l y the 2nd congruence by ;^-o~<; and add to the 1 s t . Then The 1st congruence of (c) has one and but one s o l u t i o n y = /f^ •=== - j . Then from the 2nd congruence o f (b) and from the 3rd congruence o f (a) we f i n d = J?tr<. = _ The s o l u t i o n o f (a) then i s ^-f--s^' 5. -X = IV, - /CP \ Congruences i n One Unknown, The general congruence i s one unknown i s /ty where ^ I f ^3 then + , <^ ; 0 S 2** ~ °, ^ < '> C a r e i n t e g e r s of ^ ? ^ • c be any i n t e g e r of ^V<rJ such that i s c a l l e d a s o l u t i o n of ( 1 ) , The degree o f (1) i s the degree o f the term o f highest degree whose c o e f f i c i e n t is^?o , modyO. . In order to f i n d a s o l u t i o n f o r such a congruence i t i s only necessary to s u b s t i t u t e f o r the unknown i n the e q u a t i o n the numbers of a complete r e s i d u e system, mody*. , and f i n d which ones s a t i s f y the c o n d i t i o n of the congruence, Vj, Congruences o f the F i r s t Degree i n One Unknown, The general congruence of f i r s t degree i n one unknown may be w r i t t e n i n the form where «^ ^ a r Theorem 1, The congruence, ^, e i n t e g e r s o f /£*v) . ^=^j where cxf i s prime to m Substitute for ^ CO has one, and only one s o l u t i o n . i n (1) the >i[/c] values of a complete residue system, mody*. . Then, by ^ 3 of the I n t r o - 6* a u c t i o n we o b t a i n ~>t[^] values which c o n s t i t u t e a complete residue system, modyt these values , and hence one and only one o f can be congruent %o^3 , modyU. * ' Fermat's theorem g i v e s a means o f o b t a i n i n g the r o o t o f such a congruence, f o r s i n c e A then ~< Thus &*>s/3, ~ i s a root o f the congruence / i s prime t o y u . * where Theorem 2. The necessary and s u f f i c i e n t condition f o r the s o l v a b i l i t y of the congruence i s that ^ 3 s h a l l be d i v i s i b l e by the g r e a t e s t common divisor, fulfilled & of < = > < a n d , and when t h i s c o n d i t i o n i s the congruence has e x a c t l y We s h a l l give a proof rational field. and^^ i. L e t c ^ r ^ S a n d y . =•y/ S t =^f3-*-KyU, e., so that Then. <f we must have ^ ? d i v i s i b l e by i " * Put ^ Then Since s i m i l a r t o that f o r the a r e prime to each other* Therefore tCilroots. ^ - ^ i s prime t o / * values o f ^ satisfying <T ->^^yc, . (2) has a root* ^ Moreover, a l l (2) w i l l a l s o s a t i s f y (1) since 7. we may pass from (2) to (1) by m u l t i p l i c a t i o n Therefore that ^9 be d i v i s i b l e by S is a c o n d i t i o n f o r the s o l v a b i l i t y of (1), by S , sufficient Moreover a l l •roots o f (1) s a t i s f y (2) and are therefore of the form f *• where y° i s a r o o t o f ( 2 ) . Thus i n order that we may have two incongruent roots of (1) we must have i. e. '<,y*, ^ Thus i f we , substitute for residue system, mod ^ ^ t y " . the i n t e g e r s of a reduced , which are ~K 6 i n number, we obtain a l l the incongruent roots of (1), modyc • VI • Determination of An Integer That Has C e r t a i n Residues With Respect ^0L.a Given. S e r i e s o f M o d u l i . Consider f i r s t the case where the r e q u i r e d i n t e g e r must s a t i s f y simultaneously All integers s a t i s f y i n g the two conditions (1) are of the form where <y i s an i n t e g e r of 4 *)* ( I 11 order that t h i s may s a t i s f y (2) we must have +y"> 7 or yt, f, ^ < = < -°< > , — £> x G3; 8. In order that (3) may be s o l v a b l e i t i s necessary and s u f f i c i e n t that £ divide <=<^ — ^ where <T i s the greatest common d i v i s o r of^// a n d y ^ . f 'If t h i s requirement be s a t i s f i e d and £ be a root o f (3) then every root y where of (3) must s a t i s f y ^ i s an integer of ~&t*) Then a l l i n t e g e r s s a t i s f y i n g both (1) and (2) are of the form And hence If ^ ? = f , <~^*~*< be any integer s a t i s f y i n g both (1) and (2), a l l and only those i n t e g e r s s a t i s f y both (1) and (2) which a r e congruent to ^ o with respect to the l e a s t common m u l t i p l e of the moduli of (1) and ( 2 ) . The general case of ~?t congruences may be solved, i f a s o l u t i o n e x i s t s , by a repeated a p p l i c a t i o n of the above. Hence the common s o l u t i o n s , J> , of (5) are given by where ^ i s an i n t e g e r s a t i s f y i n g a l l the congruences and X i s the l e a s t common m u l t i p l e o f the .moduli^,,---- -jyjt^ 9. A l t e r n a t e p r o o f f o r case when the m o d u l i ^ are prime to each o t h e r . In t h i s case 'modulus yr. /\ -y-.yK*. s e l e c t a /3- Z^-^ ^ . - - and we need only determine A" ^ f . F o r e a congruence K such that which has a s o l u t i o n s i n c e ^ ^ to • such that This i s always p o s s i b l e since the second implies * - i s prime . NOW p u t yO = Then ^ Z1T ^/C: <^ ^ gives the common s o l u t i o n s of the system. From (6) we a l s o have and hence since a l l o f ^ ^ except How and so ,^ are d i v i s i b l e b y / ^ we have _ j£ - /„ •? Therefore a l l integers s a t i s f y i n g (6) s a t i s f y each of the congruences ( 5 ) , Now l e t ^ a be an integer satisfying each of the congruences ( 5 ) . Then = cx'. and Hence / ^ — - / ° — ^< ; f-*'-/, ° J *-* *~^y ~£ pc u f - * " - -> c h 10. i. e. fa ~j° i s d l T 1 sible and hence by t h e i r product by each of the A . Hence ^ moduliyXy-^^. = j, 0 e <->~^-*^ A • Thus we have a method of obtaining the common s o l u t i o n o f a system of congruences i n t h i s s p e c i a l case. I f f o r =<, . — . in p we s u b s t i t u t e the i n t e g e r s of a complete residue system with r e s p e c t to the moduli/*,,y£ j - jyiS*. X r e s o e c t i v e l y , the r e s u l t i n g values of jo form a complete residue system, mod , c*^ - in y d A •••Or.'if f o r we s u b s t i t u t e the i n t e g e r s of reduced r e s i d u e systems mod^a^,^^ r e s u l t i n g values of j° jy*s.~ r e s p e c t i v e l y , the form a reduced residue system, mod A- The p r o o f s f o r these two p r o p e r t i e s are s i m i l a r to those for the corresponding theorems of Hence the number of i n t e g e r s i n a reduced residue system, mod^^y^ —y&*^. -> where^a^ )y#-~. a r e prime to each other, i s equal t o the product o f the numbers o f the i n t e g e r s i n reduced residue systems f o r each of the moduli^,, — ' ^ y * ^ a n < 3 , "therefore Polynomials i n VII. D i v i s i b i l i t y of One P o l y n o m i a l by Another With Re- spect to a Prime Modulus. Common D i v i s o r s . Common M u l t i p l e s . Let 7T- be a prime o f . Then a polynomial fa) i s s a i d to be d i v i s i b l e by a polynomial^*? J with respect to the modulus 7T~, i f there e x i s t s a polynomial j?£ ) such that 11. As a d i r e c t consequence of t h i s d e f i n i t i o n we have i. If be a m u l t i p l e , mod TT, be a m u l t i p l e , mod r " , o mod TT y of f j) ( 3 t , j J , mod nomial i s a m u l t i p l e , mod 7T, of I f f.Cj) and y £ b e and ^ ? mod 7T , of fy) and then /^j) f, (j) t~ f+t'j) J± > W t then each p o l y - of a l l that f o l l o w i t . m u l t i p l e s , mod/ , of 7- _ yf ^ ; , or i n general i f f,^) VIII. then f-,^}) i s a m u l t i p l e , c J then /<j) and > or i n general i f each polynomial p^ §) {*'=/, .?,-— ) be a m u l t i p l e of ii. of fi<j) are m u l t i p l e s , mod TT, and £.<j) he m u l t i p l e s , ^ ; be any two polynomials, ) i s a m u l t i p l e of , mod 7T~. U n i t and Associated Polynomials with Respect to a Prime Modulus, Primary P o l y n o m i a l s . We wish to f i n d whether there e x i s t polynomials that d i v i d e a l l polynomials with r e s p e e t to the modulus 7T No polynomial of degree g r e a t e r than zero can be such f o r s i n c e they must d i v i d e u n i t y , mod 77~ l the sum of the degrees of the d i v i s o r and quotient would be greater than zero, the degree o f u n i t y * Moreover i t i s evident that they must not be d i v i s i b l e by 7T~. i n t e g e r s of Hence, a l l and only those which are not d i v i s i b l e by 77~ have t h i s p r o p e r t y and are c a l l e d u n i t polynomials, mod "7 * Two polynomials which d i f f e r only by a u n i t f a c t o r , mod 77", are c a l l e d a s s o c i a t e d polynomials and are looked upon as i d e n t i c a l i n a l l questions of d i v i s i b i l i t y , mod 71". 12. I f two polynomials ? ^ J a r e each a s s o c i a t e d j mod 7T , with a t h i r d polynomial, they are a s s o c i a t e d with each other; f o r i f and ^j) ^ /i where are u n i t s , mod 7^-, and i f ^ ^ /^/^ such that ^7" f:<;>m^fo>, and then where i s an i n t e g e r 7 <=</<^ i s a u n i t , mod TT . - Two polynomials, that are a s s o c i a t e d , mod 7T~^ are of the same degree, and each i s a d i v i s o r , mod W t the other. of Conversely, i f two polynomials be each d i v i s i b l e , mod 7T y by the other, they are a s s o c i a t e d . Two polynomials having no common d i v i s o r , mod t other than the u n i t s are said to be prime t o each other, mod If . Of the.-7*CV7 — / a s s o c i a t e s of , that one having u n i t y as the c o e f f i c i e n t of i t s term of highest degree i s c a l l e d the "primary a s s o c i a t e , " mod EC. Prime Polynomials with Respect 77~ * to Prime Modulus. Determination of the Prime Polynomials, mod y", of any Given Degree. A polynomial that i s not a u n i t , mod that has no d i v i s o r s , mod 7T, 7T~, and other than i t s a s s o c i a t e s and the u n i t s , i s c a l l e d a prime polynomial, mod 7f . If 13. i t has d i v i s o r s , mod ~rr , other than these i t i s s a i d to be composite, mod 7T~* For example l e t us f i n d the primary prime p o l y - nomials, mod J** , o f any degree. We may take as a complete r e s i d u e system, mod l+< , the integers of £c<) . o / 2 3 3 } 3, V Then the primary prime polynomials o f the f i r s t degree, mod J+t , are +' > ^ ~* •> ^ * ^ ' 3 The reduced primary polynomials o f the second degree, mod -2 + -c , are 25 i n number. r - + i ^ v -j*-*/"f+3 r*?*- / J>*j+* y'V*- 3 ' 3 ^ v f+^J** y<- } + 4 3 From the primary prime polynomials o f the f i r s t degree we can form the composite polynomials, mod . These are ^ all ^ congruences ^ "/^ 7 being taken with r e s p e c t to the modulus 3+X 14. These are 15 i n number. The remaining polynomials i n (2) are the primary prime polynomials, mod and are 10 i n number. In g e n e r a l , when ~*i>l the number of primary prime polynomials, mod 77~ , of the TC^ degree i s J_ -X. where ^ X. ^ ^ Division - — , are the d i f f e r e n t prime f a c t o r s of ~TO>. of One Polynomial by Another With Respect to a Prime Modulus. Theorem 5. If -polynomial not i d e n t i c a l l y congruent there e x i s t s a polynomial £Kj} i s of lower degree than t to zero, mod fy) and by g i v i n g Let yrjf; — by and <ft<j) y f ^ ^ the remainder by ty ^) • 7 TT~, • c a l l e d d i v i s i o n , mod IT , o f c a l l e d the quotient and be any such that the polynomial The operation o f f i n d i n g SKj.) mod -JT , of <^?<j) be any polynomial and is . is i n the d i v i s i o n , We prove the existence o f a method f o r t h e i r determination; *"> ^ j> T - -i- ~<_^ be any two polynomials and l e t Consider f i r s t by the case i n which ^ — / • Divide J- £> as i n the o r d i n a r y d i v i s i o n process u n t i l we c get of lower degree than ^P^j) and a remainder having the quotient <^^) Then } /(j) from which (1) f o l l o w s . • = gCj) <p%) ->- Consider the case where Let and ^= O ^ / , mod ~7T~. be the r e c i p r o c a l , mod 7T~ , of ^ ?^ jr / V Then where ) flfg) j S a — i s a polynomial i n ^ having u n i t y as the c o e f f i c i e n t of the term o f highest degree, Divide by ^ j ^ J as b e f o r e . f<i>*£<<j)&<j)+tf,'j), Then and hence where 9^3, = (j) ?T — ^) p>Cj)+ and a r e t h - ^ ^ ^ quotient and remainder e required. XI. Congruence Double o f Two Polynomials With Respect to a Modulus. Two polynomials f, j) •» / ^ ^ J ( a r e s a i d *° ke i d e n t i c a l l y congruent t o each other w i t h r e s p e c t to the double modulus 7T, and ft/j) » where T i s a prime o f a polynomial, i f t h e i r d i f f e r e n c e , i s d i v i s i b l e by » where <=2(j) and are polynomials. I fJ - ) m O Q fj)'- • i s d i v i s i b l e , mod ^T" by t h i s may be f* j) c 16. ffy) expressed by XII. O , -^^^ = 77*^ <ft<j) Unique F a c t o r i z a t i o n Theorem f o r Polynomials With Respect to a Prime Modulus. In order t o prove the unique factorization theorem we need the following theorems. Theorem 4* If ^f%)=. <fl£) + 6?^) *^ ^~^-7T~ ^) i t 3 every polynomial that d i v i d e s , mod ~7T , both -f/j) and ^^j) d i v i d e s both and , and v i c e versa; that i s , the common d i v i s o r s , mod TT , o f and<^?£)are i d e n t i c a l with the common d i v i s o r s , mod 7T~, of and /*^>> • This i s an immediate consequence of the d e f i n i t i o n of divisibility* Theorem 5* If J~' £) ( > f-*. ) b e a n v * w o poly- nomials and "77~a prime of •$(<) , there e x i s t s a common divisor, , of J~< j) , mod ( ? (j) such that j ) ^ ) i s d i v i s i b l e , mod 7T , by every common d i v i s o r , mod ~T~ „ - of f' ^j) 3 J-*- J^ C * a n < ^ "there e x i s t two polynomials Cj) Assume that -f-^ ^) such that i s o f degree not higher than // ^ ) • h e n we may o b t a i n two polynomials c£,(j) T and /s^jJ such that J^ ^) 3 being of lower degree than j-^(^). y£ Dividing ^ Cj) i s of degree lower than f where * (j) s Similarly and since the degree o f each remainder i s decreasing we must f i n a l l y , a f t e r a f i n i t e number of steps reach a remainder ' J[ _ (g. ) which i s zero, mod 77~ . M f/ Now the common d i v i s o r s , mod , of and -f^ Cj^) are i d e n t i c a l with those of ^ ) and jz^.^ and so on u n t i l f i n a l l y those of £^ , (j)- and with those of a But and a n n ^; d i d i v i s o r of f^tj) s A</; i s a common d i v i s o r , mod of J^.^) e v i d e n t l y d i v i s i b l e by every common and • Hence ) i s the ~J)(j) > mod 17- , of fi^J • J~s ^) gruence i t s value i n terms of £(j) the 3 ( Now s u b s t i t u t e f o r first ^ £ §)•"• d r e q u i r e d common d i v i s o r , and ) r * n t n second con- e a n d y £ ) found from the congruence, s i m i l a r l y the values o f-f (j) andJ-/^) i n 3 t h i r d congruence t h e i r values i n terms of f, <j) a n d y ^ ^ and continue u n t i l the congruence 18. where^- (g) f,fj) fs-fg) and Gor: If and f_ f'(j-) each other, mod and ^_ ^.) < are expressed i n terms of s h a l l o b t a i n the congruence w e * /-_2. <jJ ^e * polynomials prime to 7T , there e x i s t two polynomials i s an i n t e g e r so we may w o <fi (j) such that < Here (j) f f i n d two polynomials M u l t i p l y i n g by the r e c i p r o c a l , Theorem 6* and f£ =v & of ^ (j) such that A we have I f the product of two polynomials be d i v i s i b l e , mod 77~ , and not d i v i s i b l e by f £f^. t W , by a prime polynomial, l e a s t one of the polynomials, f> j f } > fa. (j ) ~> i at f s IT , by ~^ £?J v i s i b l e , mod r ) and suppose that £ fj) i s not d i v i s i b l e j mod Then there e x i s t two polynomials, <tfJ ? If, ) £^ ~l~ ^)- by < such that since ) Then Hence by (1) a n ^ ^ a r e P i r m e » mG<3 - ^» *° e a ch other* > 19. where Hence f^§^ + /^(j) Cor 4: i s < ?L ^ C ) d i v i s i b l e , mod i s a polynomial. 77—, by T->^)i I f the product of any number of polynomials be d i v i s i b l e , mod ~n~ , by a prime polynomial ) , then at l e a s t one of the polynomials i s d i v i s i b l e , mod Cor 2: ) , t h e i r product i s not A polynomial and but one way » can be resolved i n one i n t o a product of prime polynomials, mod ~TT, Let be a polynomial of degree and i n i t s reduced form, mod Then A^J.) it divisible, 7T \ by " P £ ) . Theorem 7. mod t I f n e i t h e r of two polynomials be d i v i s i b l e , mod ~n~ by a prime polynomial mod ~77~ b y H P ^ ^ - 77~ . , mod lf~ 77"~. i s e i t h e r prime or has a d i v i s o r , ^^j) If say, i s prime, the theorem i s evident. If i s not prime then where the sum of the degrees of^^J^ and i s ~H and neither i s a unit. If a factor i s not a prime polynomial i t must have fi^l » m o » d s o *hat where n e i t h e r ^?^)or y (j) i s a u n i t and the sum of the r degrees of (j) and X, (j) i s the same as the degree of If (j) i s not a prime proceed as before. Since the degrees of the f a c t o r s are decreasing we must, a f t e r a f i n i t e number of steps reach a prime polynomial 20. T?^) Proceed W~* Then » mod i n the same manner with ^ (j ) • I f i t i s not 'prime we must f i n a l l y o b t a i n where f^<j) i s prime, mod IT . Continuing t h i s process we must a f t e r a f i n i t e number o f f a c t o r i z a t i o n s reach a prime p o l y n o m i a l ~ ~ I ^ L ) * m o d * such that where mod (j) ~T^(j), <^) are a l l prime polynomials, y ^ ~ , and >€. i s f i n i t e . To show t h i s f a c t o r i z a t i o n i s unique, assume that we have Then -<•* I J~? Then a t l e a s t one of the eS. (^) divisible, mod ) , must be , by^Tf (^) and hence, since they are prime, must be a s s o c i a t e d , mod 7T~ where , say « ^ i s a u n i t , mod // . 21, Proceeding as before we may show that f o r each there i s a s s o c i a t e d , mod over A f two or more 7T~, a t l e a s t one T^fj)?? ^) Sj (p . More a r e a s s o c i a t e d with each othe 'at l e a s t as many <J?^)'so are a s s o c i a t e d , mod In the same manner we may show that with each T~, <=^^) there i s a s s o c i a t e d , mod TT, a t l e a s t one Ti£ (j) , Hence the two r e s o l u t i o n s are i d e n t i c a l except f o r perhaps a unit polynomial. Any polynomial may therefore be w r i t t e n i n the form XIII, R e s o l u t i o n o f a Polynomial Into I t s Prime Factors With Respect to a Prime Modulus* The r e s o l u t i o n o f a polynomial -f(j) i n t o i t s prime f a c t o r s , mod TT , may be e f f e c t e d by d i v i d i n g , mod 77", the polynomial by each of the prime polynomials of the f i r s t degree j t ^-/, ,J - i n turn u n t i l one i s found which d i v i d e s ^Cjj , mod TT , or i t i s determined that fcj)' i s d i v i s i b l e by none of them, mod TT. Let ^ f - ^ 0 divides be the f i r s t such polynomial which * mod 7T% and l e t J~>^) be the q u o t i e n t . Continuing as before* we see whether i s divisible by any of the remaining prime polynomials of the f i r s t 22 . degree. Finally where* y4l ^) we o b t a i n contains no f a c t o r s , mod 77^ o f degree l e s s "than the second. To f i n d the prime f a c t o r s , mod 7T~, of the second degree we determine, i n the same manner as above, which (j) prime polynomials o f the second degree d i v i d e mod 77" , and s i m i l a r l y , f o r those o f the t h i r d degree, e t c . I f , however, we do not know the prime polynomials of the second degree we may determine whether d i v i s i b l e , mod 7T r ) is by any polynomial of the second degree. I f i t i s , then such a polynomial must be prime since contains no f a c t o r s of degree l e s s than the second. The same a p p l i e s f o r polynomials of higher degree. X1T. General Congruence Theorem 8, ^-(^) I f b e 2 £ t h Degree i n One Unknown. a root o f the congruence i s d i v i s i b l e , mod 7r~, by J-y° * i f /^j) a R d conversely i s d i v i s i b l e , mod 7~, b y ^ - y ° » thenyois a root of ( 1 ) , D i v i d i n g y ^ ; by ^ ~ / ° * m o d ~ » w obtain e -71— I f j° i s a root of (1) then Hence i, /<JJ ^ J~^/°J == O , mod w " 7r e, f~(^) i s d i v i s i b l e , mod 7T~, by ^ — y° - 23. Conversely i f j-'C'^) then f-(/°} = Theorem 9. o i d i v i s i b l e by g -yo , mod 7T, s » m o d a n d bence yo i s a root o f ( 1 ) . The number of roots o f the congruence where ^ " i s a prime of i s not greater than i t s degree. This follows since y4^/ cannot have more roots i t has l i n e a r f a c t o r s and i t cannot have more l i n e a r f a c t o r s than i t s degree when the modulus i s a prime* Cor: I f the congruence has e x a c t l y as many roots as i t s degree and (p(j) be a divisor s mod 7T~ of-^(^), then the congruence t has e x a c t l y as many r o o t s as i t s degree For since then every root o f (1) i s a r o o t o f e i t h e r or of Now the sum of the degrees of (3) and (4) i s equal to the degree o f (1) so that i f (3) has fewer roots than i t s degree, then (4) has more roots than i t s degree and v i c e v e r s a j which i s contrary t o theorem* 24. XV. The Congruence Theorem 10, ^ — / ^ *—>^^<r-ac^ . The congruence - has e x a c t l y as many roots as i t s degree. <^u)integers By Fermat's theorem we see that the of a reduced residue system, modyu. , s a t i s f y ( 1 ) * Moreover, since two i n t e g e r s which are congruent, m o d ^ must have w i t h ^ the same greatest integer satisfying common d i v i s o r , any (1) must have wither the greatest common d i v i s o r u n i t y * that i s * must be prime Xo^a • Hence the number o f roots of (1) i s e x a c t l y equal t o ^ V , i t s degree, . Cor. I f <f be a p o s i t i v e the d i v i s o r of •»». [V1 ~/ , then congruence <T •j CO y -r, - 0 where // i s a prime o f for -/ j , has e x a c t l y cT r o o t s ; i s a divisor of J — / and hence by the cor. of theorem 9, the congruence (1) has as many roots as i t s degree. When IT i s a prime of „ -»-<- JV7 has the congruence „ ~n> [ t t ] roots and hence i f <^, t a complete residue j ° < ^ constitute w system* mod ~TT~, we have the i d e n t i c a l congruence s ( /"- - c / - ^ ' ™ ^ o or, s i n c e JT i s a prime, we may chose as our residue 25. system, mod ~TT , the -n. JV2 °) j XVI* rational [V]-/ ? integers and so Analogue t o Wilson's Theorem i n If 7T be a prime o f /fVVJ and /°> P, be a reduced residue system, mod P , 7T", then We have L e t 5^ be the sum o f a l l p o s s i b l e products of /J, taking j at a time. - / Then ^ S, ^L--'--~+C-O^S-w > Equate c o e f f i c i e n t s o f l i k e powers of £ Now /T = - since /+u » / ^ v w [ V ] - 77~7r 7 . Then i s always odd except when or i t s a s s o c i a t e s , ^ Ctt) =• ">c £-*-"] -/ i s even and therefore When ^?(tr) = = /?«•-*'_, or i t s a s s o c i a t e s , = -2. and we see that the theorem i s a l s o s a t i s f i e d . The theorem may a l s o be proved d i r e c t l y by putting above* ^ = o i n the congruence (1) and proceeding as 26. XVII. Common Roots o f Two Congruences. The common roots o f two congruences Oj ./> <JJ — — and =• o J ^<^^ yr~ ' are the r o o t s o f the congruence where i s t n e greatest common d i v i s o r , mod TT , - O J-,CJ) I and y> fj ) Therefore, i n order t o f i n d the incongruent roots of any congruence with prime modulus, we need only f i n d the r o o t s of the congruence i s "the g r e a t e s t common d i v i s o r , mod ir~ where % o f the given congruence and the congruence This f o l l o w s since the l a t t e r congruence has f o r i t s roots the roots of a complete residue system, mod ~TT\ XVIII. Determination o f M u l t i p l e Roots o f a Congruence with R r i m e Modulus. Theorem 11. I f the congruence has a m u l t i p l e r o o t yc? of order ~g , the congruence has a m u l t i p l e root of order For l e t and suppose f^J) n by -> -£+/ fpc^)] . be a prime polynomial, mod 7T~ i s d i v i s i b l e , mod 77~, b y p p ^ V j but not 27. Then where and 7 ^ ; are polynomials, and T^j) and 'are prime to each other, mod ) where ? gt '(^y ^ ^ ) 7T . f-^j) Also are polynomials i n ^ - Therefore where i s a polynomial. Moreover i s not d i v i s i b l e , mod 1F~ by Tpf^) since ^'(j) i s of degree l e s s than ~P^) and i s prime to " P ^ J » mod TT mod 7T, by j^~p ) ~j • but not by In p a r t i c u l a r , i f order XIX. Theref ore f } <2<^) (j) i s d i v i s i b l e , ffP^j]^. ; has a r o o t , JD , of , then j-kj) has a root, y° , of order t f - / • Congruences i n One Unknown and with Composite Moduli. To f i n d the s o l u t i o n of a congruence of the form where ^ Case I . When^/t. are integers of 7eU) which are prime to each other the s o l u t i o n of (1) may be reduced to the 28. s o l u t i o n of a system of congruences T h i s follows since every root of (1) obviously satisfies each of the congruences (2) while any i n t e g e r of which s a t i s f i e s simultaneously the system of congruences (2) must s a t i s f y ( 1 ) . I f then, p. and i f \\ then £ be the roots o f the congruences (2), be any i n t e g e r of &<) such that i s a r o o t o f the congruence ( 1 ) . The system of congruences (3) i s always solvable by the method of § VI . I f any one of the congruences (2) has no root, then (1) has no root. Case I I . When^^ =- /r- .. 77^ the congruence (1) may re b e s o l v e d i n t o the V A congruences The s o l u t i o n of such a congruence may be made to depend upon the s o l u t i o n of one of the form where the power of the modulus i s one l e s s than i n the original congruence, and so f i n a l l y may be made to depend upon the s o l u t i o n of a congruence of the form where 77^ i s a prime modulus. For l e t ^ be a root of ( 5 ) . Then a l l integers 29. of the form J= + IT. r o o t s of ( 5 ) . ^ where 7 i s an integer of &j) , are Since a l l roots of (4) are roots of (5), any/root o f (4) must be of t h i s form. Then — ^ 77 or and hence since -f(^) == <o> -~^<^~&£ TT~ * ' } = K / ( p and d i v i d i n g 77- each term of (6) by 77~ •' ' we f i n d T h i s i s a necessary and s u f f i c i e n t c o n d i t i o n that must s a t i s f y i n order ^ that a root of (5) may a l s o be a root of ( 4 ) . (a) I f -f '(f) j£ O, then there i s one and but one value of ^ s a t i s f y (7) and so one and but one value which w i l l J" •+- y 7T\ which s a t i s f i e s (4). (b) If f 'CfJ there i s no value of y of ^ is, of the form j c> j -^rt^Tir: j satisfying -+- ~7T^. y v<- ^ /< ^ O-^^TT (7), and hence no value satisfying (4); that (4) has no r o o t . (c) I f f'ff* "™<^"7 j G^ct K=~ o -^^77* then (7) i s an i d e n t i c a l congruence and consequently has ^ £7/7] s o l u t i o n s , mod 7TT , from which we may f i n d ^C'TT] s o l u t i o n s of ( 4 ) . 30. Example: Solve the congruence T h i s may be made to depend upon the s o l u t i o n of ^ which has as a root ^ / } ~^^.^-^ / - ^?-e' - Then the r o o t s of (1) are of the form S u b s t i t u t i n g i n (1) we obtain T h i s gives / as the only r o o t of ( 1 ) , XX. Residue of Powers* If i s prime t o ^ and i f ^ =• <=<: , mody* , where £~ i s a p o s i t i v e r a t i o n a l i n t e g e r , then/^ i s c a l l e d a power residue of «?< with respect to the modulus^*'. A system of i n t e g e r s of power residue of such that every * mod^^ , i s congruent t o one and only one i n t e g e r of the system, modyfc * i s c a l l e d a complete system of power residues of <\ with respect to the modulus >-y£ • Consider the congruence ^ =• /, —x^-^^c CO I t i s evident from Fermat*s theorem that /"always e x i s t s and that ^ PC**-) * a p p e r t a i n to the exponent T n e i n t e g e r ^ i s said to when • i s the smallest value of jf~, other than zero, f o r which the congruence (1) i s true. 31* If the same exponent, m o d ^ Theorem 12. then <=< and ^3 a p p e r t a i n to » mod^, . I f the integer < = > < appertains to the exponent , mod^ ^°= , then the --^ o*', ^ ; powers o f ^ ^ c ^ - ^ _ , co / are incongruent each to each, modM * L e t o<r and °< be any two of the s e r i e s (1) and assume that Then since ©< i s prime t o i. e. CK. appertains to the power ^ } the hypothesis that o< a p p e r t a i n s Theorem 13. If ^ -^-^ contrary to to the exponent appertains to the exponent any two powers of c< , , with p o s i t i v e exponents are mod^^ congruent or incongruent to each other, mod A' » according as t h e i r > exponents are congruent or incongruent, mod Let o< ' * by any two powers o f o< where 5" 5^ are p o s i t i v e i n t e g e r s , and l e t (J S, = ^ and ^ osr**^ G.+r; •, , <'> being p o s i t i v e integers and > o * a ^ ^ Assume that Then and since ^< i s prime to , -r^ri & 32* But, since O ^ K-1 to the exponent < , then •n - ri Therefore, by ( 2 ) , and o< appertains = o from (1) i s a necessary c o n d i t i o n f o r (3) to be t r u e . Moreover, i f (8) i s given, then from (1) r, = n- > — — ^ and hence since r and y? are both l e s s than £ we must have Then and since we have Therefore (6) i s a l s o a s u f f i c i e n t c o n d i t i o n that (3) be t r u e . Moreover The r e l a t i o n (7) expresses the law of the p e r i o d i c i t y of power residues. 33. Theorem 14. appertains, The exponent t o which an integer <=< mod^r, i s a d i v i s o r of £7^) For"* and, therefore, by theorem 13, i.e. jZtffa-) Theorem 15. i s d i v i s i b l e by - I f two i n t e g e r s , ^ , and © < modyt , to two exponents tit^ , are prime to each other, , appertain, , r e s p e c t i v e l y , that then t h e i r product, <=< appertain apper- t t a i n s , m o d ^ , to the exponent Let a • to the exponent mody^r Then J- 0) and so But so that But appertains by theorem 13, since ^ by and . so that ^ value of to the exponent , mody^d , and hence, i s d i v i s i b l e by and, therefore* are prime to each other, ^ i s d i v i s i b l e S i m i l a r l y we may show that J ~ i s d i v i s i b l e by i s d i v i s i b l e by ^ . such that (1) i s true i s Hence the smallest = -"v * 34. Theorem 16. To every p o s i t i v e r a t i o n a l d i v i s o r there a p p e r t a i n tVCs) i n t e g e r s of the "modulus Z or (p(w~) with respect to 7T~ being a prime o f /f(<% r i Let denote the number o f i n t e g e r s of which a p p e r t a i n to the exponent -^t» Assume that to every p o s i t i v e Then divisor, appertains a t l e a s t one integer o< . ~X.(f) ^ O of qp6r) there Then each of the integers •> ° * J O < , - - > ^ which, by theorem 12, are incongruent to each other, mod 7T t i s a root o f the congruence For J ^ /j i f cxtf be one o f them, since ^ / ^ (A) then — - These are, moreover, a l l the incongruent roots of (2) since (2) cannot have more roots than i t s degree, being prime to ~7T~. Now l e t o< be one of the integers (1) and suppose that <xT * appertains to the exponent Then i f K contains a f a c t o r , and since exponent st~» < o<f mod 7T~. say, of -A, we have does not appertain to the Moreover, i f A i s prime to ^"then oi K appertains to the exponent--^, f o r suppose o< * appertains 35. to the exponent -f- . since ^ appertains Then t o the exponent *S~ mod 77~. t Therefore since K i s prime %OJ£~~, and hence the smallest value of -f to s a t i s f y (3) i s = We have proved, therefore, that the necessary and s u f f i c i e n t c o n d i t i o n s that any one o f the integers (1) s h a l l appertain to the exponent exponent be prime to mod 77~ i s that i t s t T h i s i s s a t i s f i e d by g?ft)of them. Hence Since every one of the ^PCv) integers o f a reduced residue system, mod 77~„ appertains and every such exponent i s a d i v i s o r o f the follows where But whence t o some exponent ^PCTT) that are the p o s i t i v e d i v i s o r s of fl)(7r) ,i t 36. I f , then, any be true. XXI. ~X.(£- .) — a Hence no X ~)C (jt\) — O , (4) would not and therefore = pes.) ) P r i m i t i v e Roots. Any i n t e g e r that appertains to the exponent f?(/<-) with respect to the modulus^; , i s s a i d to be a p r i m i t i v e ofyc • root I f TT i s a prime of ~$(<j , then by theorem 16, has (p ~j [_ (pM incongruent p r i m i t i v e r o o t s . Let y be a p r i m i t i v e root of ~7J~~. Then by theorem 12 the i n t e g e r s f,/ ) -- — 0 v /* form a reduced residue system, mod 7t~ • Conversely, i f a reduced residue system, mod root. For l e t jo ^ y 7 4 , /°''^constitute 77~ , theny° i s a p r i m i t i v e be any two of them and l e t « > b > ° < i . e. where A- 6 may have values from / to (^CTTJ - / In p a r t i c u l a r H e n c e i s a p r i m i t i v e r o o t of ~77~. We may therefore define a p r i m i t i v e root of '// as an 37. i n t e g e r of fa) r e s i d u e s , mod such that a complete system or i t s power 7T , c o n s t i t u t e a reduced residue system, mod* 77". We s h a l l now give a second proof of Wilson's theorem depending upon t h i s d e f i n i t i o n . prime o f such that ^ QTTJ p r i m i t i v e root of i r and f, residue system, mod yr . are the i n t e g e r s Then since y^/ * — 0 /, .2, j 7T~ /° T <pt>r) order. M u l t i p l y i n g these congruences together we have Ht* .'- T T But since we must have ^ s f> ^ , be a a reduced rJ c o n s t i t u t e a reduced residue system, mod and e i s odd, and l e t j° > f^ } Ffe a Let . ~™~^7r- a l s o we have i n some 38. Therefore •^IFTT} i s always odd except when JJTT] = 3. ' i t s a s s o c i a t e s , i n which case ~7T~= or } , The p r o o f as given here does not apply f o r t h i s case although the theorem i s true since then y?f*-J =• / , and we take / as our reduced residue system, mod /-*••£. . XXII. Indices. Let — f° P be a p r i m i t i v e root o f 7T~ . Then f, f, - - - c o n s t i t u t e a reduced residue system, mod // , so that any number °< which i s prime to 7T~must be congruent to some power of j° , mod TT . If then i s s a i d to be the index of < = > < to the base y ° , mod 7T~ T and we write ^ =• ^^^^^ <xc j ~—?^x>*-<af TT- . I t may be shown that indioes obey the following Iaws analogous : to those of logarithms. 1» The index o f the product o f two integers i s congruent to the sum of the i n d i c e s of the f a c t o r s , mod yP CTT) or i n general 59. Then 7F~ • and therefore i. e. As a p a r t i c u l a r case we have Also <=< In every system ^^af / = °. Now the index of any number depends upon the value of the p a r t i c u l a r p r i m i t i v e root chosen as base. I f , however, the index i s known f o r a p a r t i c u l a r base we may f i n d i t s value f o r any other base. For l e t jcf and be two p r i m i t i v e roots of 77"", and let A - > <—^^> so that Let c< be an i n t e g e r o f Then and hence such that 40. In p a r t i c u l a r , p u t t i n g o< =• jo , we have i . 6T. . Theorem 17. If /? = / , <=<: , mod 77", be g r e a t e s t common d i v i s o r of -c' and appertains to the exponent ^/Vy 1 , and i s the , then <=< ^Vj"/^ We a r e given that Let — «-<' ~ j£> ^ ^-^^<»-0e- 77—~ be the exponent t o which <=* appertains, mod 7i~ . We wish to f i n d the l e a s t value of J- such that Now > and hence Then where Then i s the greatest common d i v i s o r o f -c' and ^ 7 - i s prime to and so the smallest . value of j- , other than zero, such that ( 2 ) be s a t i s f i e d i s Then, by (1), ex. appertains The to the exponent » mod 7 7 - . converse of t h i s theorem i s a l s o true; 1. e., whatever p r i m i t i v e root, f> t 0 f 77~, i s taken, i f c=f 41. , mod 7 7 ~ , then d i s appertains to the exponent the ^greatest common d i v i s o r Cor: If of -^»* i s a p r i m i t i v e root of p r i m i t i v e roots of «=<? 37~~ s a n gP^Tr) d \jP *)\ then the <f (l those incongruent powers of y ° 7T~are whose exponents are prime t o y?(7r) XXIII» S o l u t i o n of Congruences by Means o f Indices* I f we have a t a b l e of i n d i c e s to any base f o r a given modulus 7T we may solve any congruences of the types or (a) ^j j (b) •== —~sr- y€ J where i n each case ^< i s not d i v i s i b l e by ~7T~ * In case ( a ) , taking i n d i c e s , we have whence and knowing and ~^i_cf ^ , and ^*~cf <^ we may f i n d ~<^-cf ^ so f i n d zy. In case (b) we have a congruence of the f i r s t degree i n one unknown. The necessary and s u f f i c i e n t c o n d i t i o n that t h i s be s o l v a b l e i s that common d i v i s o r be d i v i s i b l e by <af , the greatest of and i s s a t i s f i e d there are ^^r) * When t h i s c o n d i t i o n [ei] values of C. ^ ] corresponding t o which we f i n d values o f y which are incongruent mod 7 T and which s a t i s f y the congruence ( b ) . XXIV. Binomial Congruences. We give here another method of treatment f o r the subject o f power residues and p r i m i t i v e r o o t s from a c o n s i d e r a t i o n of the binomial congruence O — 3 - *- 0) We have seen that a l l roots of ( 1 ) w i l l be r o o t s of the congruence where / ^^J^ greatest common d i v i s o r , mod ~7T~ , of is and ^ — / . I t i s e a s i l y seen that / where ^ i s the g r e a t e s t common d i v i s o r of For a l l common d i v i s o r s of £ the form £ -/ and and Moreover, it of i s a d i v i s o r of ~H. then ^ . Hence i f ^ common d i v i s o r ot ^/ andfl'*^ y g r e a t e s t common d i v i s o r o f >c and The congruence (1) has, therefore, . — / must be of where ^ i s a d i v i s o r of both d i v i s o r of ^>~*L/ <P&r) / and (pCw) isa i s the greatest ^ then <s*f i s the i^/Tr) , incongruent roots and these are the roots of the congruence J / == O j -~r^*-^-7r- . ^ Those roots of (2) which s a t i s f y no binomial congruence of degree l e s s than (2) are c a l l e d primitive 43. r o o t s of (2) while those roots of (2) which s a t i s f y b i nomial congruences of lower degree are c a l l e d imprimitive roots. The p r i m i t i v e roots of (2) are, then, those i n t e g e r s which appertain to the exponent &t , mod ~t>~. They are (pfd) i n number. In p a r t i c u l a r , the p r i m i t i v e r o o t s of 77" are the p r i m i t i v e roots of the congruence If y° i s a p r i m i t i v e root of (2) then the °^ /> P, roots of (2) a r e , by theorem 12, If o( j f *~j J f are roots of the congruences l and <=^ ©e r e s p e c t i v e l y , then g << < / ^ 0 In p a r t i c u l a r , i f °< and and ^ ^ ^ £ T T - & <v are p r i m i t i v e roots of (3) A (4) r e s p e c t i v e l y , and i f c/ each other, then XXV* i s a root of the congruence t and c? / x are prime t o °C, °<f i s a p r i m i t i v e r o o t of ( 5 ) . x Determination of a P r i m i t i v e Root of a Given Prime Number. The method, due to Gauss, i n which we f i n d a succession o f integers appertaining to higher and higher exponents, w i l l apply e q u a l l y w e l l i n the f i e l d We must* i n such a process, to the exponent gPCv-J fa) - f i n d an integer which appertains , mod 7T~ and hence i s a p r i m i t i v e t 44. r o o t of ~7T~ . we may prove, however, that i f a. ->t. QTT] p r i m i t i v e root o f -fZ a p r i m i t i v e root of 7T i n If # is a then ct i s a l s o } . i s a p r i m i t i v e root of C"n\l i n then <Z i s a l s o a p r i m i t i v e root of 7T i n Let "H. £TT] •= , a r a t i o n a l prime. 7^? Then since «. i s a p r i m i t i v e root o f ~p> , ^ i • e, = 7 -/ / J s A Therefore, (3. === CI == /j We must s t i l l show that mod 77" , to an exponent l e s s than appertains to the exponent f , mod - ^ ^ 7 T . CL does not appertain, £^W"J . Suppose <3. 77~ , where -f- ^ ^^ ) ir Then and so, since <z - / i n which case <2 i . e. i s a r a t i o n a l integer, appertains to an exponent -=^.p^t. On-] ) i n ^ p r i m i t i v e root of ->t CTT] } , mod •?< C-7r] and so i s not a which gives a c o n t r a d i c t i o n . Therefore <2 i s a p r i m i t i v e root of ~7T i n ^r). In order to f i n d a p r i m i t i v e root of t h e r e f o r e , we need only f i n d a p r i m i t i v e root of in . -=r <pcr) r , -** £V] This w i l l a l s o be a p r i m i t i v e root o f 7T i n . 45. The remaining p r i m i t i v e roots o f 7 ^ may be found by applying the cor. of theorem 17. For example, to f i n d the p r i m i t i v e roots of -a-^ \Z4^<>'c~\ — f i r s t f i n d a p r i m i t i v e root of t h i s form the power residues of J2. , mod „ To do ^ / These are - V , -<T, - / ^ Then 5 appertains - -2^ to the exponent Wow form the power residues of so 3 appertains ^-,^/ 3 to the exponent , mod » mod f >/•/ * *-f-l . , mod We have "// . - Take ^ = • r • * The g r e a t e s t common m u l t i p l e o f Divide ^ i n t o two f a c t o r s ^- . 7 A and Then = s>- i s ~~^c-=.^/0 • prime to each other i s a d i v i s o r of y and such that of 5w , and -^~ and *?*c _ a d i v i s o r x = ? Now Then ^2. and 3 appertain to the exponents r e s p e c t i v e l y and so t h e i r product^ <?- ^ X 3 . ^ to the exponent =~ i s a p r i m i t i v e root of x F — . ~ and appertains Therefore ~z x 3 46. Now Therefore / i s a p r i m i t i v e root of p r i m i t i v e root of ~77~ - ^/*- s>~^' ^C^) = <p(4o) /£ c# [_Cp(w)~\ Then the I t i s also a = p r i m i t i v e roots of 7T~ may be found by applying the cor. of theorem 17. i s since / That i s a p r i m i t i v e root of *yV.5V, then the Cp £(P(+/+sZprimitive roots of are those ty^jT (p(4+**) J incongruent powers o f J whose exponents are prime to • /, 7, ^C^-f-i"^) 7 , • 7 x , ~ These are 7 7 , a 7 f , / 7 , 7 , 7 ; " which may be reduced t o i n t e g e r s of XXVI. The Congruence We may reduce any congruence where i s not d i v i s i b l e by Consider the case i n which i r ~ , t o one of the form /3 o, mod TT~ . From previous d i s c u s s i o n we have the theorem, Theorem 18. The necessary and s u f f i c i e n t conditions that the congruence s h a l l be s o l v a b l e , i s that s h a l l be d i v i s i b l e ~*^-<zf^ by the g r e a t e s t common d i v i s o r , a t of } and yPtir) ; 47. this c o n d i t i o n being s a t i s f i e d the congruence has e x a c t l y %C<^] incongruent r o o t s . Theorem 19. Euler's Criterion f o r the f i e l d I f o * be the p o s i t i v e greatest common d i v i s o r 1 **<- and y?(Tr) » the necessary and s u f f i c i e n t of c o n d i t i o n that the congruence s h a l l be s o l v a b l e i s T h i s c o n d i t i o n being s a t i s f i e d , the congruence has ^ D ^ ] incongruent r o o t s . exactly Let y° be a p r i m i t i v e root of 7T\ {3 = I f (2) i s s o l v a b l e then Let ^ = ^ • and l e t i s d i v i s i b l e by Then and Therefore (3) i s a necessary c o n d i t i o n f o r the s o l v a b i l i t y of ( 2 ) i Conversely, i f /g s a t i s f i e s condition (3), then since t h e n and hence ^ 48. and s i n c e so "that i s a primitive root, ^- i s an i n t e g e r . Therefore -e i s d i v i s i b l e by <sf and (2) i s s o l v a b l e . Hence (3) i s a l s o a s u f f i c i e n t c o n d i t i o n f o r the s o l v a b i l i t y of ( 2 ) . A l l incongruent i n t e g e r s /3 , f o r which the congruence (2) i s s o l v a b l e may be obtained by observing t h a t they are r o o t s of the congruence The congruence (4) has the incongruent ( *^ r) incongruent r o o t s which a r e values of /3 f o r which (2) i s s o l v a b l e . Such members congruent t o the ?t t h power o f an i n t e g e r , mod If, are called ~?£-^c r e s i d u e s of 77~~ and we have % the f o l l o w i n g : Theorem 20. mod 77" t i s --^a The number of incongruent ^-~f~ < J where common d i v i s o r of % <s*f residues, i s the p o s i t i v e g r e a t e s t and ^ % i a n d these r e s i d u e s a r e r o o t s o f the congruence //
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Congruences, primitive roots, indices for the field...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Congruences, primitive roots, indices for the field k(i), Simons, William Haddock 1937
pdf
Page Metadata
Item Metadata
Title | Congruences, primitive roots, indices for the field k(i), |
Creator |
Simons, William Haddock |
Publisher | University of British Columbia |
Date Issued | 1937 |
Description | [No abstract available] |
Subject |
Congruences and residues |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-11-01 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0080577 |
URI | http://hdl.handle.net/2429/38590 |
Degree |
Master of Arts - MA |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1937_A8_S5_C6.pdf [ 7.2MB ]
- Metadata
- JSON: 831-1.0080577.json
- JSON-LD: 831-1.0080577-ld.json
- RDF/XML (Pretty): 831-1.0080577-rdf.xml
- RDF/JSON: 831-1.0080577-rdf.json
- Turtle: 831-1.0080577-turtle.txt
- N-Triples: 831-1.0080577-rdf-ntriples.txt
- Original Record: 831-1.0080577-source.json
- Full Text
- 831-1.0080577-fulltext.txt
- Citation
- 831-1.0080577.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080577/manifest