关于n的平方和表示

关于n的平方和 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 The Hermite–Serret Algorithmand 122 332Alf van der Poorten Abstract. Musing on the cute observation that 122 332 1233 led me to remind myself of well known techniques for writing a given integer n as a sum of two squares given or having already found a square root z say of 1 modulo n. In brief one applies the Euclidean algorithm to n and z stopping ? at the rst pair x and y of remainders that are smaller than n. Then lo it happens that n x2 y 2 . Naturally square roots of 1 properly dierent from z lead to ent representations of n as sum of two squares. Obviously so simple an algorithm dier must have an elegant and near trivial explanation yet the literature contains some rather turgid proofs. I briey point out that in general a representation of n by a reduced denite binary quadratic form can readily be found by symmetric decomposition of a symmetric matrix a process well known as reduction and that this does give insight into why certain remainders in the Euclidean algorithm applied to n and some square root mod n yield the representation. My story is for our mild amusement and provides a nice and easily comprehended story to tell our students.1. 1233 and All ThatThe pleasing observation that 1233 122 332 apparently emanates from HendrikLenstra. It came to me by way of the text 1. Happily it is more than just anumerical curiosity being the augur of innitely many such cute decompositions.Lemma 1.1. The identity a2 b2 10u a b is equivalent to the representation102u 1 10u 2a2 2b 12 .Proof. Multiplying a2 b2 10u a b 0 by 4 and completing squares readilyyields 102u 4 10u a 4a2 4b2 4b 1 102u 1 . It’s enough therefore to look for representations of 102u 1 as a sum x2 y 2with x 10u 2a even and y 2b 1 odd.Example 1.2. Because 101 is prime its only representation as sum of squares is102 12 yielding a 0 and b 1 and so the boring decomposition 1 12 . However104 1 73 137 and so has a second potentially interesting decomposition givenby 82 32 42 112 8 11 3 42 8 4 3 112 762 652 . That is70 A. J. van der Poortena 12 and b 33 as in our motivating example. Similarly 106 1 101 9901yields the possibly interesting decomposition 106 1 9802 1992 . But that isa 10 and b 100 and provides only the quite dull 10100 102 1002 . It is easy to see that there are plenty of u so that 102u 1 has lots ofprime factors but it’s not entirely obvious that seemingly interesting sums ofsquares yield amusing decompositions. Indeed the example 1010 1 101 354127961 has an encouraging three prime factors but the 4 1 3 possibly amusingdecompositions are 2584043776 258402 437762 1765038125 176502 381252 which are pretty interesting but also the unacceptable 99009901 9902 099012 .In all the claim there are innitely many ‘cute’ decompositions is not totallyconvincing.Example 1.3. The following brief selection1 possibly is more compelling 1167882 3211682 116788321168 7681802 26630252 7681802663025 16754550882 37346219532 53.I take it as known that 2 and each prime p congruent to 1 modulo 4 has anessentially unique presentation as a sum of two positive integer squares. Then theidentity a2 b2 c2 d2 ad ? bc2 ac bd2 readily shows by inductionthat a product of s distinct odd primes ? 1 modulo 4 has 2s1 essentially dierentrepresentations as a sum of squares. However we had best rst discuss just how one nds the decomposition ofan integer as a sum of two squares.2. Representation of Integers in the Form ax2 2bxy cy 2It seems more convincing to discuss the more general problem of representation byarbitrary quadratic forms of negative discriminant. The matter of representationof integers by binary quadratic forms is one of the oldest problems of numbertheory. Of course the real issue is to explain just which integers are representedand why but it certainly is also of interest actually to nd representations.2.1. Symmetric Decomposition.My following remarks are a minor variant on known algorithms for determiningrepresentations by denite forms. The idea is conveniently illustrated by a toyexample. Consider the problem of nding nonnegative integers x and y so that 173 2x2 3y 2 .We rst solve the congruence z 2 ? 3 2 mod 173. Indeed 722 30 173 6.Accordingly we study the matrix 173 72 2 1 2 1 2 1 14 1 1 0 M . 72 30 1 0 1 0 1 0 1 0 0 61 From a complete list up to u 10 for which I thank Michael Volpato. Representation by Quadratic Forms 71Here I have eected the decomposition by the Euclidean algorithm on the rows ofM with the details given by the array 173 72 2 72 30 2 29 12 2 14 6 14 1 0 0 6Dually we might have performed the Euclidean algorithm on the columns of M obtaining 2 2 2 14 173 72 29 14 1 0 72 30 12 6 0 6This dual decomposition is particularly friendly to left-handed mathematicians.But it yields the transpose of the previous decomposition namely 173 72 1 0 14 1 2 1 2 1 2 1 M . 72 30 0 6 1 0 1 0 1 0 1 0Something is clearly wrong here. M is a symmetric matrix yet our methods ofdecomposition destroy that symmetry. So we try again working symmetricallyboth by row and by column. Our working begins with the two steps one rowoperation then one column operation 2 173 72 2 72 30 12 29 12 5reporting that 173 72 2 1 30 12 2 1 M . 72 30 1 0 12 5 1 0Ultimately we have 2 2 1 173 72 2 72 30 12 2 29 12 5 2 1 6 2 2 0 3 0 372 A. J. van der Poortenshowing that 173 72 2 1 2 1 1 1 2 0 1 1 2 1 2 1 M . 72 30 1 0 1 0 1 0 0 3 1 0 1 0 1 0The array 2 2 1 0 1 2 5 7 1 0 1 2 3details the computation 2 1 2 1 1 1 7 5 . 1 0 1 0 1 0 3 2So we have 173 72 7 5 2 0 7 3 M 72 30 3 2 0 3 5 2and indeed 2 72 3 52 173 .Principal Remark. Let m be a positive integer and suppose z 2 ? m mod n. zSet k z 2 m/n. Then symmetric decomposition of the symmetric matrix n k z x xyields a unimodular nonnegative integer matrix y y and integers a b and csatisfying 0 ? b lt a 0 ? b lt c and ac b m so that 2 n z x y a b x x M z k x y b c y yand plainly n ax2 2bxy cy 2 .Conversely every such representation of n is obtained by symmetric decompositionfrom a solution of z 2 ? m mod n.Proof. We perform the Euclidean algorithm on the rows of the matrix. That isthere is a greatest integer d possibly zero so that both n dz and z dk arenonnegative. Repeating the operation on the columns it suces to see we alreadyknow that z dk is positive and that because k n dz dz dk z dk2is m gt 0 it follows that also n dz dz dk must be positive. This leaves uswith a nonnegative symmetric integer matrix of positive determinant m on whichwe may repeat the symmetric decomposition. The process terminates if d is zerofor two consecutive steps or equivalently if z is less than both n and k. Conversely a representation of n yields both an ax by2 my 2 andcn bx cy2 mx2 vindicating the nal claim. Representation by Quadratic Forms 73To add conviction let me detail the case 83 2x2 2xy 3y 2 . Here m 5 and592 5 42 83. Indeed 1 2 1 83 59 1 59 42 17 2 24 17 7 3 1 8 3 2 1 4 1 3and the continued fraction 1 2 1 is 4/3 whilst 1 2 3/2. Hence 2 42 2 4 3 3 32 83 .2.2. Algorithmic Considerations.My apparent innovation though I do not claim any innovation at all is the idea ofsymmetric decomposition of symmetric integer matrices. Otherwise I hint at thewell known algorithm sometimes attributed to Cornacchia for example in the netext 1 and more conveniently at 2 ?1.5.2. My recollection is that an allusionto the contribution of Serret and Hermite might be more appropriate at any ratein the case m 1 of particular interest to us here. In that case thus the case of representation as a sum of two squares thesymmetric matrix M is unimodular and its symmetry is precisely the symmetryof the continued fraction expansion of n/z. In 8 H. J. S. Smith gives a niceproof that there is indeed a z so that p/z has a symmetric continued fractionexpansion whenever p is a prime ? 1 mod 4 we repeat that delightful story in3. The general algorithm is analysed in 4 this is also a good source for earlierreferences including those I do not detail above. However the reader will have noticed that the method sketched though nefor toy examples done by hand does not seem especially ecient. In particularrather than doing everything twice it is plainly preferable in the case m 1 justto perform the Euclidean algorithm on n and z. Then the pair of remainders x y ?rst both less than n yields x2 y 2 n. Theorem 2.1 shows that. For m gt 1it is less obvious just when to stop and exactly how to obtain x and y in termsof remainders appearing in the Euclidean algorithm. The cases b 0 are detailedin 4 and that readily generalises see for example 5. By the way although Isuppose the central coecient is even that’s no loss of generality. If that coecientis odd just consider representations of 2n by twice the given form. Knowledgeable readers will complain that my remarks miss the point. Thegame is precisely to formulate the stopping rules and the like that allow one toapply the Euclidean algorithm on n and z to nd a representation. For example in4 that’s in eect done for the case m f g and representations f x2 gy 2 by rstobtaining z so that z 2 m mod f n. One now applies the Euclidean algorithmto the pair of integers n and w z/f and x is the rst remainder less than n/f .74 A. J. van der PoortenWhatever my present remarks were in the rst instance only my personal attemptto recall why such techniques work at all. I was also amused to be remindedthat given a square root of m mod n one obtains a representation of n ofdiscriminant 4m without needing to know in advance just which representationof that discriminant it would turn out to be.3. A Curious Property of 17Of course I hide the real problem namely that of nding a square root of mmod n. Happily any factor n of 102u 1 obviously satises z 2 ? 1 mod n withz ? 10u mod n. Thus 108 1 17 5882353 leads us to compute 588 4 5882353 104 588 104 17 4 4 2353 4 1 0 1 0 1That is 5882353 104 5882 1 4 1 4 1 5882 1 104 17 1 0 1 0 1 0 1 0 2353 588 2353 4 . 4 1 588 1So 5882353 5882 23532 and we have chanced upon a cute decomposition It is now easy to conrm that each integer 1084u1 1/17 has as it werean automatic decomposition. The next is 353 82 532 .However the exponents 84u 1 are a little less automatic. The case u 1 yields 17648 588235294122 2352941176482 .Proposition 3.1. There are innitely many amusing decompositions.Proof. Each integer 1084u1 1/17 is represented by the sum of the squares of1044u1 4/17 and of 4 1044u1 1/17. The integers 1044u1 42 /17decompose as the sum of 1044u1 times a 1044u1 4/17 and of b 4a.The attentive reader will already have been hunting for other curious factors of102u 1. Those attentive readers will see readily that the said representationsare decompositions and the said decompositions yield representations as sums ofsquares. Is it that factors m2 1 are singular Try 10128 1/257. But I shouldn’tsay more lest I spoil the fun for readers with too much time on their hands. Representation by Quadratic Forms 754. RemarksThe educated reader will already have recognised that ‘symme.