Mike Speciner <speciner@ll.mit.edu> wrote:

There's something different and interesting going on with square roots in the integers mod n for n not prime, and especially if n|24.

That's because modulo 24 all units have trivial square, i.e. gcd(m,24) = 1 => m^2 = 1 (mod 24) and, further, N = 24 is the largest modulus satisfying this property. Appended below is one of my old math-fun posts containing a discussion between John Conway and I on the magic of 24. Date: Fri, 18 Apr 1997 21:01:37 -0400 (EDT) Subject: 24: its magic property [was: How does 462 come into it?] John Conway wrote to math-fun on 13 Apr 1997: | | I was at one time very interested in whatever magic property of 24 | "caused" a number of related things, like the existence of the group | M24 and the Leech lattice, and the 24 in the definition of Ramanujan's | tau function: | | q{(1-q)(1-qq)(1-qqq)...}^24 = q + ... + tau(n).q^n + ... | | and found that indeed all of these WERE "the same" 24. In this case, | the clue came when I reformulated and reproved Atkin and Lehmer's | evaluation of the normalizer of Gamma0(N) in PSL2(R), finding that | it involved the maximal divisor h of 24 for which h^2 divided N. | What I call "the defining property of 24" turned out to be the | fact that xy == 1 (mod 24) implies x == y (mod 24), a statement | that holds true if 24 is replaced by any of its divisors, but not if | it's replaced by any other number. This property of N=24 also arises in other contexts. The property may be stated as: that unit group U(Z/N) has exponent 2 (i.e. 2 is the smallest exponent e for which x^e = 1 mod 24, for all units x). It is easy to check that 24 is the largest integer N enjoying this property: simply use the well-known expression of the exponent of U(Z/N) via the Carmichael lambda function. For an application of this property to primality testing via Jacobi symbols, see H. Lenstra's expository paper "Fast Prime Number Tests" Nieuw. Arch. Wisk. 1 (1983) 133-144, where he sketches a small toy version of the Adleman-Pomerance-Rumely Jacobi sum primality test, namely he proves the following THEOREM. Suppose that (n,6) = 1 and (n-1)/2 a a = ( - ) mod n, for a = -1, 2, 3 n and there exists and integer b for which (n-1)/2 b = -1 mod n. Then there exists, for every divisor r of n, and integer i >= 0 such that r = n^i mod 24. Of course we can take i = 0 or 1 since the unit group exponent = 2, but the result is presented this way to put it in the context of Lenstra's deep approach to primality testing, namely LENSTRA'S THEOREM. n is prime <=> every divisor r of n is a power of n. You'll have to read one of Lenstra's excellent expositions to find out why this is not so trivial. There you'll find an elegant unified viewpoint towards all modern primality tests. The proof of the first theorem depends upon the following assertion, which holds for all positive integers m,n relatively prime to 6: a a m = n mod 24 <=> ( - ) = ( - ) for a = -1, 2, 3, m n which depends on the aforementioned property of 24. This in turn is closely related to the Lehmers factorization algorithm using binary quadratic forms, which I mentioned on math-fun on 19 Aug 1996. Recall that this is a systematization of Mersenne's integer factorization method by representing N as the sum of two squares in two different ways. Underlying the technique is the structure of a Steiner triple and Fano plane. Anyone else out there with close encounters with the 24th kind? John Conway later replied to the above: | | The point of my note was, I think, more important; namely that | THIS property of 24 is the "same" one as those connecting it | to the Mathieu group M24, the Leech lattice, the Monster group, | and Ramanujan's tau-function, in the sense of Jim's question. --Bill Dubuque