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 by-William Haddock Simons A Thesis submitted for the Degree of M A S T E R O F A R T S in the Department of M A T H E M A T I C S THE UNIVERSITY OF BRITISH COLUMBIA A p r i l , 1937 TABLE OF CONTENTS Section T i t l e Page I. Congruences of condition. 1 I I . Equivalent congruences. 3 III . System of congruences. 3 IV. Congruences i n one unknown. 5 V. Congruence of f i r s t degree i n one unknown. 5 VI* Integer having certain residues. 7 VII. D i v i s i b i l i t y of one polynomial by another with respect to a prime modulus, common divisors, common multiples* 10 VIII. Unit, associated, and primary polynomials. 11 IX* Prime polynomials. 12 X. D i v i s i b i l i t y of polynomials. 14 XI. Congruence of two polynomials with respect to a double modulus* 15 XII. Unique factorization theorem* 16 XIII* Resolution of a polynomial into i t s prime factors. 21 XIV i General congruence of >t th degree i n one unknown* 22 XV. The congruence ^,^^1 / Oj ^*^^oc 2 4 XVI* Analogue to Wilson's theorem i n 25 XVII. Common roots of two congruences. 26 XVIII. Multiple roots of a congruence. 26 XIX. Congruences i n one unknown with composite moduli. 27 XX. Residue of powers. 30 XXI. Primitive roots. 36 XXII. Indices. 38 XXIII. Solution of congruences by means of indices. 41 XXIV. Binomial congruences. 42 XXV. Primitive roots of a given prime. 43 XXVI. The congruence ^ tt~. 46 INTR ODUG Tl ON In his text, "The Theory of Numbers and Algebraic Numbers", L. H. Reid states, without proof, that certain relations may be proved true i n the f i e l d /^ V*0 as i n the f i e l d of r a t i o n a l numbers. It i s the purpose of t h i s thesis to investigate t h i s statement and to supply proofs wherever they may d i f f e r from those for the f i e l d Before doing this* however, i t w i l l be necessary to col l e c t together certain definitions and results necessary in l a t e r developments. 1. Numbers of &u) ; Any number of i s a ra t i o n a l f r a c t i o n a l function of with r a t i o n a l co-e f f i c i e n t s . An integer of ~&u) is a number of £u) of the form c< = a + U where CL and b are rational integers. When b =o we obtain the r a t i o n a l integers which are a sub f i e l d of . The number <3- b~c found by putting -4 for ~c i n any number c< i s called the conjugate of c< and i s denoted by <=*c ' . The norm of any number is the product of °<i and i t s conjugate »< \ and i s a positive r a t i o n a l number; The norm of the product of numbers of £w)ls equal to the product of the norms of i t s factors. Thus -y^ [_c*(9 r-- ---] - ^ H ~ ^ [ Y ] . ± . L. H. Reid, l o c . c i t . , Chapter 5, S 15, p. 190. I I . 2. D i v i s i b i l i t y : An integer <*< of Hu) i s said to be d i v i s i b l e by an integer ^3. i f there exists an integer f such that <>< - f An integer of which is a divisor of every integer of the f i e l d i s called a unit of Evidently — * are units of iu). If there be any other units then they must divide / and, conversely, any divisor of / i s a unit. We therefore find that i n there are four units, ± I j ±" • Factorization i s unique for integers of 4 (*•). 3* Congruences i n $(*) : Two integers .<=xfi ^3} of $(*) are said to be congruent with respect to the m o d u l u s i f their difference is d i v i s i b l e b y . We then write or - (3 =• K/-^ -The fundamental laws of addition, subtraction, multiplication, and division of congruences apply in the f i e l d gu) as i n the rational f i e l d . I f the integers of are divided into classes, putting two integers i n the same or different classes according as they are congruent or incongruent, mod ^pc , i t may be proved that there are ~k S.jx'] such classes. The system of integers formed by taking one from each class i s called a complete residue system, mod^# , i . e., the set i s such that no two are congruent, mod^/4 . I I I . Therefore the *x, [ ,/] integers I s\ / . *-»•«• -/ form a complete residue system, mod ^ jlc , where^/* - "»»<- ^f + ' As special cases we have (a) When^x= -jz>-tx^ t jo and ^  being r a t i o n a l and prime to each other, the integers l} — ">/?a"+ form a complete residue system^ mod^u. • (b) When » >*e. , a rati o n a l integer, the integers of 7? (•*•) , |*>~ I - / ( lj *j •> '"^l ' form a complete residue system, mod^/jl * 4. The ^ - f u n c t i o n ; As i n 1? , CpCyt.)^ where i s an integer of , i s defined as the number of integers i n a reduced residue system, raodyU. . i n l a t e r work we w i l l make use of the theorem that i f S, }be the different divisors ofyOt , then We need also Fermat's Theorem, that i f ^ . be any integer of £(<) and c< any integer prime to /a. , then Notation. In the work which follows the unknown i n the f i e l d w i l l be represented by the complex variable, f--Integers of the f i e l d w i l l be denoted by l e t t e r s of the Greek alphabet. In pa r t i c u l a r , the Greek letter7f~ } w i l l be used to denote a prime of I. Congruences of Condition. In the study of congruences we deal only with relations between definite integers of -c), a congruence stating that the difference of two integers i s d i v i s i b l e by a third integer. In congruences of condition certain of the quantities are unknown and the congruence i s true only for par t i c u l a r values of these unknowns. In the f i e l d we define a polynomial i n the undetermined coefficients ^,, ^ ; - — ) Jk^  as a r a t i o n a l integral function of ^ whose coefficients are ra t i o n a l numbers. In the work which follows, however, the coefficients are integers of the f i e l d £u) unless a statement i s made to the contrary. A polynomial, J- (fr>?L> > ) i s said to be i d e n t i c a l l y congruent to zero, modyU , i f a l l i t s coefficients are congruent to zero, mod . where the i s the coefficient of i n j-^i>"'J J^)' Two polynomials , / ^ ) , CpC},, > >^ ) are i d e n t i c a l l y congruent to each other, m o d , i f their difference is i d e n t i c a l l y congruent to zero mod^u. . 1- = : i s the symbol for " i d e n t i c a l l y congruent to" while ^ is the symbol for "congruent to" and i s used when the congruence expresses a r e l a t i o n between definite integers. This implies that the coefficients of i n ; and tjPty)—; f^) must be congruent, mod^t • I f * <r°(A> y / O , moa^*, and °*i> . be any X. integers of fay then / K , ^ ^ ^ ^ . - - ^ i m o d (0 That fc*. s h a l l have a set of values such that (1) holds i s expressed by and i s called a congruence of condition, and amy set of integers ; ; ^ such that (1). i s true i s called a solution of ( 2 ) . If c*'i ^ } o<r^  . ^  be two sets of solutions such that c^. £ET j-^x^(yU (* s * ™ - ) . then evidently and f t * ' — ' Z * - * ' - ™ ^ and hence i f ; - — ,<=<^  i s a solution of (2) then ''/^- i S a' 1' s o a s o l u ' t i o n » These, however, are looked upon as i d e n t i c a l . In order that two solutions may be considered as d i s t i n c t i t i s necessary that at least one value of one unknown s h a l l be incongruent to the corresponding value of the unknowns i n the second solution. Hence i n order to find the solutions of any congruence of condition i t i s suffi c i e n t to substitute for the unknowns the n^y/} values of a complete residue system, modyu . I I , Equivalent Congruences, Two congruences •and <p, '>---/ > <V 0-> are said to be equivalent i f every solution of the f i r s t i s a solution of the second, and i f every solution of the second is a solution of the f i r s t . Thus, we may add to (1), term by term, the terms of any iden t i c a l congruence, thus obtaining a congruence equivalent to (1), By means of this we may transpose a l l terms from one side of a congruence to the other side obtaining an equivalent congruence of the form We may also reduce the coefficients of the terms of the polynomial to their smallest absolute values, mod yu. . Also, we may multiply or divide both members of a congruence by an integer prime to the modulus and obtain an equivalent congruence, III, System of Congruences, Equivalent Systems. Instead of a single congruence, we may have a system of congruences i n j and require that these be s a t i s f i e d simultaneously for values of . By a solution 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. Two solutions } a n d ^ y — a r e considered different when and only when the congruences . < =7% V / = are not a l l true simultaneously. Two systems of congruences are said to be equivalent when each solution of the f i r s t system is a solution of the second and each solution of the second i s a solution of the f i r s t . Example: Solve the system of congruences; Multiply the 3rd congruence by Btj-i, then by / and subtract from the 1st and 2nd respectively* Then Multiply the 2nd congruence by ;^-o~<; and add to the 1st. Then The 1st congruence of (c) has one and but one solution y = /f^ •=== - j . Then from the 2nd congruence of (b) and from the 3rd congruence of (a) we find = J?tr<. = _ ^-f--s^' The solution of (a) then i s 5. -X = - /CP \ IV, Congruences i n One Unknown, The general congruence i s one unknown i s /ty + S 2 * * ~ °, ^ < C'> where ^ ; , < 0^ are integers of ^ ? c ^ • If ^3 be any integer of ^V<rJ such that then is called a solution of (1), The degree of (1) i s the degree of the term of highest degree whose coefficient is^?o , modyO. . In order to fi n d a solution for such a congruence i t is only necessary to substitute for the unknown i n the equation the numbers of a complete residue system, mody*. , and f i n d which ones s a t i s f y the condition of the congruence, Vj, Congruences of 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 written i n the form where «^ ^ a r e integers of /£*v) . Theorem 1, The congruence, ^, ^=^j CO where cxf i s prime to m has one, and only one solution. Substitute for ^  i n (1) the >i[/c] values of a complete residue system, mody*. . Then, by ^ 3 of the Intro-6* auction we obtain ~>t[^] values which constitute a complete residue system, modyt , and hence one and only one of these values can be congruent %o^3 , modyU. * ' Fermat's theorem gives a means of obtaining the root of such a congruence, for since then A ~< &*>s/3, Thus ~ / i s a root of the congruence where i s prime toy u . * Theorem 2. The necessary and su f f i c i e n t condition for 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 greatest common divisor, & of <=>< a n d , and when thi s condition i s f u l f i l l e d the congruence has exactly t C i l r o o t s . We s h a l l give a proof similar to that for the ration a l f i e l d . Let c ^ r ^ S a n d y . =•y/t S so that and^^ are prime to each other* Then. i . e., =^f3-*-KyU, <f Therefore we must have ^ ? d i v i s i b l e by i " * Put ^ - <T Then ^ ^ ->^^yc, . ^ Since i s prime to/* (2) has a root* Moreover, a l l values of ^  satisfying (2) w i l l also s a t i s f y (1) since 7. we may pass from (2) to (1) by multiplication by S , Therefore that ^ 9 be d i v i s i b l e by S i s a 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 (1), Moreover a l l •roots of (1) s a t i s f y (2) and are therefore of the form f *• where y° i s a root of (2). Thus i n order that we may have two incongruent roots of (1) we must have i . e. '<,y*, ^ , ^ ^ t y " . Thus i f we substitute for the integers of a reduced residue system, mod 6 , which are ~K i n number, we obtain a l l the incongruent roots of (1), modyc • VI • Determination of An Integer That Has Certain Residues  With Respect ^0L.a Given. Series of Moduli. Consider f i r s t the case where the required integer must s a t i s f y simultaneously the two conditions A l l integers satisfying (1) are of the form where <y is an integer of 4(*)* I 1 1 order that this 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 solvable i t i s necessary and su f f i c i e n t that £ divide <=<^  — ^  where <T is the greatest common divisor of^//f a n d y ^ . 'If this requirement be s a t i s f i e d and £ be a root of (3) then every root y of (3) must satisfy^ where i s an integer of ~&t*) Then a l l integers sat i s f y i n g both (1) and (2) are of the form And hence ? = f , <~^ *~*< If ^  be any integer sat i s f y i n g both (1) and (2), a l l and only those integers s a t i s f y both (1) and (2) which are congruent to ^ o with respect to the least common multiple of the moduli of (1) and (2). The general case of ~?t congruences may be solved, i f a solution exists, by a repeated a p p l i -cation of the above. Hence the common solutions, J> , of (5) are given by where ^ i s an integer satisfying a l l the congruences and X i s the least common multiple of the .moduli^,,---- -jyjt^ 9. Alternate proof for case when the m o d u l i ^ are prime to each other. In this case /\ -y-.yK*. Z^-^ * • F o r e a c h 'modulus yr. select a /3- such that This is always possible since the second congruence implies ^ . - - K and we need only determine A" such that which has a solution s i n c e ^ ^ - - i s prime t o ^ f . . NOW put yO = Z1T ^/C: <^ Then ^ ^ gives the common solutions of the system. From (6) we also have and hence since a l l o f ^ ^ , ^ are d i v i s i b l e b y / ^ except we have How _ j£ - /„ and so •? Therefore a l l integers satisfying (6) satisfy each of the congruences ( 5 ) , Now l e t ^ a be an integer satisfying each of the congruences (5). Then = cx'. and / — ^< ; f-*'-/, Hence ^ - / ° — ° J *-*pc*~^yu~£ f - * " - -> 10. i . e. fa ~j° i s d l T 1 s i b l e by each of the m o d u l i y X y - ^ ^ . and hence by their product A . Hence ^ e = j0, <->~^-*^ A • Thus we have a method of obtaining the common solution of a system of congruences i n this special case. I f for =<, . — . in p we substitute the integers of a complete residue system with respect to the moduli/*,,y£Xj - jyiS*. resoectively, the resulting values of jo form a complete residue system, mod A •••Or.'if for c*^  - , in yd we substitute the integers of reduced residue systems mod^a^,^^ jy*s.~ respectively, the resulting values of j° form a reduced residue system, mod A-The proofs for these two properties are simi l a r to those for the corresponding theorems of Hence the number of integers i n a reduced residue system, mod^^y^ —y&*^. -> where^a^ )y#-~. a r e prime to each other, i s equal to the product of the numbers of the integers i n reduced residue systems for 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 Polynomial by Another With Re-spect to a Prime Modulus. Common Divisors. Common Multiples. Let 7T- be a prime of . Then a polynomial fa) is said to be d i v i s i b l e by a polynomial^*? J with respect to the modulus 7T~, i f there exists a polynomial j?£ ) such that 11. As a direct consequence of this d e f i n i t i o n we have i . If be a multiple, mod TT, of fi<j) and be a multiple, mod r " , o t , then f-,^}) i s a multiple, mod TTy of f3(j) > or i n general i f each polynomial p^c§) ? {*'=/, .?,-— ) J be a multiple of j J , mod Wt then each poly-nomial i s a multiple, mod 7T, of a l l that follow i t . i i . If f.Cj) and y £ b e multiples, mod/7-, of then /<j) and ^ _ yf ^ ; are multiples, mod TT, of , or i n general i f f,^) and £.<j) he multiples, mod 7T , of fy) and > ^ ; be any two polynomials, then /^j) f, (j) t~ f+t'j) J± ) i s a multiple of , mod 7T~. VIII. Unit and Associated Polynomials with Respect to a  Prime Modulus, Primary Polynomials. We wish to find whether there exist polynomials that divide a l l polynomials with respeet to the modulus 7T No polynomial of degree greater than zero can be such for since they must divide unity, mod 77~l the sum of the degrees of the divisor and quotient would be greater than zero, the degree of unity* Moreover i t i s evident that they must not be d i v i s i b l e by 7T~. Hence, a l l and only those integers of which are not d i v i s i b l e by 77~ have this property and are called unit polynomials, mod "7 * Two polynomials which d i f f e r only by a unit factor, mod 77", are called associated 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 associatedj mod 7T , with a third polynomial, they are associated with each other; for i f and / i ^j) ^ where are units, mod 7^-, and i f ^ ^ 7 is an integer such that /^/^ ^7" and then f:<;>m^fo>, where <=</<^  i s a unit, mod TT-. Two polynomials, that are associated, mod 7T~^ are of the same degree, and each i s a divisor, mod Wt of the other. Conversely, i f two polynomials be each d i v i s i b l e , mod 7Ty by the other, they are associated. Two polynomials having no common divisor, mod t other than the units are said to be prime to each other, mod If . Of the.-7*CV7 —/ associates of , that one having unity as the coefficient of i t s term of highest degree i s called the "primary associate," mod 77~ * EC. Prime Polynomials with Respect to Prime Modulus. Determination of the Prime Polynomials, mod y", of any  Given Degree. A polynomial that is not a unit, mod 7T~, and that has no d i v i s o r s , mod 7T, other than i t s associates and the units, is called a prime polynomial, mod 7f . If 13. i t has divisors, mod ~rr , other than these i t i s said to be composite, mod 7T~* For example l e t us find the primary prime poly-nomials, mod J** , of any degree. We may take as a complete residue system, mod l+< , the integers o3 /3 2} 3, V of £c<) . Then the primary prime polynomials of the f i r s t degree, mod J+t , are + ' > ^ ~* 3 •> ^  * ^  ' The reduced primary polynomials of the second degree, mod -2 + -c , are 25 i n number. r + i - ^ v ' / v ^ -j*-*/"- J>*j+* f+^J** f+3 r*?*-3 y'V*-3 y<-4} +3 From the primary prime polynomials of the f i r s t degree we can form the composite polynomials, mod . These are ^ ^ ^ " / ^ 7 a l l congruences being taken with respect to the modulus 3+X J _ -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 general, when ~*i>l the number of primary prime polynomials, mod 77~ , of the TC^ degree i s where ^ ^ ^ - — , are the different prime factors of ~TO>. X. Division of One Polynomial by Another With Respect  to a Prime Modulus. Theorem 5. I f be any polynomial and <^?<j) be any -polynomial not i d e n t i c a l l y congruent to zero, mod TT~, there exists a polynomial £Kj} t such that the polynomial i s of lower degree than • The operation of finding SKj.) and i s called d i v i s i o n , mod IT , of by <ft<j) . i s called the quotient and y f ^ ^ the remainder i n the division, mod -JT , of fy) by ty 7^) • We prove the existence of and by giving a method for their determination; Let y r j f ; — *">^ j> T - -i- ~<_^ be any two polynomials and l e t Consider f i r s t the case i n which ^ — / • Divide J-c£> by as i n the ordinary d i v i s i o n process u n t i l we get a remainder of lower degree than ^P^j) and having the quotient <^^) • Then } /(j) = gCj) <p%) ->- ) from which (1) follows. Consider the case where ^ / and ^= O , mod ~7T~. Let ?^ be the reciprocal, mod 7T~ , of ^ a Then jr /V S j — where flfg) is a polynomial i n ^  having unity as the coeffi c i e n t of the term of highest degree, Divide by ^ j ^ J as before. Then f<i>*£<<j)&<j)+tf,'j), — and hence = ?T ^) p>Cj)+ - ^ ^ ^ where 9^3, (j) and a r e t h e quotient and remainder required. XI. Congruence of Two Polynomials With Respect to a  Double 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 to each other with respect to the double modulus 7T, » where T is a prime of and ft/j) a polynomial, i f their difference, fj)'- f*cj) i s d i v i s i b l e by » m O Q • where <=2(j) and are polynomials. If J - ) i s d i v i s i b l e , mod ^T" by this may be 16. expressed by ffy) = O , -^^^ 77*^ <ft<j) XII. Unique Factorization Theorem for Polynomials With  Respect to a Prime Modulus. In order to prove the unique factorization theorem we need the following theorems. Theorem 4* I f ^f%)=. ^) <fl£) + 6?^) i*^t^~^-7T~ 3 every polynomial that divides, mod ~7T , both -f/j) and ^ ^j) divides both and , and vice versa; that i s , the common divisors, mod TT , of and <^?£) are identi c a l with the common diviso r s , mod 7T~, of and /*^ >> • This i s an immediate consequence of the de f i n i t i o n of d i v i s i b i l i t y * Theorem 5* If J~' (£) > f-*. ) b e a n v * w o poly-nomials and "77~a prime of •$(<) , there exists a common divisor, , mod , of J~< (j) ? (j) such that j ) ^ ) is d i v i s i b l e , mod 7T-, by every common divisor, mod ~T~ „ of f' ^ j) 3 J-*- CJ^ * a n <^ "there exist two polynomials Cj) such that Assume that -f-^ ^ ) i s of degree not higher than // ^ ) • Then we may obtain two polynomials c£,(j) and /s^jJ such that J^3 ^) being of lower degree than j-^ (^) . Dividing y £ ^ Cj) where * i s of degree lower than fs (j) Similarly and since the degree of each remainder i s decreasing we must f i n a l l y , after a f i n i t e number of steps reach a remainder ' J[M_f/ (g. ) which i s zero, mod 77~ . Now the common divisors, mod , of r ) and -f^ Cj^) are identical with those of ^  ) and jz^.^ and so on u n t i l f i n a l l y those of £^ , (j)- and ^ 3 with those of a n d £ (§)•"• But ^ ; i s a common divisor, mod of J^.^) and a n d i s evidently d i v i s i b l e by every common divisor of f^tj) and • Hence ) i s the required common divisor, ~J)(j) > mod 17- , of fi^J and A</; • Now substitute for J~s ^ ) * n t n e second con-gruence i t s value i n terms of £(j) a n d y £ ) found from the f i r s t congruence, s i m i l a r l y the values of -f3 (j) andJ-/^) i n the third congruence their values i n terms of f, <j) a n d y ^ ^ and continue u n t i l the congruence 18. where^- (g) and f_f (j) are expressed i n terms of f,fj) and fs-fg) w e s h a l l obtain the congruence Gor: If f'(j-) * /-_2. <jJ ^e * w o polynomials prime to each other, mod 7T , there exist two polynomials <fi (j) and <^_<^.) such that Here is an integer not d i v i s i b l e by 77~ , and so we may find two polynomials and f£ A (j) such that Multiplying by the reciprocal, =v& of ^ we have Theorem 6* If the product of two polynomials ft £f^. be d i v i s i b l e , mod W , by a prime polynomial, ) f at least one of the polynomials, f> fj} > fa. (j ~> i s v i s i b l e , mod IT , by r~^)£?J and suppose that £ fj) i s not d i v i s i b l e j mod If, by <~l~>^)-Then there exist two polynomials, <tfJ ? £ ^ ) such that since ) a n ^ ^ a r e P r i m e » m G < 3- ^ » *° e a c h other* Then Hence by (1) 19. where + f^§^ <?LC^) i s a polynomial. Hence /^(j) i s d i v i s i b l e , mod 77—, by T->^)i Cor 4: If 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 least one of the polynomials is d i v i s i b l e , mod ~77~t byHP^^-Cor 2: If neither of two polynomials be d i v i s i b l e , mod ~n~ by a prime polynomial ) , their product is not d i v i s i b l e , mod 7T \ by " P £ ) . Theorem 7. A polynomial » can be resolved i n one and but one way into a product of prime polynomials, mod ~TT, Let be a polynomial of degree , mod lf~ and in i t s reduced form, mod 77"~. Then A^J.) i s either prime or has a divisor, ^^j) say, mod 77~ . I f is prime, the theorem i s evident. If i t is not prime then where the sum of the degrees of^^J^ and is ~H and neither i s a unit. If i s not a prime polynomial i t must have a factor fi^l » m o d » s o *hat where neither ^?^)or yr (j) i s a unit and the sum of the degrees of (j) and X, (j) is the same as the degree of If (j) i s not a prime proceed as before. Since the degrees of the factors are decreasing we must, after a f i n i t e number of steps reach a prime polynomial 20. T?^) » mod W~* Then Proceed i n the same manner with ^ (j ) • I f i t i s not 'prime we must f i n a l l y obtain where f^<j) i s prime, mod IT . Continuing this process we must after a f i n i t e number of factorizations reach a prime polynomial~~I^L) * m o d * such that where (j) y~T^(j), <^ ) are a l l prime polynomials, mod ^~ , and >€. i s f i n i t e . To show this factorization i s unique, assume that we have Then -<•* I J~? Then at least one of the eS. (^) , say « ^ ) , must be d i v i s i b l e , mod , by^Tf (^) and hence, since they are prime, must be associated, mod 7T~ where is a unit, mod // . 21, Proceeding as before we may show that for each ^ ) there i s associated, mod 7T~, at least one Sj (p . More over A f two or more T^fj)?? are associated with each othe 'at least as many <J?^)'so are associated, mod T~, In the same manner we may show that with each <=^^) there i s associated, mod TT, at least one Ti£ (j) , Hence the two resolutions are i d e n t i c a l except for perhaps a unit polynomial. Any polynomial may therefore be written i n the form XIII, Resolution of a Polynomial Into Its Prime Factors  With Respect to a Prime Modulus* The resolution of a polynomial -f(j) into i t s prime factors, mod TT , may be effected by dividing, mod 77", the polynomial by each of the prime polynomials of the f i r s t degree jt ^-/, , J - i n turn u n t i l one i s found which divides ^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 ^ be the f i r s t such polynomial which divides * mod 7T% and l e t J~>^) be the quotient. Continuing as before* we see whether i s d i v i s i b l e by any of the remaining prime polynomials of the f i r s t 22 . degree. F i n a l l y we obtain where* y4l ^ ) contains no factors, mod 77^ of degree less "than the second. To find the prime factors, mod 7T~, of the second degree we determine, i n the same manner as above, which prime polynomials of the second degree divide (j) , mod 77" , and si m i l a r l y for those of the third degree, etc. If , however, we do not know the prime polynomials of the second degree we may determine whether ) i s d i v i s i b l e , mod 7Tr by any polynomial of the second degree. If i t i s , then such a polynomial must be prime since contains no factors of degree less than the second. The same applies for polynomials of higher degree. X1T. General Congruence 2£th Degree in One Unknown. Theorem 8, I f b e a root of the congruence ^-(^) i s d i v i s i b l e , mod 7r~, by J-y° * a R d conversely i f /^j) i s d i v i s i b l e , mod 7~, b y ^ - y ° » thenyois a root of (1), Dividing y ^ ; by ^ ~ / ° * m o d ~ » w e obtain If j° i s a root of (1) then J~^/°J == O , mod w Hence /<JJ ^ 7r" i , e, f~(^) i s d i v i s i b l e , mod 7T~, by ^  — y° --71— 23. Conversely i f j-'C'^) i s d i v i s i b l e by g -yo , mod 7T, then f-(/°} = o » m o d a n d bence yo i s a root of (1). Theorem 9. The number of roots of 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 linear factors and i t cannot have more linear factors than i t s degree when the modulus i s a prime* Cor: I f the congruence has exactly as many roots as i t s degree and (p(j) be a d i v i s o r s mod 7T~t of -^(^) , then the congruence has exactly as many roots as i t s degree For since then every root of (1) i s a root of either or of Now the sum of the degrees of (3) and (4) i s equal to the degree of (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 vice versaj which i s contrary to theorem* 24. XV. The Congruence ^ — / ^ *—>^^<r-ac^ . Theorem 10, The congruence - has exactly as many roots as i t s degree. By Fermat's theorem we see that the <^u)integers of a reduced residue system, modyu. , sa t i s f y (1)* More-over, since two integers which are congruent, mod^ must have w i t h ^ the same greatest common divisor, any integer satisfying (1) must have wither the greatest common divisor unity* that i s * must be prime Xo^a • Hence the number of roots of (1) i s exactly equal t o ^ V , i t s degree, . Cor. I f <f be a positive divisor of •»». [V1 ~/ , then <T y -r- CO the congruence •j , - 0 j where // is a prime of , has exactly cT roots; for -/ is 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 the congruence „ -»-<- JV7 „ has ~n> [ t t ] roots and hence i f <^ t, - j °<^ w constitute a complete residue system* mod ~TT~, we have the ident i c a l congruence s ( / " - - c / - ^ ' ™ ^ o or, since JT is a prime, we may chose as our residue 25. system, mod ~TT , the -n. JV2 rational integers °) j [ V ] - / ? and so XVI* Analogue to Wilson's Theorem i n If 7T be a prime of /fVVJ and /°> P, P , be a reduced residue system, mod 7T", then We have Let 5^ be the sum of a l l possible products of /J, » / ^ v w taking j at a time. Then - / ^ S,>^L--'--~+C-O^S-w Equate coefficients of l i k e powers of £ . Then Now since [ V ] - 77~7r 7 i s always odd except when /T-= /+u or i t s associates, ^ Ctt) =• ">c £-*-"] -/ i s even and therefore When = /?«•-*'_, or i t s associates, = -2. ^?(tr) = and we see that the theorem i s also s a t i s f i e d . The theorem may also be proved d i r e c t l y by putting ^ = o i n the congruence (1) and proceeding as above* 26. XVII. Common Roots of Two Congruences. The common roots of two congruences ./> <JJ — Oj — and =• oJ ^<^^ yr~ ' are the roots of the congruence where i s t n e greatest common divisor, mod TT-, O I J-,CJ) and y> fj ) Therefore, in order to find the incongruent roots of any congruence with prime modulus, we need only find the roots of the congruence where is "the greatest common divisor, mod ir~% of the given congruence and the congruence This follows since the l a t t e r congruence has for i t s roots the roots of a complete residue system, mod ~TT\ XVIII. Determination of Multiple Roots of a Congruence  with Rrime Modulus. Theorem 11. I f the congruence has a multiple root yc? of order ~g , the congruence has a multiple root of order For l e t be a prime polynomial, mod 7T~ and suppose f^J) is d i v i s i b l e , mod 77~, b y p p ^ V j but not n -> -£+/ by f p c ^ ) ] . 27. Then where and 7 ^ ; are polynomials, and T^j) and f-^j) 'are prime to each other, mod 7T . Also where ) ? gt '(^y ^ ^ ) 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 less than ~P^) and <2<^ ) i s prime to "P^J » mod TT • Theref ore f(j) i s d i v i s i b l e , mod 7T, by j^~p ) ~j but not by f f P ^ j ] ^ . In p a r t i c u l a r , i f ; has a root, JD , of order , then j-kj) has a root, y° , of order t f - / • XIX. Congruences i n One Unknown and with Composite  Moduli. To find the solution of a congruence of the form where ^ Case I. When^/t. are integers of 7eU) which are prime to each other the solution of (1) may be reduced to the 28. solution of a system of congruences This follows since every root of (1) obviously s a t i s f i e s each of the congruences (2) while any integer 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). If then, p. be the roots of the congruences (2), and i f \\ be any integer of &<) such that then £ i s a root of 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 be Asolved into the V congruences The solution of such a congruence may be made to depend upon the solution of one of the form where the power of the modulus i s one less than in the ori g i n a l congruence, and so f i n a l l y may be made to depend upon the solution 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. ^ where 7 i s an integer of &j) , are roots of (5). Since a l l roots of (4) are roots of (5), any/root of (4) must be of this form. Then ^ — 77 or and hence since -f(^) == <o> -~^<^~&£ TT~ * '} / ( p = K 7 7 -and dividing each term of (6) by 77~ •' ' we find This i s a necessary and s u f f i c i e n t condition that ^ must sa t i s f y i n order that a root of (5) may also be a root of (4). (a) If -f '(f) j£ O, then there is one and but one value of ^  which w i l l s a t i s f y (7) and so one and but one value J" •+- y 7T\ which s a t i s f i e s (4). (b) If f 'CfJ c>j -^rt^Tir: j v<- ^  /< ^ O-^^TT there is no value of y satisfying (7), and hence no value of ^ of the form j -+- ~7T^. y satisfying (4); that i s , (4) has no root. (c) I f f'ff* "™<^"7 j G^ct K=~ o -^^77* then (7) i s an ident i c a l congruence and consequently has ^ £7/7] solutions, mod 7TT , from which we may find ^C'TT] solutions of (4). 30. Example: Solve the congruence This may be made to depend upon the solution of which has as a root ^ ^ / } ~^^.^-^ / - ?^-e' -Then the roots of (1) are of the form Substituting i n (1) we obtain This gives / as the only root of ( 1 ) , XX. Residue of Powers* I f i s prime t o ^ and i f ^  =• <=<: , mody* , where £~ is a positive rational integer, then/^ is called a power residue of «?< with respect to the modulus^*'. A system of integers of such that every power residue of * mod^^ , is congruent to one and only one integer of the system, modyfc * i s called a complete system of power residues of <\ with respect to the modulus >-y£ • Consider the congruence ^ =• /, —x^-^^c CO It i s evident from Fermat*s theorem that /"always exists and that ^ PC**-) * T n e integer ^  i s said to appertain to the exponent when • i s the smallest value of jf~, other than zero, for which the congruence (1) i s true. 31* I f » mod^, then <=< and ^3 appertain to the same exponent, mod^ . Theorem 12. If the integer <=>< appertains to the exponent , mod^ , then the --^ powers of ^  , ^ ° = o*', ^ ; ^ c ^ - ^ _ / co are incongruent each to each, modM * Let o<r and °< be any two of the series (1) and assume that Then since ©< i s prime to i . e. CK. appertains to the power ^ } - ^ - ^ contrary to the hypothesis that o< appertains to the exponent , Theorem 13. I f ^ appertains to the exponent , mod^^ any two powers of c< with positive exponents are congruent or incongruent to each other, mod>A' » according as their exponents are congruent or incongruent, mod * Let o< ' by any two powers of o< where 5"(J 5^  are positive integers, and l e t S, = ^ G.+r; • , ^< , <'> and ^ being positive integers and osr**^ > o * a ^ ^ , -r^ri & Assume that Then and since i s prime to 32* But, since O ^ K-1 < by ( 2 ) , and o< appertains to the exponent , then •n - ri = o Therefore, from (1) i s a necessary condition for (3) to be true. Moreover, i f (8) i s given, then from (1) r, = n- > — — ^ and hence since r and y? are both less than £ we must have Then and since we have Therefore (6) i s also a s u f f i c i e n t condition that (3) be true. Moreover The rel 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. The exponent to which an integer <=< appertains, mod^r, i s a divisor of £7^) For"* and, therefore, by theorem 13, i . e . jZtffa-) i s d i v i s i b l e by -Theorem 15. I f two integers, ^ , and ©< a , appertain, modyt , to two exponents tit^ , , respectively, that are prime to each other, then their product, <=<t apper-tains, mod^ , to the exponent • Let appertain to the exponent mody^r Then and so But so that J- 0) But appertains to the exponent , mody^d , and hence, by theorem 13, i s d i v i s i b l e by and, therefore* since ^ and are prime to each other, ^ i s d i v i s i b l e by . Similarly we may show that J ~ i s d i v i s i b l e by so that ^ is d i v i s i b l e by ^ . Hence the smallest value of such that (1) i s true is = -"v * 34. Theorem 16. To every positive rational divisor or (p(w~) there appertain tVCs) integers of with respect to the "modulus Zri 7T~ being a prime of /f(<% Let denote the number of integers of which appertain to the exponent -^t» Then ~X.(f) ^ O Assume that to every positive divisor, of qp6r) there appertains at least one integer o< . Then each of the integers •> ° * J O < , - - > ^ which, by theorem 12, are incongruent to each other, mod 7Tt i s a root of the congruence J ^  / j (A) For i f cxtf be one of them, then since ^ / ^ — -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 mod 7T~. Then i f K contains a factor, say, of -A, we have and since < o<f does not appertain to the exponent st~» Moreover, i f A i s prime to ^ "then oi K appertains to the exponent--^, for suppose o< * appertains 35. to the exponent -f- . Then since ^ appertains to the exponent *S~t mod 77~. 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 conditions that any one of the integers (1) s h a l l appertain to the exponent mod 77~t i s that i t s exponent be prime to This i s s a t i s f i e d by g?ft)of them. Hence Since every one of the ^PCv) integers of a reduced residue system, mod 77~„ appertains to some exponent and every such exponent i s a divisor of the ^PCTT) , i t follows that where are the positive divisors of fl)(7r) But whence 3 6 . I f , then, any ~)C (jt\) — O , (4) would not be true. Hence no ~X.(£- .) — a and therefore X ) = pes.) XXI. Primitive Roots. Any integer that appertains to the exponent f?(/<-) with respect to the modulus^; , i s said to be a primitive root ofyc • I f TT i s a prime of ~$(<j , then by theorem 16, has (p [_ (pM ~j incongruent primitive roots. Let y be a primitive root of ~7J~~. Then by theorem 12 the integers f,/ 0) - - — v /* form a reduced residue system, mod 7t~ • Conversely, i f , /°''^constitute a reduced residue system, mod 77~ , theny° is a primitive root. For l e t jo ^ y 7 4 be any two of them and l e t « > b>°< i . e. where A- 6 may have values from / to (^CTTJ - / In particular H e n c e i s a primitive root of ~77~. We may therefore define a primitive root of '// as an 3 7 . integer of fa) such that a complete system or i t s power residues, mod 7T , constitute a reduced residue system, mod* 77". We sh a l l now give a second proof of Wilson's theorem depending upon this d e f i n i t i o n . Let F f e e a prime of such that ^ QTTJ is odd, and l e t j° be a primitive root of i r and f, } > f^rJ a reduced residue system, mod y r . Then since y^/ 0* — j/° a l s o constitute a reduced residue system, mod 7T~ T we have and are the integers /, .2, <pt>r) i n some order. Multiplying these congruences together we have Ht* ^ . .'- T T ^ s f> , ~™~^7r-But since we must have 38. Therefore •^ IFTT} is always odd except when ~7T~=} or ' i t s associates, i n which case JJTT] = 3. , The proof as given here does not apply for this case although the theorem i s true since then y?f*-J =• / , and we take / as our reduced residue system, mod /-*••£. . XXII. Indices. Let P be a primitive root of 7T~ . Then f, f, - - -— f° constitute a reduced residue system, mod // , so that any number °< which is prime to 7T~must be congruent to some power of j° , mod TT . If then i s said to be the index of <=>< to the base y° , mod 7T~T and we write ^ =• ^ ^^^^ <xc j ~—?^x>*-<af TT- . It may be shown that indioes obey the following Iaws: analogous to those of logarithms. 1» The index of the product of two integers i s congruent to the sum of the indices of the factors, mod yP CTT) or i n general 59. Then 7F~ • and therefore i . e. As a pa 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 particular primitive root chosen as base. If, however, the index i s known for a particular base we may find i t s value for any other base. For l e t jcf and be two primitive roots of 77"", and l e t A - > <—^^> so that Let c< be an integer of such that Then and hence 40. In p a r t i c u l a r , putting o< =• jo , we have i . 6T. . /? = / , — Theorem 17. If <=<: , mod 77", be , and is the greatest common divisor of -c' and ^/Vy 1 , then <=< appertains to the exponent ^Vj"/^ We are given that «-<' ~ j£> ^ ^-^^<»-0e- 77—~ Let be the exponent to which <=* appertains, mod 7i~ . We wish to find the least value of J- such that Now and hence > Then where i s the greatest common divisor of -c' and . Then ^ 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 to the exponent » mod 7 7 - . The converse of this theorem i s also true; 1. e., whatever primitive root, f> t 0 f 77~, is taken, i f c=f 41. appertains to the exponent , mod 7 7 ~ , then d is the ^greatest common divisor of -^»* «=<? a n d gP^Tr) Cor: If is a primitive root of 3 7 ~ ~ s then the <f \jP (l*)\ primitive roots of 7 T ~ a r e those incongruent powers of y° whose exponents are prime to y?(7r) -XXIII» Solution of Congruences by Means of Indices* If we have a table of indices to any base for a given modulus 7T we may solve any congruences of the types (a) ^j j —~sr-or (b) •== y€J where in each case <^ i s not d i v i s i b l e by ~7T~ * In case (a), taking indices, we have whence and knowing ~^i_cf ^ , and ^*~cf <^ we may find ~<^-cf ^ and so find zy. In case (b) we have a congruence of the f i r s t degree in one unknown. The necessary and su f f i c i e n t condition that this be solvable i s that be d i v i s i b l e by <af , the greatest common divisor of and ^^r) * When this condition i s s a t i s f i e d there are [ei] values of corresponding to which we find C . ^  ] values of y which are incongruent mod 7T and which s a t i s f y the congruence (b). XXIV. Binomial Congruences. We give here another method of treatment for the subject of power residues and primitive roots from a consideration of the binomial congruence O 3 — - *- 0) We have seen that a l l roots of ( 1 ) w i l l be roots of the congruence where ^^J^ i s greatest common divisor, mod ~7T~ , of / and ^  — / . It is easily seen that / where ^  i s the greatest common divisor of and <P&r) . For a l l common divisors of £ - / and —/ must be of the form £ where ^ i s a divisor of both and (pCw) Moreover, it of i s a divisor of ~H. then ^ / is a divisor of ^>~*L/ . Hence i f ^  ^ / is the greatest common divisor ot a n d f l ' * ^ y ^ then <s*f i s the greatest common divisor of >c and i^/Tr) , The congruence (1) has, therefore, incongruent roots and these are the roots of the congruence J / == O j -~r^*-^-7r- . ^ Those roots of (2) which satisfy no binomial congruence of degree less than (2) are called primitive 43. roots of (2) while those roots of (2) which satisfy b i -nomial congruences of lower degree are called imprimitive roots. The primitive roots of (2) are, then, those integers which appertain to the exponent &t , mod ~t>~. They are (pfd) i n number. In par t i c u l a r , the primitive roots of 77" are the primitive roots of the congruence If y° i s a primitive root of (2) then the °^ roots of (2) are, by theorem 12, /> P, f *~j J f I f o(l j are roots of the congruences and respectively, then <=^t ©e i s a root of the congruence g << < / ^ 0 ^ ^ ^ £ T T - & In p a r t i c u l a r , i f °< and <vA are primitive roots of (3) and (4) respectively, and i f c// and c?x are prime to each other, then °C, °<fx i s a primitive root of (5). XXV* Determination of a Primitive Root of a Given  Prime Number. The method, due to Gauss, i n which we find a succession of integers appertaining to higher and higher exponents, w i l l apply equally well i n the f i e l d fa) -We must* i n such a process, find an integer which appertains to the exponent gPCv-J , mod 7T~t and hence i s a primitive 44. root of ~7T~ . we may prove, however, that i f a. i s a primitive root of ->t. QTT] -fZ } then ct i s also a primitive root of 7T i n . If # is a primitive root of C"n\l i n 7^ ? then <Z i s also a primitive root of 7T i n Let "H. £TT] •= , a rational prime. Then since «. is a primitive root of ~p> , ^ = / J i • e, 7s-/ A Therefore, (3. === CI == /j - ^ ^ 7 T . We must s t i l l show that CL does not appertain, mod 77" , to an exponent less than £^W"J . Suppose <3. appertains to the exponent f , mod 77~ , where -f- ^ ^^ir) Then and so, since <z - / i s a rational integer, i n which case <2 appertains to an exponent -=r <pcr) i . e. -=^ .p^ t. On-] ) i n ^  , mod •?< C-7r] and so i s not a primitive root of ->t CTT] } which gives a contradiction. Therefore <2 i s a primitive root of ~7T i n ^ r ) . In order to find a primitive root of r , therefore, we need only find a primitive root of -** £V] i n . This w i l l also be a primitive root of 7T in . 45. The remaining primitive roots of 7^ may be found by applying the cor. of theorem 17. For example, to find the primitive roots of f i r s t f i n d a primitive root of -a-^  \Z4^<>'c~\ — „ To do this form the power residues of J2. , mod ^ / These are - V , -<T, - / ^ - -2^ ^ - , ^ / Then 5 appertains to the exponent , mod >/•/ * Wow form the power residues of 3 » mod *-f-l . We have so 3 appertains to the exponent f , mod "// . -Take ^ = • r • * The greatest common multiple of , and -^ ~A i s ~~^c-=.^/0 • Divide ^ into two factors 5w7 and prime to each other and such that i s a divisor of y and *?*cx_ a divisor of ^- . Then = s>- = ? Now Then 2^. and 3 appertain to the exponents ~ and respectively and so their product^ <?- ^  X 3 . ^  appertains to the exponent = ~ x F — . Therefore ~z x 3 i s a primitive root of 46. Now Therefore / i s a primitive root of It i s also a primitive root of ~77~ - ^ /*- s>~^ ' ^C^) Then the c# [_Cp(w)~\ = <p(4o) = /£ primitive roots of 7T~ may be found by applying the cor. of theorem 17. That i s since / is a primitive root of *yV.5V, then the Cp £(P(+/+sZprimitive roots of are those ty j^T (p(4+**) J incongruent powers of J whose exponents are prime to ^C^-f-i"^) • These are • /, 7, 7 , 7 , 7 , 7 , 7 , 7 , 7 ; x ~ 7 a f / " which may be reduced to integers of XXVI. The Congruence We may reduce any congruence where i s not di v i s i b l e by i r ~ , to one of the form Consider the case i n which /3 o, mod TT~ . From previous discussion we have the theorem, Theorem 18. The necessary and su f f i c i e n t conditions that the congruence sha l l be solvable, i s that ~*^-<zf^ shall be d i v i s i b l e by the greatest common divisor, a t } of and yPtir) ; 47. this condition being s a t i s f i e d the congruence has exactly %C<^ ] incongruent roots. Theorem 19. Euler's Criterion for the f i e l d I f o * 1 be the positive greatest common divisor of **<- and y?(Tr) » the necessary and suffic i e n t condition that the congruence s h a l l be solvable i s This condition being s a t i s f i e d , the congruence has exactly ^ D ^ ] incongruent roots. Let y° be a primitive root of 7T\ and l e t {3 = I f (2) i s solvable then i s d i v i s i b l e by Let ^ = ^ • Then and Therefore (3) i s a necessary condition for 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 since i s a p r i m i t i v e root, so "that ^- i s an integer. Therefore -e i s d i v i s i b l e by <sf and (2) i s sol v a b l e . Hence (3) i s a l s o a 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 ( 2 ). A l l incongruent integers /3 , fo r which the congruence (2) i s s o l v a b l e may be obtained by observing that they are roots of the congruence The congruence (4) has (*^ r ) incongruent roots which are the incongruent values of /3 f o r which (2) i s solvable. Such members congruent to the ?t th power of an integer, mod If, are c a l l e d ~?£-^c residues of 77~~% and we have the f o l l o w i n g : Theorem 20. The number of incongruent --^a residues, mod 77" t i s <^-~f~J where <s*f i s the p o s i t i v e greatest common d i v i s o r of % and ^ % i a n d these residues are roots of 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