From owner-math-history-list@ENTERPRISE.MAA.ORG Wed Apr 1 10:24 EST 1998 Received: from enterprise.maa.org (enterprise.maa.org [206.4.57.253]) by polaris.net (8.8.8/8.7.6) with ESMTP id KAA16123 for ; Wed, 1 Apr 1998 10:24:13 -0500 (EST) Received: from enterprise (206.4.57.253) by enterprise.maa.org (LSMTP for Windows NT v1.1a) with SMTP id <0.269B5060@enterprise.maa.org>; Wed, 1 Apr 1998 10:23:02 -0500 Received: from ENTERPRISE.MAA.ORG by ENTERPRISE.MAA.ORG (LISTSERV-TCP/IP release 1.8c) with spool id 20822 for MATH-HISTORY-LIST@ENTERPRISE.MAA.ORG; Wed, 1 Apr 1998 10:23:01 -0500 Received: from and.Princeton.EDU by enterprise.maa.org (LSMTP for Windows NT v1.1a) with SMTP id <0.262731D0@enterprise.maa.org>; Wed, 1 Apr 1998 10:23:01 -0500 Received: from broccoli.princeton.edu (conway@broccoli.Princeton.EDU [128.112.16.16]) by and.Princeton.EDU (8.8.8/8.8.3) with SMTP id KAA17765; Wed, 1 Apr 1998 10:23:36 -0500 (EST) Received: by broccoli.princeton.edu (4.1/Math-Client) id AA09268; Wed, 1 Apr 98 10:23:32 EST Mime-Version: 1.0 Approved-By: John Conway Message-ID: Date: Wed, 1 Apr 1998 10:03:13 -0500 Reply-To: Discussion List on the History of Mathematics , John Conway From: John Conway Subject: Re: Fermat and F5 Comments: To: jband To: MATH-HISTORY-LIST@ENTERPRISE.MAA.ORG In-Reply-To: Content-Type: TEXT/PLAIN; charset=US-ASCII Content-Length: 2192 Status: RO On Tue, 31 Mar 1998, jband wrote: > Hi, > > I'm new to the list. Can you explain the Euler argument please, I don't > think I've heard it before. Thanks! I don't know quite what people are meaning by "the Euler argument", but will explain everything, specializing to the particular example of F5 for simplicity. If p is a prime dividing F5, then 2^32 is congruent to -1 modulo p, and therefore 2^64 is congruent to +1 modulo p. In other words, the order of 2, modulo p is exactly 64. [The order is the LEAST positive n for which 2^n is congruent to 1.] It now follows that, modulo p, the powers of 2 repeat with period exactly 64. But we know from Fermat's little theorem that 2^(p-1) is congruent to 1, modulo p, and therefore that p-1 must be a multiple of 64. This sort of argument was used both by Fermat and Euler. It's a great help in cutting down the number of primes to be tested. In this case, the first few primes for which p-1 is a multiple of 64 are 193, 257, 449, 577, 641, so the fifth one actually works. My own opinion, like Ilan's, is that Euler probably just did the first 5 divisions. But he might well have just done five consecutive squaring modulo p, starting from 2, like this: 2 squares to 4 4 squares to 16 16 squares to 256 256 squares to 65536 , which I reduce mod 641 as follows: subtract 64100 = 100 times 641 to get 1436 subtract 1282 = 2 times 641 to get 154 154 squares to 23716 subtract 19230 = 30 times 641 to get 4486 subtract 4487 = 7 times 641 to get -1. There is a proof by Kraitchik (which I think some people are wrongly crediting to Euler), that runs as follows: 641 = 5 times 2^7 + 1 641 = 5^4 + 2^4 So 2^32 = 2^4.2^28 is congruent to -5^4.2^28 = -(5.2^7)^4 which is congruent to -(-1)^4 = -1. This is actually quite a natural thing to do, because having seen that 5 times a power of 2 is -1, modulo 9, it's obviously a good idea to study powers of 5, modulo p, and then we see that 5^4 is really quite close to p, and so on. John Conway