GuyH> Somewhat to my surprise, I seem to have been the discoverer since 1983 > of the largest known composite M(p), namely M(M(31)). DJR: Ah yes, it's divisible by 295257526626031. > Amazing what you could do with an evening's mainframe idle time and a > short program in bc. DJR: Today's tools are better: 72280004994623 | M(M(31)+12) <...> Hardy & Wright mention that if P = 3(mod4) and Q = 2P+1 are both prime, then Q | 2^P - 1. This is because Q = 7(mod8), so 2 is a quadratic residue of Q, so 2^((Q-1)/2) = 1 (mod Q). Smallest example is 7 | M3, and smallest example that factors the Mp is 23 | M11 = 2047 = 23*89. I don't know if Fermat ever mentioned this explicitly in his letters, but he knew the small examples. I think Guy meant to claim he found the largest (known) Mersenne prime MP such that MMP is composite. As Don's arithmetic shows, it's very easy to find P such that MP is composite. In fact, the prime moduli that we recommend for the IPSEC/IKE/OAKLEY key exchange algorithm (courtesy of Messers Diffie and Hellman) are Sophie Germain primes (actually the Q=2P+1) that are 7(mod 8), and, by the H&W theorem, they provide very large primes P such that MP has a known divisor Q=2P+1. I computed Qs just a tad under 2^768, 2^1024, and 2^1536, and other people have continued at least to 2^2048. Rich rcs@cs.arizona.edu