login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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

LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 2..1200 (2..300 from Zhi-Wei 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. - Zhi-Wei 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^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

CROSSREFS

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 11:18 EST 2019. Contains 329144 sequences. (Running on oeis4.)