The solutions are in! Last week’s POW-9 is a problem for which you need a bit of insight to solve at all (even with calculator or computer), and then a bit more to solve elegantly without machine aid.

Solution by Philipp Lampe, University of Bonn: The answer is n = 65536. The decimal expansion of 1/65537 is eventually periodic with (minimum) period length n. Suppose it takes the form

\displaystyle s \cdot 10^{-k} + t \cdot 10^{-(k+n)} + t \cdot 10^{-(k + 2n)} + t \cdot 10^{-(k + 3n)} + \ldots

\displaystyle = \frac{s}{10^k} + \frac{t}{10^k (10^n - 1)}

for integers 0 \leq s < 10^k and 0 \leq t < 10^n. Then 65537| 10^k (10^n - 1), and therefore 65537|10^n - 1; equivalently 10^n \equiv 1 \mod 65537. The minimum m such that 10^m \equiv 1 \mod 65537 (i.e., the order of 10 modulo 65537) must then divide n. On the other hand, from 65537u = 10^m - 1, we derive

\displaystyle \frac1{65537} = \frac{u}{10^m - 1} = \frac{u}{10^m} + \frac{u}{10^{2m}} + \ldots

Thus by minimality of n, we conclude m = n, and that the decimal expansion is periodic (not merely eventually periodic).

It is well known that p = 65537 = 2^{16} + 1 is prime (it is the largest known Fermat prime), so by Fermat’s little theorem, the order of 10 modulo p divides \phi(p) = p - 1 = 2^{16} (where \phi is the Euler phi-function), and so it must be a power of 2, at most 2^{16}. That the order is in fact 2^{16} can be checked either by brute force (by repeated squaring and reduction modulo 65537, best carried out with calculator or computer), or by the following number-theoretic argument.

Since p is prime, the multiplicative group of nonzero elements of the field \mathbb{Z}_p is cyclic (is generated by a single element, say a). Hence 10 \equiv a^i \mod p where 1 \leq i < 65536, and 10 itself is a generator (has order 65536) iff i is prime to 65536, i.e., iff i is odd. This occurs iff 10 is a non-square modulo p. Defining the Jacobi symbol by the usual formula

\displaystyle (\frac{a^i}{p}) = (-1)^i

(so that (\frac{x}{p}) = 1 iff x is a square modulo p), we have

\displaystyle (\frac{10}{p}) = (\frac{2}{p}) \cdot (\frac{5}{p})

The second factor is, by the law of quadratic reciprocity (and the fact p \equiv 1 \pmod 4),

\displaystyle (\frac{5}{p}) = (\frac{p}{5}) = (\frac{2}{5}) = -1.

Also, by the “second supplement“, we compute (\frac{2}{p}) = (-1)^{(p^2 - 1)/8} = 1. Hence (\frac{10}{p}) = -1: 10 is a non-square as desired. This completes the proof.

Remarks:The argument in the first paragraph of Philipp’s solution proves for 1/65537 a fact which holds generally for any reduced fraction 0 < q/p < 1 where p is prime to 10: that the decimal expansion is actually periodic, not just eventually periodic. Henry Wilton also took the time and trouble to argue this point. I’m not sure how widely known that is, so I was glad the point was made; of course the main thing we need from that paragraph is the general fact that the period length of q/p equals the order of 10 modulo p.

A number of solvers computed the order of 10 by brute force, which I accepted. The use of quadratic reciprocity is slick but gets into rather deeper waters. As the Wikipedia article explains, this law was known to (or at least conjectured by) Euler and Legendre, but resisted a complete proof until Gauss found one after an intensive effort; it was one of his proudest achievements, and a theorem he returned to over the decades, giving over half a dozen more proofs in his life. Now more than 200 proofs are known. One proof that I like was given by Zolotarev, which is given a nice account in an appendix to John Conway’s very entertaining book, The (Sensual) Quadratic Form. Arin Chaudhuri pointed out to me that it’s also given as an exercise in Knuth’s The Art of Computer Programming (Vol. I, p. 45, exercise 47).

The “second supplement” was, according to the Wikipedia article, first proved by Euler. Its use here can be circumvented by observing that 2 cannot have order p -1 = 65536 since already 2^{16} = -1 \mod p, so that by Lampe’s argument, 2 is a square mod p, i.e. (\frac{2}{p}) = 1.

Quadratic reciprocity is no isolated curiosity: most of the deeper, more conceptual treatments involve some nontrivial algebraic number theory, and the efforts to formulate reciprocity laws for higher powers had a lot to do with the creation of class field theory, culminating in Artin reciprocity, one of the crowning achievements of early 20th century mathematics.

Also solved by Arin Chaudhuri, Ashwin Kumar, Vladimir Nesov, Américo Tavares, Nathan Williams, and Henry Wilton. Thanks to all who wrote in!

About these ads