A186522 Smallest prime factor of 2^n - 1 having the form k*n + 1.

3, 7, 5, 31, 7, 127, 17, 73, 11, 23, 13, 8191, 43, 31, 17, 131071, 19, 524287, 41, 127, 23, 47, 241, 601, 2731, 262657, 29, 233, 31, 2147483647, 257, 599479, 43691, 71, 37, 223, 174763, 79, 41, 13367, 43, 431, 89, 631, 47, 2351, 97, 4432676798593, 251, 103, 53, 6361, 87211, 881, 113, 32377, 59, 179951, 61

Offset: 2

Author

T. D. Noe, Feb 23 2011

Keywords

• nonn

Comments

The values of k are in A186283.

From Zhi-Wei Sun, Dec 27 2016: (Start)

For any odd prime p, by Fermat's little theorem p = (p-1) + 1 divides 2^(p-1) - 1, and it is well-known that any prime divisor q of 2^p - 1 must be congruent to 1 modulo p.

Conjecture: a(n) exists for any integer n > 1 (verified for n = 2..300). (End)

Proof of the above conjecture: By Bang's theorem, for each n > 1 except 6 there exists an odd prime p such that the multiplicative order of 2 modulo p is n, and therefore n must divide p-1. Note that a(n) <= p. - Robert Israel and Thomas Ordowski, Sep 08 2017

For prime p, a(p) = 2p + 1 if and only if p is a Lucasian prime (A002515). - Thomas Ordowski, Sep 08 2017

Examples

			For n = 4, the prime factors of 2^n - 1 are 3 and 5, but only 5 has the form k * n + 1. Hence a(4) = 5.
a(254) = 56713727820156410577229101238628035243 since this prime number is equal to (2^127+1)/3 and congruent to 1 modulo 127, and 2^127 - 1 is a Mersenne prime.
a(257) = 535006138814359 since this is a prime congruent to 1 modulo 257 and 2^257 - 1 = 535006138814359*p*q with p = 1155685395246619182673033 and q = 374550598501810936581776630096313181393 both prime. - _Zhi-Wei Sun_, Dec 27 2016
		

Links

• Table of n, a(n) for n = 2..1236
• GIMPS (Prime95), Mersenne exponent cofactor probable prime PRP.

Crossrefs

Cf. A000040, A000225, A060443 (all prime factors of 2^n-1).

Programs

Mathematica

Table[p = First/@FactorInteger[2^n - 1]; Select[p, Mod[#1, n] == 1 &, 1][[1]], {n, 2, 60}]

PARI

a(n)=my(s=if(n%2,2*n,n));forstep(p=s+1,2^n-1,s, if(Mod(2,p)^n==1&&isprime(p), return(p))) \\ Charles R Greathouse IV, Sep 07 2017

PARI

a(n)=my(f=factor(2^n-1)[,1]); for(i=1,#f, if(f[i]%n==1, return(f[i]))) \\ Charles R Greathouse IV, Sep 07 2017

Formula

a(p - 1) = p for odd prime p. - Thomas Ordowski, Sep 04 2017

A002326((a(n)-1)/2) divides n for all n > 1. - Thomas Ordowski, Sep 07 2017

a(n) = A186283(n) * n + 1. - Max Alekseyev, Apr 27 2022

Extensions

Terms to a(300) in b-file from Zhi-Wei Sun, Dec 27 2016

a(301)-a(1200) in b-file from Charles R Greathouse IV, Sep 07 2017

a(1201)-a(1236) in b-file from Max Alekseyev, Apr 27 2022