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

%I #55 Mar 07 2020 14:55:56

%S 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,

%T 3,3,435,3,35805,3,765,5,3,7,2878785,3,3,3,20295,3,903,5,1035,3,141,3,

%U 116025,3,99,3,795,3,399,5,435,3,177,3,85180095,3,3,3,765,3,32361,3,45,5,11715,3

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

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

%C a(72) > 10^8.

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

%C From _David A. Corneth_, Aug 17 2015: (Start)

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

%C 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.

%C (End)

%C From _Robert Israel_, Sep 02 2015: (Start)

%C Both conjectures are true.

%C 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.

%C 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.

%C (End)

%H Robert Israel, <a href="/A260119/b260119.txt">Table of n, a(n) for n = 1..10000</a> [Terms 72 through 5000 were computed by _David A. Corneth_, Aug 17 2015]

%e Since 2^5-1 = 31 and 3^5-1 = 242 are relatively prime, a(5) = 3.

%e The divisors of 72 are 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72;

%e Adding one to each divisor gives 3, 4, 5, 7, 9, 10, 13, 19, 25, 37, 73;

%e The odd primes in this list are 3, 5, 7, 13, 19, 37, 73;

%e The product of these primes is 3 * 5 * 7 * 13 * 19 * 37 * 73 = 70050435;

%e Thus a(72) is of the form 70050435 * m.

%p f:= proc(n) local P, Q, M, k, kn;

%p P:= select(isprime, map(t -> t+1, numtheory:-divisors(n)) minus {2});

%p M:= convert(P,`*`);

%p Q:= 2^n - 1;

%p for k from M by 2*M do

%p kn:= k &^ n - 1 mod Q;

%p if igcd(kn, Q) = 1 then

%p return k

%p fi

%p od

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Sep 02 2015

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

%o (Sage)

%o def min_k(n):

%o g,k=2,0

%o while g!=1:

%o k=k+1

%o g=gcd(2^n-1,k^n-1)

%o return k

%o print([min_k(n) for n in [1..71]])

%o (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

%o (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);

%o 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

%Y Cf. A086892.

%K nonn

%O 1,2

%A _Tom Edgar_, Jul 17 2015