A260119 a(n) is the least positive integer k such that 2^n-1 and k^n-1 are relatively prime.

1, 3, 3, 15, 3, 21, 3, 45, 3, 99, 5, 1365, 3, 3, 3, 765, 3, 399, 3, 1815, 3, 69, 5, 1365, 3, 3, 3, 435, 3, 35805, 3, 765, 5, 3, 7, 2878785, 3, 3, 3, 20295, 3, 903, 5, 1035, 3, 141, 3, 116025, 3, 99, 3, 795, 3, 399, 5, 435, 3, 177, 3, 85180095, 3, 3, 3, 765, 3, 32361, 3, 45, 5, 11715, 3

Offset: 1

Author

Tom Edgar, Jul 17 2015

Keywords

• nonn

Comments

Note that (2^n-1)^n-1 is always relatively prime to 2^n-1.

a(72) > 10^8.

According to the conjecture given in A086892, a(n) = 3 infinitely often.

From David A. Corneth, Aug 17 2015: (Start)

Conjecture 1: a(n) is never divisible by 2.

Conjecture 2: a(n) is of the form q * m where q is the product of all odd primes that are one more than a divisor of n.

(End)

From Robert Israel, Sep 02 2015: (Start)

Both conjectures are true.

Since (2k)^n - 1 = (k^n)*(2^n - 1) + (k^n - 1), GCD((2k)^n - 1, 2^n-1) = GCD(k^n-1, 2^n-1). Thus a(n) is always odd.

If p is an odd prime such that p-1 divides n, then k^n - 1 is divisible by p for all k coprime to p (and in particular k=2). Thus a(n) must be divisible by p, and thus by the product of all such p.

(End)

Examples

			Since 2^5-1 = 31 and 3^5-1 = 242 are relatively prime, a(5) = 3.
The divisors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72;
Adding one to each divisor gives 3, 4, 5, 7, 9, 10, 13, 19, 25, 37, 73;
The odd primes in this list are 3, 5, 7, 13, 19, 37, 73;
The product of these primes is 3 * 5 * 7 * 13 * 19 * 37 * 73 = 70050435;
Thus a(72) is of the form 70050435 * m.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000 [Terms 72 through 5000 were computed by _David A. Corneth_, Aug 17 2015]

Crossrefs

Cf. A086892.

Programs

Maple

f:= proc(n) local P, Q, M, k, kn;
P:= select(isprime, map(t -> t+1, numtheory:-divisors(n)) minus {2});
M:= convert(P,`*`);
Q:= 2^n - 1;
for k from M by 2*M do
  kn:= k &^ n - 1 mod Q;
  if igcd(kn, Q) = 1 then
    return k
  fi
od
end proc:
map(f, [$1..100]); # Robert Israel, Sep 02 2015

Mathematica

Table[k = 1; While[! CoprimeQ[2^n - 1, k^n - 1], k++]; k, {n, 59}] (* Michael De Vlieger, Sep 01 2015 *)

PARI

a(n) = {my(k=1, pt = 2^n-1); while (gcd(pt, k^n-1) != 1, k++); k;} \\ Michel Marcus, Jul 17 2015 && Jan 27 2016

PARI

conjecture_a(n) = {my(d=divisors(n)); v=select(x->isprime(x+1),select(y->y%2==0,d)); v+= vector(#v,i,1); p=prod(i=1,#v,v[i]); if(p==1&&n!=1,p=3);
forstep(i=1, p, 2,if(gcd((p * i)^n-1, 2^n-1)==1, return(p*i))); for(i=1,n,if(gcd(p^n-1,2^n-1) == 1, return(p), p=nextprime(p+1))); forstep(i=1,100000,2,if(gcd((i)^n-1,2^n-1)==1,return(i)))} \\ David A. Corneth, Sep 01 2015

Sage

def min_k(n):
    g,k=2,0
    while g!=1:
        k=k+1
        g=gcd(2^n-1,k^n-1)
    return k
print([min_k(n) for n in [1..71]])