

A186522


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


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

The values of k are in A186283.
From ZhiWei Sun, Dec 27 2016: (Start)
For any odd prime p, by Fermat's little theorem p = (p1) + 1 divides 2^(p1)  1, and it is wellknown 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 p1. 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


LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 2..1200 (2..300 from ZhiWei Sun)
GIMPS (Prime95), Mersenne exponent cofactor probable prime PRP.


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


EXAMPLE

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.  ZhiWei Sun, Dec 27 2016


MATHEMATICA

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


PROG

(PARI) a(n)=my(s=if(n%2, 2*n, n)); forstep(p=s+1, 2^n1, 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^n1)[, 1]); for(i=1, #f, if(f[i]%n==1, return(f[i]))) \\ Charles R Greathouse IV, Sep 07 2017


CROSSREFS

Cf. A000040, A000225, A060443 (all prime factors of 2^n1).
Sequence in context: A097406 A064078 A292015 * A048857 A005420 A212953
Adjacent sequences: A186519 A186520 A186521 * A186523 A186524 A186525


KEYWORD

nonn


AUTHOR

T. D. Noe, Feb 23 2011


STATUS

approved



