login
Least positive integer k such that 3^n-1 and k^n-1 are relatively prime.
2

%I #22 Nov 20 2024 17:47:02

%S 2,2,2,10,2,28,2,10,2,22,10,910,2,2,2,170,2,3458,2,110,2,46,10,910,2,

%T 2,2,290,2,9548,2,340,10,2,22,639730,2,2,2,4510,2,1204,10,230,2,94,2,

%U 216580,2,22,2,530,2,3458,22,580,2,118,2,18928910

%N Least positive integer k such that 3^n-1 and k^n-1 are relatively prime.

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

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

%C When n>1, a(n) = 2 if and only if A260119(n) = 3.

%C From _Robert Israel_, Nov 20 2024: (Start)

%C a(n) <= a(m*n) for m >= 1.

%C If p is a prime factor of 3^n - 1 such that p-1 divides n, then a(n) is a multiple of p. (End)

%H Robert Israel, <a href="/A268081/b268081.txt">Table of n, a(n) for n = 1..10000</a>

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

%p f:= proc(n) local t,F,m,k,v;

%p t:= 3^n-1;

%p F:= select(isprime,map(`+`,numtheory:-divisors(n),1));

%p m:= convert(select(s -> t mod s = 0, F),`*`);

%p for k from m by m do

%p v:= k &^ n - 1 mod t;

%p if igcd(v, t) = 1 then return k fi

%p od

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Nov 20 2024

%t Table[k = 1; While[! CoprimeQ[3^n - 1, k^n - 1], k++]; k, {n, 59}] (* _Michael De Vlieger_, Jan 27 2016 *)

%o (Sage)

%o def min_k(n):

%o g, k=2, 0

%o while g!=1:

%o k=k+1

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

%o return k

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

%o (PARI) a(n) = {k=1; while( gcd(3^n-1, k^n-1)!=1, k++); k; }

%Y Cf. A086892, A260119.

%K nonn

%O 1,1

%A _Tom Edgar_, Jan 25 2016