From: Dave Rusin <rusin@math.niu.edu>
Date: Mon, 22 Jun 1998 11:35:36 -0500 (CDT)
To: afjb@ix.netcom.com
Subject: Re: Generator properties
Newsgroups: sci.math.research

In article <358D9C74.BFD8628A@ix.netcom.com> you write:
>Are necessary and sufficient conditions known under which powers of a
>prime p higher than its first divide the expression x^(p-1) -1 when
>(x,p)=1?

>The case x = kp^n + 1 is trivial. A non-trivial example is with p=29,
>for which p^2 divides 14^28 - 1.

There are "non-trivial" examples for all p. For every  x  with (x,p)=1,
you can show there is a unique  k  with (x+kp)^(p-1) -1  divisible by
p^2. In fact,  k  is just  (x^p-x)/p  mod  p, but there's really no better
way to describe  k  and so there's no "good" way to know when  k=0.

If you're looking for examples with  x  small, that's a little harder.
It's known that  2^(p-1) -1  is divisible by  p^2  for  p=1093 and
p=3511; no other such  p  are known, and all other  p  up to the millions
or more have been checked. Whether it is reasonable for there to be
infinitely many such  p  or not depends on the heuristics you put on the
situation; it is most definitely an open question to prove finitude or
infinitude.  (Guy's "Solved and Unsolved Problems in Number Theory" lists this
finitude question in section A3.) Likewise for  x=3  there is the small 
example  p=11 ; the next example is  p=1006003.  (I don't know if any others 
are known for  x=3; I think the answer is no.)

For a given  x, Maple can test all the  p  up to a million is a matter of
minutes, so getting numerical examples is not really the challenge here.
I found (x,p)=(5,20771), (7,5), (8,3); and of course if  x^p = x  mod p^2
then  (x^r)^p = (x^r)  mod p^2. You can even handle composite  p  with
this formulation, and observe that  9^6 = 9 mod 6^2   and  9^66 = 9 mod 66^2.
Here are the examples with  10 <= x <= 20 and  p < 10000:  (x,p) = 
(10, 487), (11,71), (12, 2693), (13,863), (14,29), (14, 353), (16,1093),
(16,3511), (18,5), (18,7), (18,37), (18,331), (19,7), (19,13), (19,43),
(19,137), and (20, 281); in all these cases, p  turns out to be prime.

Interestingly, the 1053/3911 situation created a bug in Maple's integer
factorization routine in release 3; see
	97/maple.blindspot

Historically, the condition  x^p = x mod p^2  was of value in attempts to
prove Fermat's Last Theorem; just after the turn of the century
Weierfrich et al showed an important case of the theorem is true for the
exponent  p  unless  x^p = x mod  p  for several small  p  simultaneously.

dave

==============================================================================
[A couple of typos corrected 1999/04/09.

The list of examples misses a couple of trivial examples in the given ranges.
Data below.

Note that in none of the given examples is  x^p = x mod p^3  except (x,p)= 
(7,18), (7,19). It is trivial to find examples of pairs  (x,p)  with  x>1  and
x^p = x mod p^3, but the values of  x  will be fairly large (relative to p);
for example when  p=2  we must have  x >=8; when p=3 we need x >= 26; when
p=5 we must have x >= 57 (but for p=7 we can use the comparatively small
x=18 mentioned above).
]
==============================================================================

From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Super-satisfied Fermat congruences (Was: Re: Nico Benschop's Non-corollary)
Date: 11 Apr 1999 05:27:46 GMT

The recent re-emergence of the "1093" problem encouraged me to collect
some more data and consider the heuristics; I thought others might
appreciate this report.

Fermat's little theorem states that if  p  is prime and  k  any integer,
then  k^p = k (mod p). For a number of reasons people have asked about
examples with    k^p = k (mod p^r)  for other  r > 1, usually with small  k.
An example is the congruence  2^1093 = 2  mod  1093^2.

I will focus on the case  r=2  until the end of this report.

For any fixed prime  p, the congruence  k^p = k mod p^2  holds for  p
congruence classes modulo  p^2:  k=0  is the only solution among multiples
of  p, and the others are the  (p-1)-st roots of unity in  (Z/(p^2))^*;
equivalently, they are the  p-th  powers in the ring  Z/(p^2). It follows
that if you consider any interval of integers of length  M, there are
about  M/p  solutions to  k^p=k mod p^2  in this interval. They are most
definitely NOT evenly distributed in this interval -- e.g. there are
three consecutive solutions  k=-1,0,1 -- but if  M  is at least  p^2,
for example, then the estimated number of solutions dominates the error term.
Also note that among the irregularities of the solution set, we know
easily which multiples of  p  are solutions  k; and we know that if  k  is
a solution, so is  k^m  for any integer  m. (Actually if  k and m  are prime 
to  p, the converse is also true.) 

So there are many solutions to our problem, though not necessarily having
k  "small". But, how small is "small"? In order to answer this, we can
chart the solutions found by mapping a solution pair  (k,p)  to the point
(log(p), k/log(p))  in the plane. Then the solutions for a particular  p
line in a vertical line, and the "small" solutions are those near the
horizontal axis. There is a good reason to use this particular mapping,
as we shall see.

Despite the irregularities noted two paragraphs earlier, it is appropriate
in regions FAR from the horizontal axis ("far" meaning "relative to  p")
to think of the solution set as being the outcome of a random selection of
points in the various vertical lines, with each point selected with
probability  1/p.  In a similar way, the Prime Number Theorem may be
interpreted as stating that the prime numbers are roughly distributed
as though selected by a random process with probability  1/log(p). (This
interpretation may be stated with error estimates; informally, it's true
that this view is increasingly accurate as we move farther to the right.)

Thus if we take a rectangle of sufficiently great height  h  and of width  w,
starting at some point  (x,y), we can estimate the number of solutions
(k,p) represented by points in the rectangle: the number of primes  p with
log(p) in  [y, y+w]  is  pi(e^(y+w))-pi(e^y) ~ e^y (e^w -1)/y ~ w e^y / y;
the number of solutions  k  for each  p  is about  M/p = h log(p)/p = h y/e^y.
Therefore, the number of solutions is the product of these, which comes out
to  h w,  the area of the rectangle. In other words,
        the images of the solutions  (k,p)  in the xy-plane should form
	a set which looks like a random distribution of points with a
	uniform density of  1.
I feel bound to repeat that this statement can be given a precise form,
complete with error estimates, but that these error terms swamp the estimate
itself unless applied to a region which stretches very far off the  x-axis.

On the other hand, we can collect empirical data, and they appear to support
this rule of thumb, even over comparatively shallow regions of the plane.
Here is a Maple display showing the approximate locations of the points
in the rectangle  [0,14.5] x [0,20]  which correspond to solutions (k,p):

20+                  o                   o        o         o    o       o o  
  +              o o  o            o o   o                    o o     o   o   
  +                o  o        o                           o   o           o  
  +           o             o o              o  o     ooo      o  o    oo     
  +         o               o  o        o o   oo   o      oo     o            
15+       o               o  o    o                o ooo  o o o   o o    o    
  +             o o  oo       o     o                         o        o    o 
  +                    o   oo o o  o        o o  o               o        o   
  +                o     o o    o        o      oo   o o  oo   oo  o    o   o 
  +       o   o                    o  o       o o o                           
10+         o                              o o   o o  o         o   o         
  +         o  o oo       o   o    o   o  o    o  oo   o    o                 
  +                        o  o  o               o   o   o oo    o    oo      
  +     o      o        o      o    o    oo            o  o         oo   o    
  +                     o     o        o                o      o         o    
5 +                 oo                  o     o        o o  o     o o o       
  +       o        o       o                o   o             o               
  +           o                oo  o           o         o oo            o    
  +                     o       o   o                 o        o              
  +           o                   o       o           oo o    o           oo  
  +-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+-+-+o+-+-+o+-+-+-+-o-+o+-o-+-+-+-+-o-+-o-o+ 
0           2         4          6         8        10        12        14    

This isn't a lot of data and I don't claim to have analyzed it statistically,
but it does appear to be fairly uniformly distributed except at the extreme
left (there are not many primes with  log(p)<2 ...). Please note that I have
excluded a few points, namely those with  k  a perfect power. If included,
the single low dot corresponding to  (k,p)=(2,1093), for example, would
be replaced by as many as  7  dots in this graph, corresponding to 'new'
solutions with k=4, 8, 16, ... I cannot quite determine which would be
a more "fair" test -- including the dependent solutions or not. (Of course
I have also excluded the perfect powers  k=0, k=1.)

Based on the big-picture analysis and the small-picture data, we take the
leap of faith that the number of solutions in any "nice" region is roughly
equal to the area of that region.

Now consider the set of solutions to  k^p=k mod p^2  with  2 < =k <= kmax  and
2 <= p <= pmax.  These are the solutions in the  xy-plane with  x <= log(pmax)
and  y <= kmax/x. The number of these solutions should then be roughly
this area, which is  kmax * log(log( pmax )).  In particular, as  pmax -> oo
this area becomes infinite. Considering different values of  kmax  shows:
	For a fixed  k, the set of solutions to  k^p=k mod  p^2  should
	be infinite; on average, the number of DIGITS of each solution  p
	should be about  e  times as large as the number of digits in the
	previous solution !

Selfridge is supposed to have posed the question of finding "fifty more
numbers like  1093". It should be clear that we should not expect these
numbers to be small enough to allow their discovery by tabulating all p !

Now let us compare this to the task of finding solutions to  k^p=k mod p^r
for  r>2. The entire analysis above carries over without real change, as
long as we map the pair  (k,p)  to the point  (log(p),k/( p^(r-1) log(p) ) ).
However, that means the number of solutions having only  k < kmax  should
roughly be the same as an area, which is now given by an exponential
integral which is certainly less than  int( k/exp((r-1)x),x ). This
integral is _bounded_, and so we suppose that there are only
finitely many solutions  (k,p)  with a fixed  k. Whether or not there are
any at all depends on  k: there are many small  k  for which no solution
p  is known, but there must be solutions for general values of  k.

dave

==============================================================================
#Here are the data:
#
#"Small" solutions to  k^p=k mod p^2  tabluated by the following Maple program
#We take "small" to mean  k < 20 log(p), and have checked to p= 178 482 300+

kernelopts(printbytes=false);

Mx:=10^9:Nx:=20: #Make a list of non-powers  k  and when to start using them:
a:=[]:for i from 2 to floor(evalf(Nx*log(Mx))) do 
 en:=floor(evalf(log(i)/log(2)))+1: powr:=false:
 for j from 2 to en do if i=floor(simplify((i^(1/j))))^j then powr:=true:fi:od:
 if powr=false then a:=[op(a),i] fi:od:lprint(a);
Digits:=30:b:=[seq(ceil(evalf(exp(a[i]/Nx))),i=1..nops(a))]:lprint(b);
N:=5:S:=[]:
for p from 2 to Mx do
 if isprime(p) then
  if p>b[N] then lprint(`stretch to`,a[N],b[N]):N:=N+1: fi: #Quirk: see remark
  for j to N do aa:=a[j]:
 	if (aa&^p mod p^2)=aa then S:=[op(S),[aa,p]]:lprint(aa,p):fi: od:
 fi:od:
#through  k < 20*log(p), with p < 10^8 or so.
#Very small examples (p<400,k<75) missed by quirk in the program, added later.

#Note: can only extract roots of base if root is prime to p, which will only
#be a problem for the smallest p. So need have added manually:
#[8, 3], [9,2]
#Also: do we want to include the pairs k=0 mod p^2 ? Add:
#[4,2], [9,3], [25,5], [8,2], [18,3], [12,2]
#Also  [63, 23]  has ratio  20.0925 -- a near miss; add in?

CC:=[
[5,   2],
[9,   2],
[13,   2],
[8,   3],
[7,   5],
[18,   5],
[24,   5],
[18,   7],
[19,   7],
[30,   7],
[31,   7],
[3,   11],
[40,   11],
[19,   13],
[22,   13],
[23,   13],
[38,   17],
[40,   17],
[28,   19],
[54,   19],
[28,   23],
[42,   23],
[14,   29],
[41,   29],
[60,   29],
[63,   29],
[18,   37],
[51,   41],
[19,   43],
[75,   43],
[53,   47],
[67,   47],
[71,   47],
[53,   59],
[11,   71],
[26,   71],
[31,   79],
[53,   97],
[43,   103],
[68,   113],
[38,   127],
[62,   127],
[58,   131],
[19,   137],
[78,   151],
[65,   163],
[84,   163],
[78,   181],
[69,   223],
[44,   229],
[33,   233],
[94,   241],
[48,   257],
[79,   263],
[20,   281],
[91,   293],
[40,   307],
[104,   313],
[18,   331],
[71,   331],
[75,   347],
[14,   353],
[52,   461],
[10,   487],
[93,   509],
[69,   631],
[56,   647],
[84,   653],
[120,   653],
[22,   673],
[92,   727],
[46,   829],
[13,   863],
[127,   907],
[2,   1093],
[76,   1109],
[78,   1163],
[45,   1283],
[62,   1291],
[35,   1613],
[119,   1741],
[54,   1949],
[87,   1999],
[143,   1999],
[95,   2137],
[151,   2251],
[12,   2693],
[68,   2741],
[59,   2777],
[122,   2791],
[79,   3037],
[2,   3511],
[35,   3571],
[108,   3761],
[83,   4871],
[138,   4889],
[136,   5153],
[110,   5381],
[96,   5437],
[44,   5851],
[80,   6343],
[31,   6451],
[137,   6733],
[102,   7559],
[105,   7669],
[39,   8039],
[96,   8329],
[153,   8539],
[114,   9181],
[93,   9221],
[76,   9241],
[110,   9431],
[108,   10271],
[85,   11779],
[102,   11813],
[185,   12577],
[83,   13691],
[151,   14107],
[140,   14591],
[148,   14879],
[95,   15061],
[84,   20101],
[5,   20771],
[124,   22511],
[146,   22639],
[147,   24203],
[24,   25633],
[168,   27427],
[98,   28627],
[15,   29131],
[149,   29573],
[55,   30109],
[75,   31247],
[94,   32143],
[77,   32687],
[18,   33923],
[123,   34849],
[179,   35059],
[63,   36713],
[5,   40487],
[177,   42397],
[17,   46021],
[20,   46457],
[33,   47441],
[57,   47699],
[87,   48121],
[17,   48947],
[173,   56087],
[78,   56149],
[166,   61819],
[130,   62351],
[6,   66161],
[40,   66431],
[178,   67751],
[86,   68239],
[130,   70439],
[199,   77263],
[37,   77867],
[106,   79399],
[220,   79867],
[93,   81551],
[57,   86197],
[172,   91303],
[157,   122327],
[12,   123653],
[179,   126443],
[217,   127447],
[45,   131759],
[204,   142061],
[70,   142963],
[142,   143111],
[198,   147647],
[30,   160541],
[148,   161141],
[117,   182111],
[228,   182353],
[141,   192047],
[155,   211691],
[240,   227797],
[190,   236981],
[104,   237977],
[67,   268573],
[211,   279311],
[192,   302279],
[155,   309131],
[191,   379133],
[190,   382351],
[92,   383951],
[63,   401771],
[134,   406531],
[94,   463033],
[7,   491531],
[6,   534851],
[107,   613181],
[76,   661049],
[248,   663893],
[106,   672799],
[220,   717967],
[190,   753743],
[158,   820279],
[232,   838667],
[3,   1006003],
[79,   1012573],
[41,   1025273],
[101,   1050139],
[204,   1070347],
[273,   1086731],
[183,   1231487],
[18,   1284043],
[264,   1446587],
[22,   1595813],
[284,   1601147],
[13,   1747591],
[260,   1749229],
[171,   1803383],
[199,   1843757],
[212,   1960573],
[120,   2074031],
[242,   2386301],
[242,   2434609],
[23,   2481757],
[69,   2503037],
[31,   2806861],
[253,   2905031],
[97,   2914393],
[195,   3132631],
[118,   3152249],
[6,   3152573],
[292,   3239857],
[215,   3327697],
[281,   3443059],
[163,   3898031],
[157,   4242923],
[238,   4997219],
[133,   5277179],
[151,   5288341],
[159,   5356051],
[153,   5540099],
[161,   6188401],
[197,   6237773],
[155,   6282943],
[260,   6647339],
[56,   7079771],
[55,   7278001],
[217,   8468323],
[182,   8934721],
[20,   9377747],
[118,   10404887],
[92,   12026117],
[142,   12838109],
[143,   12848347],
[96,   12925267],
[282,   13120561],
[220,   13477271],
[312,   13622501],
[23,   13703077],
[127,   13778951],
[272,   14084849],
[204,   15028133],
[271,   16774141],
[254,   18042251],
[92,   18768727],
[137,   18951271],
[260,   19148231],
[109,   20252173],
[150,   21199069],
[152,   22554863],
[302,   22621771],
[103,   24490789],
[165,   25102757],
[207,   26240063],
[337,   30137417],
[326,   30589393],
[254,   32984389],
[303,   33873179],
[141,   42039743],
[58,   42250279],
[267,   46926349],
[5,   53471161],
[152,   54504719],
[10,   56598313],
[79,   60312841],
[98,   61001527],
[19,   63061489],
[167,   64661497],
[325,   68992603],
[134,   73629977],
[336,   78666481],
[321,   78793807],
[150,   85877201],
[201,   86722091],
[233,   86735239],
[66,   89351671],
[161,   93405163],
[363,   94565579],
[344,   102089209],
[221,   103361803],
[235,   118022689],
[149,   121456243],
[20,   122959073],
[302,   123644663],
[120,   124148023],
[365,   128587933],
[224,   130677149],
[41,   138200401],
[102,   139409857],
[45,   157635607],
[263,   159838801]
]:

print(nops(CC),`terms, max p=`,CC[nops(CC)][2],`(log=`,evalf(log(CC[nops(CC)][2])),`)`);
#lprint(`k`,`p`);
#for c in CC do lprint(c[1],c[2]):od:

#look for "accidental" repeats:
print(`Primes with two low p-th powers:`):
lprint(`k1, k2, p`);
for i to nops(CC)-1 do if CC[i][2]=CC[i+1][2] then lprint(CC[i][1],CC[i+1][1],CC[i][2]):fi:od:
#87, 143, 1999  is the largest, followed by
#84 129 653;  18 71 331; 65 84 163; 38 62 127; 11 26 71
#For p=47 we find k=53,67,71  all work; likewise p=29, k=14,41,60, 63!
#Other examples with p=43  and all  p<25 except p=3!
#Note that the p has _two_ hits with "probability" (20log(p)/p)^2, so the 
#number of such primes is about int(20log(p)/p)^2*dp/log(p) = 400(logN+1)/N.
#This is  1  for N=3685, .0007 for N=10^7.  So maybe  1999  is the last.

print(`Twin primes each with a low p-th power`):
for i to nops(CC)-1 do if CC[i+1][2]-CC[i][2]=2 then lprint(CC[i],CC[i+1]):fi:od:
#Also several twin primes, largest is 41-43. OTOH, largest gap between primes
#is after [118,   10404887]. "Percentage-wise", closest pair of distinct primes
#is [118,   3152249], [6,   3152573]; furthest is [8,   3], [7,   5] ! 
#(although perhaps [172,   91303], [157,   122327]  is more "real").

#Of course, by design we find multiple pairs with the same  k -- only 
#non-power k <= 365 are in the table shown.
print(`Max  k  is`,max(seq(CC[i][1],i=1..nops(CC))));
#Interestingly no solutions found here with  k=21, 29, 34, 47, 50, 61, 72, ...
#but perhaps they are known; see references below.
CX:=array[1..20*20]:for i to 400 do CX[i]:=[]:od:
for i to nops(CC) do CX[CC[i][1]]:=[op(CX[CC[i][1]]),CC[i][2]]:od:
for i to 400 do lprint(i,CX[i]):od:
#e.g. k=18 has p=5,7,37,331,33923,1284043 ! Three for k=260!

#Super-duper congruences?
print(`Solutions to k^p=k mod p^3:`);
for c in CC do if (c[1]&^c[2] mod c[2]^3)=c[1] then lprint(c) fi od;
#only with p=7,23,113. None of these have k^p=k mod p^4.

#plotting routines (These look better with  XMaple: more exact positioning.)
BB:=[seq(evalf([log(CC[i][2]),CC[i][1]/log(CC[i][2])]),i=1..nops(CC))]:
plot(BB,x=0..BB[nops(BB)][1],y=0..20,style=point); 
plot(BB,x=0..20,y=0..2,style=point);

print(`Adding in (relatively prime) powers:`):
DD:=[]:for c in CC do for r from 2 to evalf(log(20*log(c[2]))/log(c[1])) do
 DD:=[op(DD),[c[1]^r,c[2]]]:od:od:
print(nops(DD),`of them:`):
for i to nops(DD) do lprint(DD[i][1],DD[i][2]):od:
as:=proc(a,b)
   if a[2]<b[2] or (a[2]=b[2] and a[1]<b[1]) then true else false fi end:
CC:=sort([op(CC),op(DD)],as):
BB:=[seq(evalf([log(CC[i][2]),CC[i][1]/log(CC[i][2])]),i=1..nops(CC))]:
print(nops(CC),`terms, max p=`,CC[nops(CC)][2],`(log=`,evalf(log(CC[nops(CC)][2])),`)`);lprint(`k`,`p`);
#for i to nops(CC) do lprint(CC[i][1],CC[i][2]):od:
plot(BB,x=0..20,y=0..20,style=point); 
plot(BB,x=0..20,y=0..2,style=point);

print(`Distribution`):
#expect about 20 terms per unit-x
for i to 20 do
s:=0:for b in BB do if b[1]<i and b[1]>i-1 then s:=s+1:fi:od:
lprint(i,s);od:lprint();

di:=proc(a,b) evalf(sqrt((a[1]-b[1])^2+(a[2]-b[2])^2)):end:
mn:=100:for i to nops(BB) do for j from i+1 to nops(BB) do dd:=di(BB[i],BB[j]):
if dd<mn then mn:=dd:bst:=[i,j]:fi:od:od:
print(`closest pair seen: `,CC[bst[1]],CC[bst[2]]);
#found k=242 works for both p=2386301 and 2434609  (only 2.02% larger)

==============================================================================
Some of these results are already in the literature:

   98h:11002 11A07 (11B68)
   Agoh, Takashi(J-SUT-M2); Dilcher, Karl(3-DLHS); Skula,
   Ladislav(CZ-MASS)
   Fermat quotients for composite moduli. (English. English summary) 
   J. Number Theory 66 (1997), no. 1, 29--50. [ORIGINAL ARTICLE] 

   The authors investigate when $q\sp {\phi(m)}\equiv 1 \pmod {m\sp 2}$,
   thus generalizing the usual notion of Fermat quotients (for primes
   $m$). They show the surprising fact that if $m$ is such an integer
   (which they call a "Wieferich number"), then the largest prime factor
   $p$ of $m$ is also a Wieferich number (that is, $q\sp {p-1}\equiv 1
   \pmod {p\sp 2}$). They then show how to determine all Wieferich
   numbers with a given largest prime factor. Given that there have been
   very extensive computations of Wieferich primes [see R. E. Crandall,
   K. Dilcher and C. Pomerance, Math. Comp. 66 (1997), no. 217, 433--449;
   MR 97c:11004; P. L. Montgomery, Math. Comp. 61 (1993), no. 203,
   361--363; MR 94d:11003], this allows them to find all of the Wieferich
   numbers with prime factors less than some astronomical bound.
     
   The authors have to develop many results about such composite moduli,
   analogous to well-known results for prime moduli. There are some
   pretty consequences, including a (technical) characterization of
   Wieferich numbers. If $m$ is squarefree then this characterization
   becomes: $m$ is Wieferich if and only if for every prime factor $p$ of
   $m$, we either have that $p$ is a Wieferich prime or $p$ divides $ l
   -1$ for some other prime divisor $ l$ of $m$. Their characterization
   also leads to the consequence that the product of any two coprime
   Wieferich numbers is also a Wieferich number.

                        Reviewed by Andrew Granville
     _________________________________________________________________

   97i:11003 11A07 (11Y70)
   Ernvall, R.; Metsänkylä, T.(FIN-TURK)
   On the $p$-divisibility of Fermat quotients. (English. English
   summary)
   Math. Comp. 66 (1997), no. 219, 1353--1365. [ORIGINAL ARTICLE] 

   If $a$ is an integer not divisible by the odd prime $p$, let $q\sb a$ 
   (the "Fermat quotient") denote the least non-negative residue of
   $(a\sp {p-1}-1)/p$ modulo $p$. This paper reports the results of
   computations of $q\sb a$ for $0<a<p$ and $p<10\sp 6$, and surveys
   related theoretical results. There have been many previous
   computations [see, e.g., J. Brillhart, J. Tonascia and P. Weinberger,
   in Computers in number theory (Proc. Sci. Res. Council Atlas Sympos.
   No. 2, Oxford, 1969), 213--222, Academic Press, London, 1971; MR 47
   #3288]. However, the emphasis of the present paper is principally on
   the behaviour of $q\sb a$ for fixed $p$ and varying $a$, an aspect
   largely ignored in previous works.

                       Reviewed by D. R. Heath-Brown
     _________________________________________________________________

   97c:11004 11A07 (11Y35)
   Crandall, Richard(1-REED-AC); Dilcher, Karl(3-DLHS); Pomerance,
   Carl(1-GA)
   A search for Wieferich and Wilson primes. (English. English summary)
   Math. Comp. 66 (1997), no. 217, 433--449. [ORIGINAL ARTICLE] 
   
   An odd prime $p$ is called a Wieferich prime [resp. a Wilson prime] if
   $2\sp {p-1}\equiv 1\bmod p\sp 2$ [resp. $(p-1)!\equiv -1\bmod p\sp
   2$]. The study of these numbers is motivated by the first case of
   Fermat's last theorem. For instance, if $p$ does not divide $xyz$ and
   $x\sp p+y\sp p+z\sp p=0$, then $p$ is a Wieferich prime. The only
   known Wieferich primes [resp. Wilson primes] are 1093 and 3511 [resp.
   $5$, $13$, $563$]. The article under review extends the search of
   previous authors to show that there are no new Wieferich primes [resp.
   Wilson primes] below $4\times 10\sp {12}$ [resp. $5\times 10\sp 8$].
   These negative results are supported by a statistical model for the
   existence of such numbers.
   
   From a practical point of view, the computations are speeded up using
   many tricks, among which are the use of fast arithmetic mod $p\sp 2$
   and a fast procedure for evaluating a product of terms in an
   arithmetic progression. The computation of $(p-1)!$ is accelerated
   using a formula due to Granville together with known formulae
   involving quadratic partitions and binomial coefficients. A typical
   example is as follows: if $p\equiv 5\bmod 12$, write $p=a\sp 2+b\sp 2$
   where $a\equiv 1\bmod 4$. Then $$(p-1)!\equiv(((p-1)/4)!)\sp 4(2\sp
   p-1)(2\sp {p-1}+1)\sp 2(a-p/(4a))\sp 2\bmod p\sp 2.$$ Several
   algorithms for computing factorials are also described and
   generalizations to related special primes mentioned.
   
                        Reviewed by Francois Morain
     _________________________________________________________________
   
   98a:11145 11R29 (11B68 11R18 11R20)
   Jakubec, S.(SK-AOS)  
   Connection between congruences $n\sp {q-1}\equiv 1\pmod {q\sp 2}$ and
   divisibility of $h\sp +$.
   Abh. Math. Sem. Univ. Hamburg 66 (1996), 151--158.

   Let $l,p$ and $q$ be primes with $q$ odd and $p=2l+1$. Furthermore,
   assume that $l\equiv3\bmod4, p\equiv-1\bmod q, p\equiv-1\bmod q\sp 3$
   and $q$ has order $(l-1)/2$ modulo $l$. The main theorem states: If
   $q$ divides the class number $h\sp +$ of ${\bf Q}(\zeta\sb p+\zeta\sp
   {-1}\sb p)$ then $n\sp {q-1}\equiv1\bmod q\sp 2$ for each divisor $n$
   of the number $l+1$. Since $q$ divides $p+1=2(l+1)$, the hypothesis
   that $(n,q)=1$ must be added to the theorem.
     
   The proof uses some previous results of the author [Abh. Math. Sem.
   Univ. Hamburg 63 (1993), 67--86; MR 95a:11098; Acta Arith. 71 (1995),
   no. 1, 55--64; MR 96e:11138] involving character sums and Bernoulli
   numbers. The special case $n=2$ was already proven in the latter
   article.

                        Reviewed by Charles J. Parry
     _________________________________________________________________

   96e:11138 11R29
   Jakubec, Stanislav(SK-AOS)
   Connection between the Wieferich congruence and divisibility of $h\sp
   +$. 
   Acta Arith. 71 (1995), no. 1, 55--64.
   
   Much interest in number theory is devoted to the Wieferich primes,
   which are odd primes $q$ satisfying the congruence $2\sp {q-1}\equiv
   1\bmod q\sp 2$. One of the reasons for studying these primes is the
   celebrated theorem of Wieferich (1909): "If the first case of Fermat's
   last theorem is false for an odd prime $q$, then $2\sp {q-1}\equiv
   1\bmod q\sp 2$." At present only two Wieferich primes are known,
   namely 1093 and 3511, and it is not even known whether there are
   infinitely many Wieferich primes.
   
   In this paper the author points out a connection between the property
   of a prime $q$ to be Wieferich and the divisibility of the second
   factor $h\sp +\sb p$ of the class number of the $p$th cyclotomic field
   by $q$ for a certain prime $p$: Assume that $q,p,l$ are primes with
   the properties $p=2l+1$, $l\equiv 3\bmod 4$, $q$ is odd, $p\equiv
   -1\bmod q$, $p\nequiv -1\bmod q\sp 3$, order of $q\bmod l$ equals
   $(l-1)/2$, and $q$ divides $h\sp +\sb p$. Then the author proves
   Theorem 1: $q$ is a Wieferich prime.
   
                            Reviewed by L. Skula
     _________________________________________________________________
   
   94d:11003 11A07 (11A15)
   Montgomery, Peter L.(1-ORS)
   New solutions of $a\sp {p-1}\equiv 1\pmod {p\sp 2}$. (English. English
   summary)
   Math. Comp. 61 (1993), no. 203, 361--363. 
   
   Some number-theoretic questions require primes $p$ satisfying (1)
   $a\sp {p-1}\equiv 1\bmod p\sp 2$ for given $a$ not a power. J. D.
   Brillhart, J. Tonascia and P. J. Weinberger listed all solutions of
   (1) for $2\leq a\leq 99$ and $3\leq p<10\sp 6$ [see Computers in
   number theory (Oxford, 1969), 213--222, Academic Press, London, 1971;
   MR 47 \#3288]. In this paper, the author extends the above results to
   $p<2\sp {32}$ and gives $23$ new solutions. Included are the first
   solutions for $a=66$ and $a=88$.

                             Reviewed by Qi Sun
     _________________________________________________________________

   85e:11001 11-01 (11A41)
   Ribenboim, P.(3-QEN)
   "$1093$". 
   Math. Intelligencer 5 (1983), no. 2, 28--34.
   
   An excursion through various topics in number theory, starting with
   the fact that 1093 is the smallest prime $p$ satisfying $2\sp
   {p-1}\equiv\break 1$ $({\rm mod}\,p\sp 2)$, and touching on Fermat's
   last theorem, Fermat and Mersenne numbers.
   
                          Reviewed by H. J. Godwin
     _________________________________________________________________

   56 #8489 10B15 (10A30)
   Johnson, Wells
   On the nonvanishing of Fermat quotients $({\rm mod}$ $p)$. 
   J. Reine Angew. Math. 292 (1977), 196--200.
   
   The author derives various conditions on $p$ and $a$ that ensure that
   $q\sb a\not\equiv 0 (\text{mod}\,p)$, where $q\sb a$ is the Fermat
   quotient modulo $p$, i.e. $q\sb a=(a\sp {p-1}-1)/p$. The results imply
   the validity of the Fermat conjecture in the first case for prime
   exponents, $p$, which linearly divide the sums $a\sp {(s-1)k}±a\sp
   {(s-2)k}±\cdots±a\sp k+1$, where $p\nmid s$ and $2\leq a\leq 31$.
   Noting that the two primes $p$ known, 1093 and 3511, for which $q\sb
   2\equiv 0 (\text{mod}\,p)$, exhibit a certain cyclicity in their
   binary expansions, the author deduces that primes $p$ that have a
   similar property in their $a$-adic expansion satisfy $q\sb a\not\equiv
   0 (\text{mod}\,p)$.
   
                          Reviewed by Graham Lord
     _________________________________________________________________
   
   53 #11090 32C10 (14J25 57D20 10C10)
   Ewing, John; Moolgavkar, Suresh
   On the signature of Fermat surfaces. 
   Michigan Math. J. 22 (1975), no. 3, 257--268 (1976).
   
   The Fermat surface $Q\sb n(q)$ is the hypersurface of complex
   dimension $n$ and degree $q$ in $CP\sp {n+1}$ given by the equation
   $z\sb 0{}\sp q+z\sb 1{}\sp q+\cdots+z\sb {n+1}\sp q=0$. There are
   well-known formulas for the numbers $\chi\sp k=$ Euler number with
   coefficients in the sheaf of germs of holomorphic $k$-forms [cf. the
   reviewer, Proc. Internat. Congress of Mathematicians (1954,
   Amsterdam), Vol. III, pp. 457--473, Noordhoff, Groningen, 1956; MR 19,
   317]. The signature of $Q\sb n(q)$ equals the sum of the $\chi\sp k$,
   and the Euler number of $Q\sb n(q)$ equals the alternating sum of the
   $\chi\sp k$. The number $\chi\sp 0$ is the Todd genus. The formula $$
   \chi\sp k=(-1)\sp k+\sum\sb {t=0}\sp k(-1)\sp {n+k-t}\left(
   \smallmatrix n+2 \\ t \endsmallmatrix \right)\left( \smallmatrix
   qk-qt+q+t-1 \\ n+1 \endsmallmatrix \right) $$ given by the authors
   seems to be new. Using one of the signature formulas, the authors show
   that, for an odd prime $q$, $\text{sign}\,Q\sb {2n}(q)\equiv
   0\,\text{mod}\,q$ for $2n\leq q-3$ and $\text{sign}\,Q\sb
   {2n}(q)\equiv 1\,\text{mod}\,q$ for $2n>q-3$. For $2n\leq q-3$ it
   turns out that $q\sp {-1}\,\text{sign}\,Q\sb {2n}(q)\equiv
   1+{\textstyle\frac 1{3}}+{\textstyle\frac 1{5}}+\cdots+(2n+1)\sp
   {-1}\,\text{mod}\,q\sp 2$. From known results in number theory, the
   authors deduce that $q\sp 2\vert \text{sign}\,Q\sb {q-3}(q)$ if and
   only if $2\sp {q-1}\equiv 1\,\text{mod}\,q\sp 2$ and $q\sp 3\vert
   \text{sign}\,Q\sb {q-3}(q)$ if and only if $2\sp {q-1}\equiv
   1\,\text{mod}\,q\sp 3$. These conditions are interesting since both
   are known to be necessary for the first case of the Fermat conjecture
   $(x\sp q+y\sp q+z\sp q=0,q\nmid xyz)$. The first holds for exactly two
   primes $<3·10\sp 9$ (namely 1093, 3511) and almost certainly for
   infinitely many primes, whereas the latter holds for no prime
   $<3·10\sp 9$ and almost certainly for no prime at all [cf. J.
   Brillhart, J. Tonascia and P. Weinberger, Computers in number theory
   (Proc. Sci. Res. Council Atlas Sympos. No. 2, Oxford, 1969), pp.
   213--222, Academic Press, London, 1971; MR 47 #3288].
   
                         Reviewed by F. Hirzebruch
     _________________________________________________________________

   47 #3288 10A10
   Brillhart, J.; Tonascia, J.; Weinberger, P.
   On the Fermat quotient. Computers in number theory (Proc. Sci. Res.
   Council Atlas Sympos. No. 2, Oxford, 1969), pp. 213--222. 
   Academic Press, London, 1971.

   This is a report on a seven year search for odd solutions $N$ of the
   congruence $a\sp {N-1}\equiv 1 (\text{mod}\,N\sp 2)$ for $a=2(1)99$.
   The main results appear in a one-page table for $N=p$, an odd prime,
   and $a$ in the given range if it is not a power; the omission of
   powers is justified by Theorem 1: If $p$ is a prime that does not
   divide an integer $n\geq 2$, then, with $\alpha\geq 2$, an integer,
   $(a\sp n)\sp {p-1}\equiv 1 (\text{mod}\,p\sp \alpha)$ if and only if
   $a\sp {p-1}\equiv 1 (\text{mod}\,p\sp \alpha)$. This table gives a 
   resume of all known information; the search range varies with $a$ but
   is always at least 2$\sp {\text{25}}$. The new values listed may be
   indicated for brevity as pairs $(a,p)$ and are (5, 53471161), (10,
   56598313), (18, 1284043), (19, 63061489), (20, 9377747), (20,
   122959073), (22, 1595813) and (23, 1370377). A second and much briefer
   table gives the (odd) composite solutions whose prime divisors appear
   in Table 1. Its brevity is due to three theorems, of which the first
   seems most significant. It is as follows: If $a\sp {N-1}\equiv 1
   (\text{mod}\,N\sp 2)$, with $a$ and $N$ both greater than 1, and $p\sp
   \alpha$ divides $N$, then $p\sp {2\alpha}$ divides $a\sp {p-1}-1$. The
   paper also contains remarks on the significance of the search, as  
   reflected in the appearance of the congruence in strikingly different
   problems in number theory, a description of the computer programming
   procedure (the work was almost completely in idle time) and an
   extensive bibliography. 
   
[deletia -- djr]
                           Reviewed by J. Riordan
     _________________________________________________________________
   
   39 #2690 10.03
   Fröberg, C. E.
   On some number-theoretical problems treated with computers. Computers
   in Mathematical Research pp. 84--88
   North-Holland, Amsterdam 1968
   
   In number theory, the application of computers has been very natural.
   The author illuminates recent research on Wilson and Fermat
   remainders, on the inverses (reciprocals) of twin primes, and on the
   Mobius power series.
   
[deletia -- djr]
   
   Let the Fermat remainder $F\sb p$ be defined as the remainder when
   $a\sp {p-1}-1$ is divided by $p\sp 2$. Then $F\sb p=0$ for $a=2$ and
   $p\sp 2=1093\sp 2$ and $p\sp 2=3511\sp 2$, but there were no other
   $p\sp 2$ for $a=2$ and $p<50000$ in 1958 [the author, Math. Tables
   Aids Comput. 12 (1958), 281], and for subsequent raises of $p$ up to
   31059000 by S. Kravitz [Math. Comp. 14 (1960), 378; MR 22 #12073], H.
   Riesel [ibid. 18 (1964), 149--150; MR 28 #1156], E. H. Pearson [ibid.
   17 (1963), 194--195; MR 28 #2996], Hausner and Sachs [1964,
   unpublished], and K. E. Kloss [J. Res. Nat. Bur. Standards Sect. B 69B
   (1965), 335--336; MR 32 #7473]. But many $p\sp 2$ for $a>2$ were
   found, for example: $p\sp 2=1006003\sp 2$ for $a=3$, $p\sp
   2=1747591\sp 2$ for $a=13$, $p\sp 2=2481757\sp 2$ for $a=23$, and
   $p\sp 2=1025273\sp 2$ for $a=41$, all found by Kloss, and the most
   recent result (not yet published) $p\sp 2=3152573\sp 2$ for $a=6$
   found in 1969 by John Brillhart.
   
[deletia -- djr]
                            Reviewed by E. Karst
     _________________________________________________________________
   
   © Copyright American Mathematical Society 1999