Browse Groups

• ## Re: Small prime divisors of very large numbers

(69)
• NextPrevious
• ... I did not find any such. The largest prime base for which I readily found such occurrences was q=41. For example: q=41;p=8876627;c=4824114;
Message 1 of 69 , Jul 2, 2009
View Source

> Can anyone find a prime that divides 137^^n+k and 137^^(n+3)+k
> but not 137^^(n+1)+k or 137^^(n+2)+k for n>1 ?

I did not find any such. The largest prime base for which
I readily found such occurrences was q=41. For example:

q=41;p=8876627;c=4824114;
for(k=2,10,a=vector(k,j,q);print([lift(pmod(a,p)+c),a]))

[241214, [41, 41]]
[6390615, [41, 41, 41]]
[0, [41, 41, 41, 41]]
[904821, [41, 41, 41, 41, 41]]
[1030163, [41, 41, 41, 41, 41, 41]]
[0, [41, 41, 41, 41, 41, 41, 41]]
[0, [41, 41, 41, 41, 41, 41, 41, 41]]
[0, [41, 41, 41, 41, 41, 41, 41, 41, 41]]
[0, [41, 41, 41, 41, 41, 41, 41, 41, 41, 41]]

but I did not look hard at larger prime q.

David
• ... With b = 3581, n = 8001, the 28436-digit prime p = 2*b^n + 1: http://primes.utm.edu/primes/page.php?id=5735 found by René Dohmen in March 2000, neatly
Message 69 of 69 , Jul 7, 2009
View Source

> Puzzle: Find a triplet [b, n, p] such that:
> 1) b is a prime base greater than 1033,
> 2) n is an integer exponent greater than b,
> 3) p is a prime modulus greater than b^n,
> 4) the order of b modulo p is precisely b^n.

With b = 3581, n = 8001, the 28436-digit prime p = 2*b^n + 1:
http://primes.utm.edu/primes/page.php?id=5735
found by René Dohmen in March 2000, neatly solves the puzzle.

Lemma: If b = 1 mod 4 is prime and p = 2*b^n + 1 is prime,
then the order of b modulo p is a divisor of b^n.

Proof: Both b and p are coprime to 3. Hence b = 5 mod 12 and
n is odd. Since -2*b^n = 1 mod p and p = 11 mod 24 = 3 mod 8,
we obtain kronecker(b,p) = kronecker(-2,p) = 1, from which it
follows that b^(b^n) = b^((p-1)/2) = 1 mod p.

Method: To solve the puzzle we are obliged to investigate the
possibility that the order is less than b^n. This can be done
in a Pocklington test of the primality of p, with factored
part F = b^n dividing p-1, by choosing the witness a = b in

{Pock(a,b,n)=local(p,t);if(b%12==5&&isprime(b),p=2*b^n+1;
t=Mod(a,p)^((p-1)/b);if(t^b==1&&gcd(t-1,p)==1,"Prime","?"))}

Examples: With b = 89 and n = 93, Pock(3,b,n) returns "Prime"
and Pock(b,b,n) returns "?", since gcd(t-1,p) = p. Hence the
order of Mod(b,p) is less than b^n. To prove that it is
b^(n-1) = 89^92, one may compute gcd(t^(1/b)-1,p) = 1.

With b = 3581 and n = 8001, Pock(b,b,n) returns "Prime".
By Pocklington's theorem, we have proven the primality of
p = 2*3581^8001 + 1. By using the witness a = b, we have
also shown that the order of Mod(b,p) is b^n, since the
Lemma proves that the order is a divisor of b^n and
Pock(b,b,n) found that b^((p-1)/b) - 1 is coprime to p.

Comment: I was unable to find an entry in the Prime Pages
that provides a solution with n > b > 3581. There is an
interesting reason for this. The archivable case
http://primes.utm.edu/top20/page.php?id=37
puts a premium on prime bases with b = 11 mod 12, for which
a prime p = 2*b^n + 1 = 23 mod 24 = 7 mod 8 is certain to
divide a cyclotomic number Phi(b^m,2) with m not exceeding n.
http://primes.utm.edu/primes/page.php?id=69908
shows that Ingo Büchel and Wilfrid Keller obtained m = n - 1
in the 97498-digit case with b = 107, n = 48043. At large b,
one might expect to obtain m < n in about 1/b of the cases.