Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #72 Apr 27 2022 20:16:29
%S 3,7,5,31,7,127,17,73,11,23,13,8191,43,31,17,131071,19,524287,41,127,
%T 23,47,241,601,2731,262657,29,233,31,2147483647,257,599479,43691,71,
%U 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
%N Smallest prime factor of 2^n - 1 having the form k*n + 1.
%C The values of k are in A186283.
%C From _Zhi-Wei Sun_, Dec 27 2016: (Start)
%C 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.
%C Conjecture: a(n) exists for any integer n > 1 (verified for n = 2..300). (End)
%C 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
%C For prime p, a(p) = 2p + 1 if and only if p is a Lucasian prime (A002515). - _Thomas Ordowski_, Sep 08 2017
%H <a href="/A186522/b186522.txt">Table of n, a(n) for n = 2..1236</a>
%H GIMPS (Prime95), <a href="http://www.mersenne.ca/prp.php">Mersenne exponent cofactor probable prime PRP</a>.
%F a(p - 1) = p for odd prime p. - _Thomas Ordowski_, Sep 04 2017
%F A002326((a(n)-1)/2) divides n for all n > 1. - _Thomas Ordowski_, Sep 07 2017
%F a(n) = A186283(n) * n + 1. - _Max Alekseyev_, Apr 27 2022
%e 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.
%e 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.
%e 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
%t Table[p = First/@FactorInteger[2^n - 1]; Select[p, Mod[#1, n] == 1 &, 1][[1]], {n, 2, 60}]
%o (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
%o (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
%Y Cf. A000040, A000225, A060443 (all prime factors of 2^n-1).
%K nonn
%O 2,1
%A _T. D. Noe_, Feb 23 2011
%E Terms to a(300) in b-file from _Zhi-Wei Sun_, Dec 27 2016
%E a(301)-a(1200) in b-file from _Charles R Greathouse IV_, Sep 07 2017
%E a(1201)-a(1236) in b-file from _Max Alekseyev_, Apr 27 2022