# Searching for special double solutions to 2^x + 2^y = p^z - p^w for prime p, used in paper "On the generailzed Pillai equation $\pm a^x \pm b^y = c$" where we have the embarrassing unfinished case in Theorem 6 of p = 1 mod 16 # # March 18, 2004 # # A solution which is problematic for our results satisfy p = 1 mod 16. We can use three different approaches to eliminate values of p. # # The first is simple congruence conditions: if r is max such that 2^r | p-1, then if r = 4 can eliminate all but p mod 5 = 2, then if r=4 can eliminate all except p mod 16 = -2, -6, or 8. If r = 5, 8, 9, 12, or 13 etc. can eliminate all but p mod 5 = 2, if r = 6, 7, 10, 11, etc, can eliminate all but p mod 5 = 3. These conditions seem to eliminate about 2/3 of all primes. # # Second, we can rewrite 2^x + 2^y = p^z - p^w as 2^x( 2^(y-x) + 1 ) = p^z (p^(w-z) - 1 ) and we claim that y-x is odd and that z-w must be 2 mod 4. In particular, z-w is even so p and p-1 and p+1 divide both sides. Let q be the odd part of p-1, and let r be the odd part of p+1. Define minusorder(b,a) to mean the least power t such that b^t + 1 = 0 mod a, and let it be false if there is no such order. Then we want minusorder(2,p), minusorder(2,q) and minusorder(2,r) to all be odd. We search for any prime p satisfying all these conditions. # # Thirdly, we use Theorem 2 equation 13 of Scott's 1993 paper which gives a bound in terms of class numbers. Let N = p + 2^(r+1) ; let P = product of all primes dividing N to an odd power, and Q be the product of all primes dividing N to an even power. Define L in terms of the lcm of the Q factor as in Theorem 2. If r mod 2 = 0 then let h be the class number of Q( sqrt(-P) ), if r mod 2 = 1 then h is class number for 2*P instead. Then consider the set of divisors of J = L*h. If any divisor of L is congruent to 3 or 7 mod 16 and also not 1 mod 3, then call such a divisor k; we check if p^k - p - 2^(r+1) is a power of 2. Actually we only check if it is congruent to zero mod a large power of 2. # # We could also use bootstrapping, but this turns out to take longer and be less efficient. # > restart; with(numtheory): Warning, the protected name order has been redefined and unprotected # Here are the procedures to use the divisors p, p-1, p+1 approach. # # We find the odd part of a number. > oddpart := proc(n) > local a, i; > a:= n; > while a mod 2 = 0 do a := a/2; od; > a; > end; oddpart := proc(n) ... end; # We use the "order" that gives -1 if any, that is, minusord = t means t is the least number such that p divides 2^t+1. # If there is no such t, we set it to "fail". > minusorder := proc(a,b) > local i,ans,k,t; > i:= order(a,b); > ans := false; > while i mod 2 = 0 and ans=false do > i := i/2; > if b^i +1 mod a = 0 then ans := i; fi; > od; > ans; > end; > minusorder := proc(a, b) ... end; > # Now for the least effective but easiest congruence approach. # # We define congruence conditions that help eliminate possibilities. The conditions are determined by how many factors of 2 divide p-1. > twoexponent:= proc(n) > local i,k; > k:= n; i:= 0; > while k mod 2 = 0 do > i:= i+1; k := k/2; > od; > i; > end; twoexponent := proc(n) ... end; > twoexponent(64); 6 > congruencecondition := proc(p) > local r, ans, p5,p17; > r := twoexponent(p-1); > p5 := p mod 5; > ans:= true; > if r<4 then print("problem");fi; #this should never happen since p mod 16 = 1 > if r = 4 then if p5 <> 2 then ans:= false > else > p17 := p mod 17; > if (p17 <> 15 and p17 <> 11 and p17 <> 8) then ans:= false > fi;fi;fi; > if r = 5 or r=8 or r=9 then if p5<>2 then ans:= false > else > if r=6 or r=7 or r=10 or r=11 then if p5<>3 then ans:= false; > fi;fi;fi;fi; > ans; > end; congruencecondition := proc(p) ... end; > congruencecondition(9137); true > counttrue:= 0; countfalse:=0; > for p from 17 to 10^7 by 16 do > if isprime(p) then > if congruencecondition(p) = true then counttrue:= counttrue+1; else countfalse:= countfalse+1; fi;fi;od; > counttrue; countfalse; counttrue := 0 countfalse := 0 24992 57975 # This took about 15 minutes. # This shows that about two thirds of the primes are taken care of by the congruence condition which seems to be the fastest also. # # Now we use a class number condition test: first we find the L factor of the square part of N. > getPQ := proc(n) > local P, Q, f2, k, b, a, i; > f2 := op(2, ifactors(n)); > k := nops(f2); > P := 1; Q:= 1; > for i from 1 to k do > b := op([i,1], f2); > a := op([i,2], f2); > if a mod 2 = 1 then P := P*b; else Q := Q*b; fi; > od; > [P,Q]; > end; getPQ := proc(n) ... end; > getPQ(2^30*3^20*5^21); [5, 6] > getL := proc(P,Q) > local L, Qfac, i, q; > L := 1; > if Q > 1 then > Qfac := factorset(Q); > for i from 1 to nops(Qfac) do > q := op(i,Qfac); > L := lcm(L, q - legendre(-P, q)); > od; > fi; > L; > end; getL := proc(P, Q) ... end; > getL(3*5*11, 5*13); 60 > imagquadclassnum := proc(N) > local i, h, a, b, b1, be, d; > #we assume here that N is squarefree > if N < 4 then h := 1; else > if N mod 4 = 3 then > d := N; b := 1; > else > d := 4*N; b := 0; > fi; > h := 0; > for b1 from b to isqrt( iquo(d,3) ) by 2 do > be := iquo( b1^2 + d, 4); > for a from max(1, b1) to isqrt(be) do > if be mod a = 0 then h := h+1; > if b1 <>0 and a<>b1 and a^2 <> be then h := h+1; fi; > fi; > od; > od; > fi; > h; > end; imagquadclassnum := proc(N) ... end; > imagquadclassnum(1234567); 496 > # This test is based on Theorem 2 of Scott's 1993 paper. # We use a bound of 2^(40+r), below which we calculate the full p^k-p-2^(r+1) and see if it is a perfect power of 2, but above this bound we just view this modulo 2^8 to see if it is a power of 2. If it is 0 mod 2^8, we also check it mod 2^15. > classnumtest := proc(p) > local r, n, PQ, P, Q, L, J, k, divlist, w, i; > r := twoexponent(p-1); > n := p + 2^(r+1); > PQ := getPQ(n); > P := op(1, PQ); Q := op(2, PQ); > L := getL(P,Q); > if r mod 2 = 0 then J := L*imagquadclassnum(P); > else J := L*imagquadclassnum(2*P); fi; > divlist := divisors(J); > for i from 1 to nops(divlist) do > k := divlist[i]; > if (k mod 16 = 3 or k mod 16 = 7) and k mod 3 <> 1 then > if k < evalf((40+r)*log(2)/log(p)) then > w := p^k - p - 2^(r+1); > if oddpart(w) = 1 then w := 0; fi; > else > w := (p&^k - p - 2&^(r+1)) mod 2^8; > fi; > if w = 0 then print(p, k, r, n, J, (p&^k - p - 2&^(r+1)) mod 2^15); fi; > fi; > od; > end; classnumtest := proc(p) ... end; # We test combining the simple congruence, the minus one order conditions, and the class number conditions. > > for p from 17 to 10^8 by 16 do > if isprime(p) then > if congruencecondition(p) = true then > if (2&^oddpart(order(2,p)) + 1) mod p = 0 then > q:= oddpart(p-1); > if q>1 then > if (2&^oddpart(order(2,q)) + 1) mod q = 0 then > r := oddpart(p+1); > if r>1 then > if (2&^oddpart(order(2,r))+ 1) mod r = 0 then > classnumtest(p); > fi; > fi; > fi; > fi; > fi; > fi; > fi; > od; 2243777, 3, 6, 2243905, 792, 10496 2243777, 99, 6, 2243905, 792, 28928 3351233, 3, 6, 3351361, 1728, 29952 3463217, 119, 4, 3463249, 1428, 2816 5312897, 3, 7, 5313153, 2232, 25088 5312897, 279, 7, 5313153, 2232, 16384 6337217, 3, 6, 6337345, 1200, 5376 6368177, 119, 4, 6368209, 1428, 22528 7180673, 3, 7, 7180929, 3648, 25088 7934657, 3, 6, 7934785, 1584, 21760 7934657, 99, 6, 7934785, 1584, 23808 8956097, 3, 6, 8956225, 1296, 256 8970433, 3, 6, 8970561, 1128, 28928 9929057, 39, 5, 9929121, 3744, 10240 10075537, 3, 4, 10075569, 3168, 24064 10075537, 99, 4, 10075569, 3168, 25600 12611617, 3, 5, 12611681, 2160, 27648 12961457, 87, 4, 12961489, 2088, 17408 21701297, 23, 4, 21701329, 3312, 24576 22133297, 327, 4, 22133329, 2616, 17920 28123937, 3, 5, 28124001, 2688, 4608 29625377, 3, 5, 29625441, 4224, 9216 30101633, 35, 7, 30101889, 3920, 28672 30853937, 39, 4, 30853969, 4056, 26112 32501537, 3, 5, 32501601, 2160, 10752 32600417, 455, 5, 32600481, 3640, 17408 33478177, 419, 5, 33478241, 3352, 27648 33624257, 3, 6, 33624385, 1728, 20736 36187937, 3, 5, 36188001, 11664, 10752 36187937, 243, 5, 36188001, 11664, 14336 36611857, 3, 4, 36611889, 5904, 256 37400977, 3, 4, 37401009, 5460, 17920 37400977, 35, 4, 37401009, 5460, 18432 37400977, 195, 4, 37401009, 5460, 20992 39777377, 135, 5, 39777441, 4320, 24064 40008833, 3, 7, 40009089, 3672, 14336 40008833, 51, 7, 40009089, 3672, 4096 40999457, 3, 5, 40999521, 5640, 16384 41354017, 3, 5, 41354081, 4224, 20992 42485537, 3, 5, 42485601, 4752, 23040 42485537, 99, 5, 42485601, 4752, 17920 46989857, 3, 5, 46989921, 5376, 4096 54139937, 3, 5, 54140001, 6912, 17408 61675297, 3, 5, 61675361, 5544, 31232 61675297, 99, 5, 61675361, 5544, 26112 64013617, 231, 4, 64013649, 7392, 1536 66020897, 3, 5, 66020961, 6072, 22528 66999697, 3, 4, 66999729, 7056, 3584 66999697, 147, 4, 66999729, 7056, 5888 68526097, 3, 4, 68526129, 6912, 21248 69029137, 35, 4, 69029169, 8960, 32512 71231617, 3, 7, 71231873, 10440, 4096 71231617, 87, 7, 71231873, 10440, 23040 71231617, 435, 7, 71231873, 10440, 26624 73152817, 39, 4, 73152849, 8736, 31232 > for p from 73152817 to 10^8 by 16 do > if isprime(p) then > if congruencecondition(p) = true then > if (2&^oddpart(order(2,p)) + 1) mod p = 0 then > q:= oddpart(p-1); > if q>1 then > if (2&^oddpart(order(2,q)) + 1) mod q = 0 then > r := oddpart(p+1); > if r>1 then > if (2&^oddpart(order(2,r))+ 1) mod r = 0 then > classnumtest(p); > fi; > fi; > fi; > fi; > fi; > fi; > fi; > od; 73152817, 39, 4, 73152849, 8736, 31232 76976513, 3, 7, 76976769, 5280, 25088 79177793, 3, 6, 79177921, 5712, 0 79177793, 51, 6, 79177921, 5712, 3072 79177793, 119, 6, 79177921, 5712, 23808 83160257, 3, 6, 83160385, 4032, 2304 83888257, 3, 7, 83888513, 8376, 20480 83888257, 1047, 7, 83888513, 8376, 31232 84389953, 35, 6, 84390081, 10640, 6144 87774593, 3, 7, 87774849, 13824, 27136 88788353, 131, 7, 88788609, 2096, 6656 89292817, 3, 4, 89292849, 8460, 4864 89292817, 2115, 4, 89292849, 8460, 14080 91199873, 3, 7, 91200129, 11136, 29184 91199873, 87, 7, 91200129, 11136, 20480 92539457, 3, 6, 92539585, 4800, 17408 93900817, 3, 4, 93900849, 7728, 13056 93900817, 483, 4, 93900849, 7728, 256 We see the only case we need to check is 79177793. We check the value of p^k-p-2^(r+1) modulo 2^16: > p:= 79177793; k:= 3; r := 6; x := p^k - p - 2^(r+1); p := 79177793 k := 3 r := 6 x := 496375315612250242318336 > x mod 2^15; x mod 2^16; 0 32768 >