From: Dave Rusin 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 http://www.math.niu.edu/~rusin/known-math/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]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 ddq-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