On Two Conjectures of P. Chowla and S. Chowla Concerning Continued Fractions. A. S c n x ~ z ~

(Warszawa)

To Professor Beniamino S:EGRE on his 70-th birthday.

- The alternating sum of the partial quotients in the primitive period of a continued fraction expansion of ~/D is determined rood 2 and mod 3.

Summary.

L e t D be a non-square positive integer a n d set

1t 11 ~ . ~ = bo + ~ + ... + ~ =

[bo, b~, ..., b~],

where the b a r denotes the p r i m i t i v e period~ Z D = b~-- b~-i + . . . + (-- 1)k-lbl. P. C~OWL_~ and S. C~OWL=A.[1] h a v e m a d e a m o n g others the following' conjectures: if D ~ 3

rood 4, 3~/D t h e n Z"D ~ 0 m o d 3,

if p, q ure p r i m e s ; p ~ 3 m o d 4, q_----5 rood 8 t h e n

The a i m of this p a p e r is to p r o v e two t h e o r e m s which generalize the a b o v e conjectures (Note t h a t D ~ 3 rood 4 implies k ~ 0 rood 2). TtI~:o~Eg 1. - I f k is even, 3 ~ D t h e n Z'~ ~ 0 m o d 3. TH~OR~g 2 . - Z'D ~ V m o d 2, where u, v is the least non-trivial solution of U " - - D V 2 = 1. Moreover, le~ 2 ~ D , k(D) be the squarefree kernel of D and C a n y divisor of 2k(D) different f r o m i a n d ~ k(D) sueh t h a t U 2 - k ( D ) V ~ ~- (2 is soluble. I f either (2 ~ 1 rood 2 or each p r i m e f a e t o r of D divides k(D) t h e n Z'~ ~ C + 1 rood 2. (*) Pervenuto il 7 maggio 1973.

112

A. S0~IINZEL: 0 ~ two eonjeet~eres of P . Chowla and g. Chowla, etc.

lgr,~:. - I f b o t h c o n d i t i o n s g i v e n in T h e o r e m 2 for o d d D a r e v i o l a t e d t h e conclusion m a y fail, e.g. for D ---147 = 3 . 7 3 w e h a v e Z 9 = 1 6 ~ 0 m o d 2, a l t h o u g h u * - 3v ~ = - - 2 is soluble. C01~0LL_~!~Y 1.

-

-

I f D ~ 0, 3, 7 m o d 8 t h e n Z~ = 0 rood 2.

C o a o I m _ ~ Y 2. - I f p is a p r i m e , p ~ 3 COI~OLLII~Y 3.

-

-

m o d 4; ~ is o d d t h e n Z ~ - ~ - I

m o d 2.

I f p , q are p r i m e s , p ~ 3 rood 4, ~ -~ 5 m o d 8, e, fi are o d d t h e n

P r o o f is b a s e d on s e v e r a l k n o w n f a c t s f r o m t h e classical t h e o r y of c o n t i n u e d f r a c t i o n s w h i c h we q u o t e b e l o w in f o r m of l e m m a t a f r o m t h e b o o k of P ~ o ~ [4]. F i r s t h o w e v e r we m u s t recall P e r r o n ' s n o t a t i o n . F o r a g i v e n r e g a l a r c o n t i n u e d fract i o n [bo, b~, ..., b,] t h e Muir s y m b o l K b0, b~, b~, ..., b~ d e n o t e s its n u m e r a t o r A~, c o m p u t e d f r o m t h e f o r m u l a e A-i=-1,

Ao --~ bo ,

A = b A _ l + A _~ .

T h e n we set

L~iwi

A~,~= K

1, ... ~ 1 ) b~, b~+l, ..., b~+v '

B,.~ -- K

b~+l, b;.+~, ..., bz~

A,,0

'

1. - T h e following f o r m u l a e h o l d

(2)

B~.~. =A,_~a+~ ,

(3)

A,.~ = b~A,_i.~+ i + Bv_l,~.+i ,

(~t)

A,

X , a B , _ l . ; . - - A,_~,aB,, z = (-- 1) "-1 .

PlSOOP. - (1) follows d i r e c t l y f r o m t h e definition of A,. a. F o r t h e r e m a i n i n g f o r m u l a e see [4] p. 15, f o r m u l a e (25) a n d (29); p. 17, f o r m u l a (35).

A. SOI~I~ZEL: 0~ two eonjeetures o/ _P. Chowla and S. Chowla, etc.

113

2. - If for all positive ~ < k, b~ = be_s t h e n for all ~-<
LE~,

(5)

ak_~.~A = -fla.k_.~_l.). •

PROOF. - We have by definition ( 1,"',i ) B~_~,~.-- K b~+~, b~+~, ..., b~_~ '

A~_~_~.~ :

K

1,..., 1 ) b~_~_l

b~, b).+l, . . . ,

and the lemma follows from the s y m m e t r y property of the Muir symbol ([4] p. 12). LE~MA 3. - The symmetric part of the continued fraction ~o = [bo, bl, b2, ..., b~, b~, 2bo]

with period of length k being given, the necessary and sufficient condition for ~o to be a quadratic root of an integer is t h a t bo should have the form (6)

bo =

mA~_~,l-- (-- 1)~ A~_3.1Bk_~.I 2 '

where m is an integer. Then =

(--1) B~-3,1 •

PROOF. - See [4] p. 98, Satz 17. t)ROOF OF THEOlCE~ l. - If D ~ 0 mod 3 t h e n in the notation of L e m m a 3 (7)

mA~_2.x ~ A~_3.1A~_2,1 mod 3.

Indeed, this is clear if Ak_~,~~ 0 mod 3, otherwise we have

D -~ (--mA~_~.~ + Ak_3.~Bk_~,l)2 + mA~_3.~-- B~_~.I =~-- m 2-2mAk_2.1Al:_3.1B~_3n + A~_~,IB~-~.~ ~ ~ + mA~_~n-- B~-3,~ ~"

and since b y (~) and (5) for ~ = 1 , v = k - - 2 . a Ak_~. 1 B~-3.1 __ - - Ak-3.1

1

it follows D~

m2--1

if A,-3.1 ~ 0 m o d 3 ,

m ~ + mA,_s.1

if Ak_3.1 ~ 0 m o d 3 .

Thus DA~_2.1 ~ 0 mod 3 implies m ~ Ak_3.1 mod 3 and a ]ortiori the congruence (7). 8 - Annali di Matematica

A. SCKLNZEL: On two conjectures of P. Chowla and S. Chowla, etc.

11~ Since

XD = 2bo--2b~ + ... + (-- 1)~/~-~2b~/~_x + (--1)~/~b~, in view of (6) and (7) it remains to show t h a t (8)

½A~_~.~(A~,_;:.~--B~_~,~)~-- b~--b~ + ... + (-- 1 ) ~ b ~ _ ~ + ( ~ l ) ~ b ~

mod3.

This we prove b y induction with respect to k. F o r k = 2 A~_3.~ = 1 ~

B~_~,~= 0 ,

A~:_~.~= bl

and (8) takes the form - - b l ~ - - b l nlod 3. Assume (8) is true for any symmetric sequence of positive integers bl, ..., bk_3 (]~ even >4). We have b y (1), (3) and (5)

A~_~.~ = b~A~_,., + B ~ . ~ = b~A~_~,2 -}- A~_~,, , A~_.,x = b~_~A~_a,~ + A~_~.~ = b~(b~A~_a,~ + A~_~,~) + b~A~,_~,~ + B~_~ = = b~~A ~_~ + 2b~A~_~,~ + B~_~.~; b y (2) B~_~,~-----A~,_~. Hence

=

A~-5,2)(blA~-4,~ + 2blAb,_5,2 + Bk-5,~-- A7~-~,1)

b~(A~_a,~B~_~, + A~._~,~) + A~_~,~(A~_~,4- B~_~.~) rood 3. However, b y (4) and (5)

bl(-- A~._,,,.Bk_5,2 + A~_~.~) ~ ~ bl(-- 1) ~-* ~ bl , b y the inductive assumption applied to the sequence b2, ..., bk_.o

AT~_5(Ak_,,~- BT~_~,~,)~ 2 ( b ~ - b3 + ...) ~ -

b2 + b s - ... + (--1)~"* bk~2rood3

and (8) follows. L~_,~-~[_x 4. - If ~/D = [bo, bl, . . . , b,_ 1 , ~v] t h e n

~ =

QV

where P~, Q, are positive integers (9)

D-P~+~=Q~Q~+~

A. SOItI~'ZEL: 0 ~ two conjectures o/ P. Chowla a,~d S. Chowla, ere.

115

and for v = 1 , ..., k - - i 2
(10)

P~OOF. - See [4] p. 83, formula (5); p. 33, formulae (4), (5). LEPTA 5.

-

I f k is even, k = 2 r t h e n

(11)

2Pr = b,Qr ,

(12)

2A,_~ = (B,_~b, + 2B,_~)Q, ,

B~,_I -~ B,_~(B,_lb, + 2B,_~) ,

Q, is a divisor of (2A,_~, 2D) and

(13)

~, Q, ]

-¢/-2B,_1= (-1),4.

PR00F. - See [4] p. 107, formulae (9) and (10); p. 115, the third formula from below. L E ~ I 6. - If D is square-free there are e x a c t l y two values of C which divide 2D such t h a t C=/:I, ~ D and U ~ - - D V ~ = C is soluble. The p r o d u c t of these two values of C equals - - 4D when D is odd and C is even, in all o t h e r cases the p r o d u c t equals - - D. P~00F. - See [3] p. 12, T h e o r e m 11 p a r t 3. PBOO~ oF T~E01~:E)[ 2. - I f k is odd t h e n U ~ - - D V ~ - ~ - - I is soluble, v ~ 0 C~lmod2. On the other h a n d Z D = 2 b o thus 2:D ~ v ~ C + I rood2. If k is even 2, k = 2 r t h e n

and

Z'm = 2be-- 2bl + . . . + (-- 1),- 12b,_~ + (-- 1)'b, ~ b, rood 2 . We have clearly V = B 2 r _ 1 ailed We first prove b, ~-B2,_~ meal 2. Indeed, if b , ~ 0 we have B~,_x~-0 b y (12~). If b , ~ l then b y (11) Q , ~ O . If we had Br_~ ~-~0, (121) would give 2A,_I/Q, ~ 0 and the left hand side of (13) would be divisible b y 8. Therefore, B,_I-~ 1 and b y (12~) B2,_, ~_b,. W e now a~sume t h a t D is odd. I f Q, ~ 0 rood 2 t h e n b y (9) applied for v = r - - 1 it follows t h a t P~ ~ 1 m o d 2 and b y (11) b ~ l rood 2. I f Q ~ I then b , ~ 0 . Thus

(14)

X~-Q~+

1 rood2.

L e t Q,-~q~k(Q~). B y L e m m a 5 Q, I2D hence q is odd, k(Q,)t2k(D). B y (13)

(A,-~lq) ~

(D/q2!B~ = (-- 1)'k(Q,) ,

A. SCmENZEL: O~ tWO conjectures o/ P. Chowla and S. (Thowla, etc.

116

thus U'--k(D)V~-~(--1)'k(Q,) is soluble. possibilities

(15) (16)

B y L e m m a 6 we h a v e t h e following

(-- 1)'k(Q,) = 1, (-- 1),k(Q,) = - k(D),

(-

1),~(Q,)

=

(7, - - k(D)(7-~

(-- 1),k(Q,) ----

4k(D)

C -~

if ( 7 ~ 1 r o o d 2 , if C ~ 0

mod2.

If (7 ~ 1 rood 2 t h e n

Q~=- k(Q,) -~ (7 mod 2 .

(17)

If e~ch prime factor of D divides k(D) t h e n (15) and (16) are impossible. I n d e e d each odd prime factor of Q~ divides k(D) hence if Q, : q ~ it divides also D/Q~. I n view of (13) this implies Q, = 1 , c o n t r a r y to (10). Also each odd prime factor of 2D/Q, divides k(D) hence if Q, = q2k(D) it divides also Q,. I n view of (13) this implies Q , - ~ D >2bo again c o n t r a r y to (10). Since

(7 ~-

-- k(D) C-~ rood 2

if C - ~ I r o o d 2 ,

4k(D) C-1 mod 2

if C ~ - 0 r o o d 2 ,

we obtain again the congruence (17). The t h e o r e m follows from (14) and (17). PROOF

plies v ~ 0

If D ~ 0 , 3 , 7 mod 2 thus ! D ~ v ~ 0 mod 2.

OF C O R O L L A R Y 1 . -

mod 8 then u ~ - - D v ' ~ l

mod 8 im-

PROOF OF COROLL~,~Y 2. - I f D : p ~ where p is a prime, p ~ 3 mod 4, ~------1 mod 2 t h e n each prime factor of D divides k(D) ~-p. The only divisors of 2p besides 1 and - - p are - - 1 , ± 2 , p and ± 2 p . I t o w e v e r the equations

U2--pV 2 ~--I,

U~--pV~-~p

~re impossible mod p and p~, respectively, because (--I/p) =--i. Thus C = ~ 2 or -F2p and 2:1)-- C ÷ 1 --~ 1 mod 2. P a o o r oF C0~OLL~Y 3. -- If D =p~q~ where p, q are primes, p ~ 3 mod 4, q ~ 5 rood 8, ~ ~ fi ~ 1 m o d 2 t h e n each prime factor of D divides k(D) =pq. The only divisors of 2pq besides 1 a n d - - p q a r e - - 1 , ± 2 , ± p , =k2p, q-q, :k2q, pq, =k2pq. The equations

U2--pqV 2 = - - 1 ,

U~--pqV ~= p q

are impossible mod p and p2, respectively, because ( - - l / p ) = - - 1 .

A. SCHI~ZEL: On two conjectures o/ P. Chowla and S. Chowla, ely.

117

The equations

U*--P¢V ~--- :i: 2 ,

U~--Pq V*-~ i 2pq

are impossible rood q and q~, respectively, because (~-2/~/)~---1. I f ( p / q ) : 1 the equations

Us - p q V ~ -

-4- 2p ,

U~--pqV~-~ ~ 2q

are impossible rood q and q~, respectively, because (~: 2 p / q ) - ~ - - 1 . Then C - ~ 4 - p or :Lq and Z~-----C+I--~0 m o d 2 . I f ( p / q ) = - - 1 the equations

U2--pqV~:Ip,

U~--pqV~=~:q

are impossible rood q and q~, respectively. Then C - ~ i 2 p or :t:2q and 2 7 ~ C ~ 1 - - - - - 1

rood2.

RE~ARK. -- The congruence 27D~ v rood 2 has been suggested to me b y H. LANG, who established a similar congruence for the relevant Dedekind sums (see his forthcoming paper [2]).

REFERENCES [1] P. CHOWLA - S. CHOWLA, Some properties o] periodic simple continued ]raetions, Proc. Nat. Acad. Sci. USA, 69 (1972), pp. 37-45. [2] I-I. LA~G, if bet die Klassenzahlen eines imagin~ren bizyklischen biquadratisehen Zahlk5rpers und seines reellquadratisehen Teilk6rpers, J. Reine angew. Math., 262/263 (to appear). [3] T. NAG]~LL, Contributions to the theory o] a category o] diophantine equations o] the second degree with two unknowns, Nova Acta Regiae Soc. Sc. Upsaliensis, (4), 16 (1954), no. 2. [4] O. P~RRO~', Die Lehre yon den Kettenbri~ehen, 2 te Auflage, reprinted by Chelsea (New York).