UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Congruences, primitive roots, indices for the field k(i), Simons, William Haddock 1937

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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 //  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items