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