A186522 - 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