Annals of Mathematics

On the Numerical Factors of the Arithmetic Forms n n Author(s): R. D. Carmichael Source: The Annals of Mathematics, Second Series, Vol. 15, No. 1/4 (1913 - 1914), pp. 30-48 Published by: Annals of Mathematics Stable URL: http://www.jstor.org/stable/1967797 . Accessed: 12/10/2011 15:39
Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at . http://www.jstor.org/page/info/about/policies/terms.jsp JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about JSTOR, please contact [email protected].

Annals of Mathematics is collaborating with JSTOR to digitize, preserve and extend access to The Annals of Mathematics.

http://www.jstor.org

ON THE

NUMERICAL

FACTORS

n i34

OF THE
*

ARITHMETIC

FORMS

BY R. D. CARMICHAEL.

Let a + ,3and ao3 be any two relatively primeintegers(different from zero). Then a and : are rootsofthe quadraticequation
Z2 (a + 3)Z + Ca4 = 0.

It is obviousthat the numbers and Sn, Dn

Dn = ?

on

a n-1 +

n-2

...

13n-1

Sn =

an + O3n

are integers, since they are expressed as rational integral symmetricfuncwith tions of the roots of an algebraic equation with integral coefficients leading coefficientunity. The principal object of the present paper is an investigation of the numerical factors of the numbers Dn and Sn. The case when a and : are roots ofunityis excluded fromconsideration. (See ? 2.) The most valuable treatment of the questions connected with these numbers is that of Lucas. t The special case' in which a and i3 are integers has been considered by Siebeck,4 Birkhoffand Vandiver,? Dickson,11and Carmichael. ? In Lucas's paper many results of interest and importance are obtained. The methods employed, however, are oftenindirect and cumbersome. In the present paper a direct and powerfulmethod of treatment**is employed throughout; and in connection with the new results which are obtained many of Lucas's theorems are generalized and several errorstt in the statement of his conclusions are pointed out. In ? 1 several fundamental algebraic formulae obtained and a partial are factorization of Dn and Sn is effected. In ? 2 these algebraic formula are employed to derive numerous elementary properties of the integers
* Presented theAmerican December, 1912. Mathematical Society, to 1 Journal Mathematics, (1878): 184-240, of 289-321. tAmerican 33 1 Crelle's Journal, (1846): 71-77. (2) ? AnnalsofMathematics, 5 (1904): 173-180. Mathematical Monthly, (1905): 86-89. 12 American ? American 16 Mathematical Monthly, (1909): 153-159. ** Compare themethod by employed Dicksonin thepaperalreadycited. der tiber ttComparethe reviewof Lucas's paperin the Jahrbuch die Fortschritte Mathematik, (1878): 134-136. 10
30

ON THE NUMERICAL

FACTORS

OF THE ARITHMETIC

FORMS.

31

and are DAand Sn relativeto divisibility, theseproperties statedin explicit

theorems. In ? 3 the importantquestion of the appearance of a given prime is investigated. The principal factorin the sequence D1, D2, D3, resultsare containedin TheoremsXII and XIII. Attention called to is in the newnumber-theoretic functions introduced connection withTheorem XIII and its corollary. In ? 4 a detailed study is made of the numericalfactorsof a set of numbers whichare the values of an algebraicform Fk(a, ,3)whichmay be
...

of as factor a-'k defined thatirreducible algebraic

in of any a" - p3" which v < k (but see the definition ? 1). This infor in vestigation fundamental the studyof the numbers and Sn,and the is Dn resultswhichare here obtainedhave important in applications the theory of numbers. Attentionis called especiallyto TheoremsXIV, XVI and XVIII. " In ? 5 the theoryof " characteristic factors of F., Dn and Sn is developed. In ? 6 verysimpleproofs givenof certainspecial cases of Dirichlet's are celebrated theorem the of concerning prime terms an arithmetical progression of integers;in particular, is shown that thereis an infinitude prime it of of 4n numbers each of the forms + 1, 4n - 1, 6n + 1, 6n - 1. In ? 7 are given a numberof theorems whichare usefulin the identification largeprimenumbers. Amongthe results of obtainedthe following two alone willbe mentioned here:A necessary and sufficient condition that a givenodd number is primeis that an integer existssuch that p a F,-,(a, 1) 0 mod p; a necessary and sufficient condition that 22"+ 1, n > 1, is primeis that 3221 + 1 _ O mod 229+ 1. Let 1. Notation. FundamentalAlgebraicFormulae.
Qn(X) = 0

1kwhich nota is

factor

be the algebraicequation whoserootsare the primitive rootsof unity nth withoutrepetition, coefficient the highest of the powerof x in Qn(x)being unity. The polynomial integers;and it is of Qn(x) has all its coefficients wheres(n) denotesthe numberof integers greater not than n degreesp(n), and primeto n. From the theory* the primitive of rootsof unitywe have two formulae
* See Bachmann's the lecture. Kreistheilung, especially third

32

R.

D.

CARMICHAEL.

whichare fundamental our purposes. Thus, for

= jjQd(X),
d

whered rangesover all the divisors n. Also, of

(2)

Qn(X)

(Xn l(XnP

1)
1)

llI(XnIPiPi _ (Xn/pipipk

1)
-

...

'-

1)

...

wherethe p's denotethedifferent factors n and wheretheproducts of prime denoted II extendover the combinations 4, 6, ** at a timeof Pi, P2, by 2, and over the combinations 3, 5, * at a time 1, p3 * * in the numerator in the denominator. Let a + , and ao3be any two relatively primeintegers(different from zero); then a and 3 are the rootsof the equation
Z2 (a + O)z + ao3 = 0

a whose coefficients + , and a: are any two relativelyprime integers both of whichare different fromzero. We shall exclude the trivialcase = , = 1. It is thenclearthat a and ,3cannotbe equal. CZ Now an + A represents integer everyvalue of n, since the funcan for tion an + on is a symmetric in polynomial a and A and has integral coefficients. On the other hand the functionan An does not necessarily o have an integralvalue. If, however,this numberis divided by a - B theresult clearly integer, is an sinceit mayobviously written a rational be as integralsymmetric functionof a and : with integralcoefficients. Aclet cordingly, us define integers and Sn, foreveryvalue of n, by the the Dn relations on On-1+ Cen-2 + ...+ Sin = Cen On. + Dn = Cen0 n-1

Then, obviously,
Sn
D2n

Dn

so that a studyof the factorization the form of values ofn, Dn, forvarying includesincidentally that of the form Sn. We shall therefore interested be in primarily theform Dn. We define (a, 3) by the relation Fk
(3) k = 1.
Fk(ae, 3) = I3 (k)Qk(aII)

We shall now show that Fk(a, 3) is an integer everyvalue of k except for

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

33

kth root of Then suppose that k is greaterthan 2. Let w be a primitive Then evidently, unity.
(4)
4(k)

Fk(a,

0)

by (k)Qk(a/0)

II(a

wa8i)

less positiveintegers than the wherefori = 1, 2, ** , p(k), s, are the wo(k) k and primeto k. Hence
4(k)

Fk(a,

d)

I (a

since when

coc-

s, + sk = k

fall in and the factors the above equationobviously intopairssuch that the sum of the s's in each pair is k. Hence we see readilythat
16(k)

Fk (a,

f3) =

II

(k)

i=1

(aWk"

-(

j=l

w8a),

where in the last membersj is writtenfor k - si. By comparingthis equation with (4) we findthat
Fk(a, 3) = Fk(1, a);

to with thatis, Fk(a, 3) is symmetric respect a and 3. But it is a polyHence we concludethat coefficients. nomialin a and d withintegral k valueof k except = 1. for The number Fk(a, () is an integer every Now from(1) we have readily
(5)
= DDn
a-

= IT'Fd(
=L

whered ranges over all the divisorsof n except unity. This important of Dn. Likewise,if v is formulagivesa (partial) factorization theinteger any divisorof n, (6)
Dw.v=

dka

3),

II' Fa(a
a

(),

wherea rangesover all the divisorsof n/vexceptunity. If now we divide we the first these equations by the second,memberformember, have of (7)

n= a0(&-1)/&-+ an (-2)/Yn/

. .

an"'(3n

-2)1v4+ on(v-1)/v.=.

JIFk(a,

3)

wherek rangesover all the divisorsof n whichare not at the same time divisorsof n/v.

34

R. D. CARMICHAEL.

From (2) we obtainreadilythe equation

fi) Fn~a,0) =I(an/Pi

(aOn-

fn) . IIH(an/pipi -_ An/Pipi) ... - OPiPjPk) _ On/pi) . (an/PiPjPk

...

2, denotedby II extendover the combinations 4, 6, * wherethe factors and 1, at a timeofpi, P2, * * * in the numerator overthe combinations 3, 5, ... at a time in the denominator. The total numberof factorsin the for, of numerator this equation is the same as that in the denominator; is the of obviously, first these numbers the sum of the positivetermsand of the second is the sum of the negativetermsin the expansion (1 - 1)? of of r primefactors n. formula, beingthe number different by the binomial and denominator in each of these factors both numerator Hence, dividing by a - f, we have
..

(9)

Fn(a, fi)

H[Dn/ H[Dn/ .. ipjpC pi

Dn

H IDn/ipip...*

wherethe productsdenotedby II have a meaningsimilarto that above. of Let p be any primefactor n and write n = ppa whichis not divisible a wherethe exponent is so chosenthat v is an integer by p. Considerthe factorsin the second memberof (9) into which p from(9) itselfit it clear that thesefactorsalone does not enterexplicitly; into In the same-waywe see that the factors have the value F (aPa, fpa). Hence have the value 1IF1(aPa-, fpPal1). whichp entersexplicitly (10) Since
Fn(a fi)
-

F,(pa,

fpa)

F1(,pa-l,
- a,

pal)

Fi(af)

=a

for formula determining Fn(a, f) equation (10) may be used as a recursion < 36, Sylvester'stable* of cyclotomic functions may conveniently For n for be employed finding Fn(ayf). that (10) may be proved In passing we note withoutdemonstration of for and thenbe employed the derivation (9).t directly If, now, in equation (7) we replacen by 2n, give to v the value 2 and that remember
D2n

we have

D=

Sn,

(11)

Sn=

an + fI

A,

Fk(a, f),

* American 2 of Journal Mathematics, (1879): 367-368. 1. Dickson, c., p. 86. t Compare

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

35

integerSn.

wherek runsoverall thosedivisors 2n whichcontain2 to the same power of as 2n itself. This important formulagivesa (partial) factorization the of Let v be any odd divisorof n; then,writing forn in (11) we have n/v

(12)

= Sn/,

flF(a, (
k

),

where runsoverall thosedivisors 2n/v k of which contain2 to thesamepower as 2n/vitself. Dividing (11) by (12), member member, have for we
(13)
Sn
Sn/ Y

II

Fk

odd,

where runsoverall thosedivisors 2n whichcontain2 to thesame power k of as 2n itselfand whichdo not divide 2n/v. 2. General Propertiesof the IntegersDn and Sn Relativeto Divisibility. In view of the fact that a rationalintegral symmetric function a, 0j of with integralcoefficients an integer have readilythe two equations is we (a + fl)n = an + fOn af3Il = Sn + c43I1, +
Dn
=

3n1

+ a1312= Sn-i +

a13I2,

whereI, and I2 are integers. Since ad and a + ,3 are relativelyprime integers follows it fromthe first these equationsthat Sn is primeto a13 of foreveryvalue of n. Then from secondof the equationswe conclude the that Dn is likewiseprimeto a: foreveryvalue of n. Hence we have the following theorem: THEOREM I. The integers and Sn are both Dn primeto ao(. This theoremenables us to dispose of an exceptionalcase; namely, whenDm = 0 forsomevalue ofm. In thiscase alm = (3mand hence
Sm= 2am.

But Sm is prime to aodand hence to amolm". These two resultsagreeonly when

so that in thiscase a and ( are both rootsof unity. It is easy to see that Sk can assume no other value than - 2, - 1, 0, 1, 2; for Now
jka ISkl< l +
(3kj

= 2.

(a

()2

(a +

()2

4ao =

integer;

36 and hence since a

R. D. CARMICHAEL.

la -(3l

1,

disso thatDk can take onlythevalues -2, - 1, 0, 1, 2. A corresponding = 0 forsomevalue ofm,and withlike results. cussioncan be madewhenSm both The cases Dm = 0 forsome m and Sm = 0 forsome m are therefore trivial. They arisewhenand onlywhena and A are rootsofunity. Hence a the fromconsideration case in which and (3 we in what follows shallexclude from are roots unity. Then Dmand Smare alwaysdifferent zero. of Now and hence
-

Dkj _ak

< - O3ki lakI + l(kI = 2,

(aOn+
52

on)2 -

(aOn -

On)2 =

4ann,

(a

3)2Dn2 =

4a n/n.

()2 is an integer. Then from the above equation it It is clear that (a divisorofSn2 and Dn2 mustbe a divisorof4a n~n; that any common follows but by TheoremI such a divisoris primeto ad. Hence it is a divisorof4. primeor theyhave the greatest either and Sn are relatively Therefore, Dn commondivisor2. That both of these cases may arise is shownby the examples: following divisor2 and hence (1) a = 2, (3 = 1. Dn and Sn have not the common are relatively prime; (2) a = 3, ( = 1. Dn and Sn have the commonfactor2 if n is even. theorem-:* Hence we have the following prime or II. The integers and Sn eitherare relatively THEOREM Dn 2. divisor havethegreatest common of the We shall now determine character Dn and Sn relativeto divisibilityby 2. From TheoremI it followsthat both of themare odd when a(3 is even. Hence we have to treatfurther onlythe case whenad is odd. as into This willseparatefurther two cases according a + ( is odd or even. the formula We startfrom recurrence

)D

-+2-(a

+f3)Dn+l

+ a(Dn

= 0,
= O0

Sn+2 - (a + (3)Sn+l + a(S,.

for which are readilyverified substituting Dk and Sk, k = n, n + 1, by n + 2, theirvalues in termsof a and (3. Since forthe presentdiscussion a(3 is odd, we have from(14) or
Dn+2 -Dn
Sn+2

Sn mod 2
Sn+1

as according a + ( is even or odd.

Dn+2-Dn+1 + Dn,

Sn+2

+ Sn mod 2

* Lucas (1.c., p. 200) statesinaccurately D. and S. are relatively prime. that

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

37

Now D1 = 1 and D2 = a + g. Hence fromthe above congruences whichinvolveDn we see readilythat whena + ,3is even Dn is even or odd according n is even or odd; and that when a + f is odd, Dn is even or as odd according n is or is not a multiple 3. as of We treat the numberSn in a similarmanner. We have

Si = at+t,

S2 =

a2+f2 = (a+f)2

- 2af.

Hence, if a + ,3is odd both S1 and S2 are odd; and if a + fiis even both fromthe above congruences, involving Sn Si and S2 are even. Therefore we concludereadilythat if a + g is even Sn is even forall values of n; and thatifa + g is odd Snis evenor odd according n is oris nota multiple as of 3. theorem: Collectingtheseresultswe have the following THEOREM III. If aOsis evenboth and Sn are odd. If ao3 is odd and Dn a + f3 even, is then is even all values n while nis even oddaccording for of D or S. as n is evenor odd. If both and a + FIare odd then and S are both Dn aod evenor both odd according n is or is nota multiple 3. as of From the properties symmetric of functions the rootsof an algebraic of of equation and the algebraicdivisibility Dn by D, when v is a divisorof n, it followsimmediately that the integerD. is divisibleby the integer D. when v is a divisorof n. This is also an immediateconsequenceof equation (7); and the latterequationin generalstatesmorethan this,that is, it gives a partialfactorization the integer of Dn/Dv. Thus we have the theorem: following THEOREM IV. If v is a divisorof n thenD, is a divisorof D,, and we have
Dn =

11F

g),

k all where ranges over those divisors n which notat the of are sametime divisors For v = 1 this theorem of givesa partialfactorization Dn, sinceD1= 1. In the precedingsection we proved that the quantitiesFk(a, 43) have values. integer theorem By the aid ofequation (13) thefollowing maybe demonstrated: THEOREMV. If v is a divisorof n such thatn/vis odd thenSn is divisible byS. and we have
S= of P.

Fk(a, 4),

k 2 where runsover those all contain to thesamepower as divisors 2n which of 2 2n itself do and which notdivide v.

38 From the identity

R. D. CARMICHAEL.

An) (am +

Am) = 2anfln(am-n

3m-n),

m > n,

we have readily
(15) DmSn
-

DnSm = 2an/3nDm-n.

From thisequationand the factthat Dmand Dn are primeto a13it follows that every commonodd divisorof Dm and Dn is also a divisorof Dn; whencewe concludereadilythat everycommonodd divisorof Dm and Dn is a divisorof D, where v is the greatestcommondivisorof m and n. But accordingto TheoremIV D, is a divisorof Dm and Dn. Hence the greatestcommondivisorof Dm and Dn is D, providedthat eitherDn/Dy or Dn/D, is odd. This latterfactwe shall now proveby aid of Theorems I and III. We have
Dm am

D~

a~-3~

O m3m am/v
-

am/v

by if we replacea", #Iv a-,1. The last memberof the above equation we denote by Dmv. We defineD-,,Iin a similar manner. It followsfrom prime. They are both difare TheoremI that al03' and a" + 13v relatively both primeintegers That is, aB and a + a are relatively from zero. ferent TheoremIII to fromzero. Hence wp may apply of whichare different is are and DmI, D,/I. If a-3is evenbothofthesenumbers odd. If a-f odd and or and DnV is odd; foreither m/v n/v a + 1 is even one ofthe numbers DmIV if commondivisorof m and n. Likewise, ad is odd, since v is the greatest and DnyIis odd; for and a + a are both odd thenone of the numbers D).,, eitherm/v or n/vis not divisible by 3, since v is the greatestcommon factor2. have not the common divisorof m and n. Hence Dai, and Dn/y that D.1, = Din/D and Dn/, = Dn/Dy and makinguse of Remembering we the resultsof the last two paragraphs have the theorem:* v of divisor DA and Dn iS D, where common THEOREM VI. The greatest divisor m and n. of common is thegreatest corollary: Since D1 = 1 we have at once the following whenm and n prime Dm COROLLARY. The integers and Dn are relatively prime. are relatively The example S6(2, 1) = 26 + 1 = 5.13,
S4

= 24 + 1 = 17,

S2

= 22 + 1=5

divisorofSm and Sn is not always common showsat once that the greatest
* The partof thistheorem of appliesto the odd divisors Dmand D. is due to Lucas which (1.c., p. 206).

ON THE NUMERICAL FACTORS OF THE ARITHMETIC FORMS.

39

m/v S, where v is the greatestcommondivisorof m and n. If, however, and n/v are both odd this simplelaw obtains,as we now show. In this from TheoremV that S. is a commondivisorof Smand Sn. case it follows Now and
= D22m SmDm D2n = SnDn,

divisor common VI we whence concludeby aid ofTheorem thatthegreatest of Sm and Sn is a factorof D2,. Now
D2v =

SvDv

and hence we have only to examinewhat factors has in commonwith D, Sm and Sn. Now D, is a factorof D, and Dm and Sm have the greatest divisor1 or 2. Hence D. has withSmand Sn thegreatestcommon common divisorS, Sm divisor1 or 2. Therefore and Sn have the greatestcommon we or 2S,; and in the next two paragraphs show that the lattercase does not arise. is To prove that the greatest commondivisorunderconsideration not This follows or to 2S, it is sufficient show that either Sm/Sv Sn/S,is odd. at once from TheoremIII if a3 is even; forthenSmand Sn are odd. In general
S'
_

am + 3M
all + TV1

Sv.

-a

anIv + X1/' ~
+

S,,, in a similarway. Then TheoremIII is applicable to S,/vand Snt, Now eitherm/vor n/vis primeto 3, and hence one of the numbersS./ and Sn&v odd if a- and a + B are both odd, that is, if a3 and a + 3 are is and Sm/Sv Sn/Sv both odd. In thiscase, then,one at least of the numbers is odd. Let us next considerthe case in whichaj3 is odd and a + ,3 is even; of say thata + $ is an odd multiple 2k. Then,since and
S, = a+3
S2 = a2 + /2 = (a +
p)2 -

and define if a, = a and B = B. Denote the last numeratorabove by Sm./

2a3,:

it is easy to see that S, and S2 are odd multiples of 2k and 2 respectively.

(14) one sees that in generalSn formula By means of the secondrecursion is an odd multiple 2k or of 2 accordingas n is odd or even. Hence in of this case Sm/S and Sn/Sv are both odd, since m and v and likewise n and v are both odd or both even. theorem: Thus we have the following

40 THEOREM VII.

R. D. CARMICHAEL.

divisorof m and n, and common If v is the greatest of divisor Smand Sn is S. common the odd,then greatest and n/vare both m/v namely: character, of theorem a different We turnnow to an interesting d, integer different that whichhavetheproperty any positive integers positive of fromunity,whichis a factorof (just) t integers thesecondset is also a the set; of first then number of factor at leastt integers the
D1m* Dfl2 .
Dni
-Dn2

THEOREM VIII.

Let ml,

m2,

*..,

m8

and ni, n2,

*..,

n, be two sets of

n,

is an integer. of is consequence the (partial) factorization This theorem an immediate of D, givenin equation (5). of terms thesequence of COROLLARYI. The product any n consecutive ... is divisible theproduct the n of first terms.* by D1, D2, D32
COROLLARY II.

*Ae

Dn,

The number D1D2

...
*.*

Dnl~n2+ Dn2)
...

(D1D2

*..

Dn) (D1D2

+nk (D1D2

***

Dn)

is an integer. coefficient that the polynomial This resultis analogous to the theorem

(n, +

is an integer. and suppose primepositiveintegers Let m and n be any two relatively of d that the positiveinteger (d $ 1) is a divisorof s integers the set 1, 2, In view ofthis of of at least s + t integers the set 1, 2, * * *, m + n -1. corollary: factTheoremVIII yieldsthe further prime positiveintegers, III. If m and n are any tworelatively COROLLARY the then number
D1D2
...

! n i~n2! ..no!

n2 +

...

nk)!

*.. , m and of t integersof the set 1, 2,

* * *,n.

Then d is obviously a divisor

is an integer. is This theorem analogousto that whichassertsthat

(D1D2

Dm+ni Dm)(DID2 ...

...

Dn)

m! n!

thatm and n are relatively prime. is an integer, provided

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

41

which Similarlyone may prove an extendedanalogue of the theorem statesthat .. (kMk) (km,)! (kM2) ! k 2
ml! M2! .. *mk! (ml + m2 + * +m)!' k>2

namely: is an integer, COROLLARY IV. The number

(DlD2 ...
...

Dml)k1

Dk?nl) (DlD2 ... (D1D2

...

...* Dm)k

D;km2)..(DlD2
(DlD2
...

..Dkm,)
Dml+m,+...+mk)

is an integer. of Justas equation (5) was used in the demonstration TheoremVIII theorem: we may employequation (11) to provethe following Let ml, M2, *.., m8 and ni, n2, *... n, be twosets of THEOREM IX. d of is integer which a factor (just) t such thatevery positive integers positive is of thenumbers n2, ** , n, withodd quotient also a factorof at leastt ni, odd quotient. Then thenumber m8 with ofthenumbers i2 ml,
**,

Sm<

Sm,2

is an integer.

1 Sn

&, Snr * .

* e e e

Sm.

Sn,

it If m is any integer and q is any odd prime, is obviousthat thereexist integers q- 1

of terms thesequence COROLLARY. The productofany 2n - 1 consecutive ... n terms. is divisible theproduct the of first Si, S3, S5, by

on dependent q alone, such that

_mq

(am _ am) q + alam om(Oem

om) q-2 +

+
*

a2l2mfl2m(am +

_ Om) q4
-

whence
(16) Drnq = (a
j3)

aga8mI3sm(am

r);

-lD

a,(&

f3) +aaqm:mDmD - +

...

of Let us evaluate a8. Since it is independent a, ,3and m, we may choose any convenientvalues for these numbers. Then put m = 1, f = 1, a = r + 1, where is a positive r to integer be chosenat convenience. Then from(16) we have 1 (r + 1)q (r~ =a8(r+ r)amodr.
-

If we suppose r to be a primenumberdifferent fromq we see that a. is that a. is divisibleby q but not divisibleby r. If we put r = q2 it follows not by q2. Hence a8 = q.

42

R. D. CARMICHAEL.

Supposenow that Dmis divisibleby p', X * 0, and by no higherpower thenfrom (16), sincea. = q, we have number; ofp, p beinga prime

(17)

Dmq

mod p3. qaJmI:mDm

it From this congruence followsthat pA+l is the highestpowerof p conpowerof tainedin Dmp, providedthat p is odd, and that pAis the highest in from p. We enquire p contained Dmqwhenq is an odd primedifferent What is the highestpower of p containedin D2m? We have further: III we have seenthatDmand Smhave no common D2m = DmSm. In Theorem from unity). Hence, if p is an odd primethe highest odd factor(different in by powerof p contained D2m is pA. If p is even,so thatDmis divisible 2, from from by TheoremIII thatSm is divisible 2. Then it follows it follows 2. Hence in factor common TheoremII that Dmand Sm have the highest this case D2m contains2A+1; and it containsno higherpower of 2 unless
X = 1.

theorem: These resultslead to the following of power a primep X. If forX > 0, pA $ 2, pA is thehighest THEOREM in in powerof p contained Dmpa is pa+A, . contained Dm thenthehighest prime to p. If pA = 2, thenDm,,2a containsthefactor beingany number of 2a+1 and Dmn an oddmultiple 2.* is Suppose that Sm is divisibleby pA, X > 0, but by no higherpowerof the odd primep. Then D2m contains pA and no higher power of p, since
D2m

= DmSm

according and Dmand Sm have no commonodd primefactor. Therefore, to the preceding theorem, D2m.,,p, or Dmpa*S.,.p-yA being prime to p, contains pa+A and no higher power of p. Moreover Dm.apaand Smupa contains do not have a factor in common. Hence one of thesenumbers p pa+kand no higherpowerof p while the otheris pre to p. Since D2m is a divisorof DmApif ji is even, we see that Dmnpacontains pa+A when ,u of is even. When,uis odd Sm is a factor Smpaand hence in this case Smpa theorem: Thus we have the following XI. If pA, X > 0, is the highest power of an odd prime p THEOREM Dmpa is divisible to in contained Smand ,uis a number if prime p; then Ais even is of power p and SmA.pa primetop, whileif A is odd bypa+A and byno higher of to power p. by p DMA, is prime p and Smu pais divisible pa+)A and byno higher
* The specialcase ofthistheorem which = 1 is givenby Lucas (1.c., p. 210), but Lucas in A of character the case whenpA= 2. failed noticetheexceptional to

contains the factor pa+A.

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

43

3. On the Appearanceof a Given Prime Factor in the Sequence D1, D2, D3, in of If it is knownthat a primenumber is a factor D, theorems the p In intoDm#Lp- the present sectionenable us to say howp enters preceding sectionwe show that any givenprimep, whichis not a factorof ao3,is a number the sequenceD1, D2, D3, * .; we also of factor a certaindefinite of carryout otherrelatedinvestigations. We have need of two lemmas,as follows: function of symmetric LEMMA I. If S(aP, ,3P) is any rationalintegral then integral APT j3P with coefficients,
S(aP, BP) S(a, A) mod p,

p beinga primenumber. it that The proofis not difficult.From Fermat'stheorem follows (18) aCOOPaCOmod p, (a+fl)P- =a+
(a +) )P

sinceca3is an integer. Likewise modp. we But by the aid of the binomialformula see that
acP +tP3modp,

since the binomialcoefficients the primeexponentp are all multiples for clearlyp timesa polynomial of p and (a + ,3)P- (acP+ iP) is therefore that in whichis symmetric a, ,3and has integralcoefficients; is, (a + 3)P - (aP + BP3) p timesan integer. Hence is
(19) aP + foP _ a +f mod p.

,P are rootsof the equation But, since ae and

3P)X +

apfp = 0,

of of functions the rootsof an of it is a consequence the theory symmetric in can be expressed the form algebraicequation that S(aP, Op)
S(aP, (P)
=

P(aP

(P", a<pp)

From coefficients. in whereP is a polynomial aP + (3P,aP"(Pwithintegral that (18) and (19) it follows But
P(caP + P3, a"P(P)

_ P(a + (, a() mod p.

P(a + 3, aC) = S(a, ()

44

R. D. CARMICHAEL.

and therefore

S(aog,,3P) -S(au, ) mod p, as was to be proved. of we and If m is any integer q is an odd prime, have an identity theform
(am
-

fm)Q = (am

13qm)- qalmlm(amn(q-2) 3)-D q = Dmq +

13m(q-2)) +

that whenceit follows

qI,

whereI is an integer. Hence Hence, II. LEMMA

we and If m is any integer q is any odd prime, have

In particular,
D =- (a

(a-(

13) 'Dm mod q.

) q-lDqa-

3)a(

q-l)Dj mod q.

Hence, since D1 = 1, it followsthat D a is divisibleby q when and only when (ca - 3)2 is divisible by q. the divisibilityof concerning Theorem III gives exact information of the Dn and Sn by 2. We shall now consider questionofthe entrance an from TheoremI that odd primefactorq. If q is a factorof ao3it follows of it does notdivideeither orS,. If it is a factor (a - 1)2 thenit divides DA we as we readilysee fromLemma II. In what follows shall consider D, by an odd primep whichis not a divisorof of the divisibility Dn and Sn
either (a _

If in equation(15) we put m = p and n = 1 we have

/3)2

or a13.

or

D1S,
-Sp

= 2aoD3pa4, = 2aceDp-.

(a + j3)Dp
Dp =- (a
Sp --a

that From LemmaII it follows

Lemma I that and from

mod p,

+ 13 mod p.

the Hence from last equationwe have

1)P-1 -

(a + 1)

2a1Dp~1 mod p.

Now (a _ that

13)2

Fermat'stheorem from it and therefore follows is an integer;

1 mod p.

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

45

Hence fromthe above congruence have the two cases we D i_ O mod p if (a- 3)P-l _ 1 mod p, that Now it is easy to verify + Dpsl -(ax + O3)Dp a0lDj and hencewe see that D,+ =_Omod p if (a- 3)P-1 Therefore have the following we theorem:*
a0D =_i
-

(a + A) mod p

if (a-

O)P-'=-1

mod p.

= -1

; mod p.

Obviously,if a - 3 is an integer(that is, if a and /3are integers)we have always that D,1 is divisibleby p. X of By meansofTheorems and XII we are nowto provea result fundawe mentalimportance. In orderto be able to state this resultsuccinctly below. It shall employa number-theory function X,.(n) whichwe define is convenient the same time to define secondfunction a whichis at (op,(n) intimately relatedto X,.(n). that is, let r and s be the roots Let rs and r + s be any two integers; of any quadraticequation of the form
.X2-ux + V = 0

THEOREM XII. An odd prime p which does not divide either (a - 3)2 or aof is a factor of D 1 or of D,+1 accordingas (a - (3) 1 is congruent to + 1 or to - 1 modulo p.

whereu and v are integers. When p is an odd primewe define symbol the (I ) by the congruence
(r s) P (1 8) )

modp,

it being understoodthat (

is the residue of least absolute value;

whence (rps) = 0, + 1, or-1 accordingas (r - 8)2 is divisibleby p, is a quadraticresidueofp, or is a quadraticnon-residue p. The symbol of (rY 8) is definedthus:

( ') = 1,ifrsis even; ( ,2s) = 0, ifrs is odd and r +

s is even;

( ')

= -1, ifrsandr + s areboth odd.

* Thistheorem due to Lucas (1.c., pp. 290,296,297). Lucas's proof, is is however, different from thatabove.

46

R. D. CARMICHAEL.

Then if

n
*--,

paP

al

.a.

pak,

where P2, pi,

by the equation

pk

are thedifferent prime factors n, we define of prs(n)

(n)

fjpiaii

[pi

(r's)]

by is This function similarto one introduced Lucas, 1. c., p. 300. It is, however,somewhatmore general. For r = 2 and s = 1 we have
(P21(n)

= sp (n),

introduced Lucas by of where<(n) is Euler's so-function n. The function as property includingthe p-function a of does not have this interesting special case. to multiple value Xrs(n) is defined be the least common The functional of the numbers

[P (pi)],
-

1 i=1,2,

,k.

It is obviousthat X,.(n) is a divisorof p,8(n). but properties; (rs(n) and X,,(n)have severalimportant The functions place to develop themin full. this is not an appropriate to theorem be provedmay now be stated as follows: The fundamental n, XIII. If thenumber THEOREM n where P2, P11 we have
*

P laP2a2

. ..

P kak,

P are thedifferent factors n, is primetoaofand if of prime i,

DA--0 mod n. to it To provethistheorem is sufficient showthatDAcontainsthe factor wherei is any numberof the set 1, 2, *--, k. This followsat once piai of from previousresults. For, X is a multiple ti,
= ti pi[p-

)1

=pi-1ki,

Lemma II say. From TheoremsXII and III and the remarkfollowing we see that Dk, is in every case divisibleby pi; and hence fromX that DA is divisible piai. by COROLLARY.* If (p = (pa (n), then Do e 0 mod n.
* This corollary essentially same as a certain resultdue to Lucas, 1. c., fundamental the is accurate. is of be thatLucas's statement thistheorem notentirely p. 300. It should noted

ON THE NUMERICAL

FACTORS OF THE ARITHMETIC

FORMS.

47

In connection with these simple theoremsconcerning the divisorsof in the numbers the sequenceD1, D2, ***itshouldbe noticedthat no laws of corresponding obtain in the case of the sequenceSi, S2, simplicity We have seen that an odd primep whichdoes not divide either(a - p3)2 or ad is a factorof D,, or of D,+i. But in the case of the sequence it oftenhappens that a given prime numberis not a factor Si, S2, of any term. Thus 7 is not a factor of Sn(2, 1), _ 2" + 1, for any value of n. More generally, suppose that Dk, where k is odd, has an odd prime factorp while p is not a divisorof any D, for v less than k. FromTheoremVI it follows that Dmis divisibleby p whenand onlywhen m is a multiple k. If we supposethat p is a divisorof S, forany given of value of n we shall be led to a contradiction. For, sinceD2n= DnSn,D2n
...

n is a multipleof k. Therefore is divisibleby p; and Dn and Sn have Dn

is divisible by p; and therefore is a multiple of k. But k is odd, and hence 2n

the common odd prime factorp, which is impossible. Hence, an odd prime numberp which divides Dk, where k is odd, and does not divtide any D, for v less than k, is not a factorof any Sn. 4. On the Numerical Factors of the Forms Fk(cx, A).

We have already seen that the numbers Fk(a, ,3) are of fundamental importance in the factorization of Dn and Sno We turn thereforeto a detailed treatment of these numbers. Let us suppose that v> F,(a, 3)Omodp, and that v is not a multiple of the prime number p. subscript for which O mod p. Fk(a,/) Suppose that k is a

Now* F. and Fk are divisors of D. and Dk respectively,while the greatest common divisor of D, and Dk is Ds, where 8 is the greatest common divisor of v and k. If we suppose that a is different from v we shall be led to a contradiction; for,F, is then a factor of D,/Ds, as we see from (5), whereas from Theorem X it follows that Dl/Ds is not divisible by p since p is a factorof Ds and v/6is prime to p. Hence 8 = v; and therefore is a k multiple of v. We shall now show that FPa(a, A),a > 0, is divisible by p but not by p2, except that when p = 2, v = 3, F6 may be divisible by 22. [From Theorem III it follows that F6 is divisible by 2.] If we suppose that we do not have simultaneously p = 2, v = 3, a = 1, we may proceed as follows: From
* Whenno confusion arisewe sometimes can write forF, (a, Al). F,

48
TheoremIV we have

R. D. CARMICHAEL.

Da=
D pa-i

7Fi(a, A),

where i ranges over those divisorsof ypa which contain the factorpa. X of member thisequationis divisible FromTheorem it follows thatthefirst Fi(a, d) ofthesecond by p but notby p2. Hence (only) one ofthe numbers is member divisibleby p and it is not divisibleby p2. Suppose that this the of is number thatforwhichi = k. Then k is a multiple pa. But from discussionin the precedingparagraphwe see that k is a multipleof P. multiple v and pa occurring of Hence k = vpa, sincethisis the onlycommon in of as a subscript the secondnumber our equation. Fromthiswe concludethat each of the numbers Fp, FVp * contains p the factor but that no one of themcontainsp2, exceptthat whenp = 2, 22. P = 3, F6 may contain Now considerthe numberF,11Pa,whereA is greaterthan unityand is that the X and primeto p. It is a divisorof DVXp-/DVPa; from it follows is latternumber not divisibleby p. Hence FVEZPa primeto p. is _ Let us suppose that F12= (a - )2, is divisibleby the odd primep. Lemma II we see that each of the numbers From the remarkfollowing we argument may is divisibleby p. Justas in the preceding Fp, F,2, is divisibleby p2, and that show that no one of the numbers Fp2,Fp3, than 1 and is primeto p and a > 0. Fla is not divisibleby p if,uis greater The example
... ...

1+ i.6,

= 1- 16,

(a - ,)2 = 24,

F3 = a2 + a4+12 =

by showsthatF12may be divisible p whileFp is at the same timedivisible F., p2. If ji is greater than 1 and is primeto p and iffurther is divisible by by by p, we see at once thatD,, and Dp are both divisible p -contrary to the corollary TheoremVI, whichassertsthat D,, and Dp are relatively to by prime. Hence FA is not divisible p. primesince /iand p are relatively Now supposethat F12is divisibleby 2. Then, since
F12 = (a
-

1)2 =

(a

1)2

4aO

it follows that a + 13 divisibleby 2. That is, F2 is divisibleby 2. The is examplea = 2k + 1, 13= 2- - 1 shows that F2 may be divisibleby any powerof 2 whatever. By means of the relation
F2a

= a2"2

12a1

(a2a2 +

2a-2)2

2a2G212-

it may be proved,however, that F2a,a > 1, is divisibleby 2 but not by 22.