login
Smallest m_0 such that A118106(m_0) = n; smallest m_0 such that if we write m_0 = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) = n, where ord(a,r) is the multiplicative order of a modulo r.
0

%I #9 Nov 04 2019 00:58:07

%S 1,6,14,10,55,18,203,34,146,22,46,26,689,86,302,51,5759,38,955,50,98,

%T 69,94,288,505,5462,327,58,466,77,9305,384,5447,309,142,74,446,2933,

%U 158,246,3403,129,862,115,543,141,4702,119,5713,453,206,106,5671,162,605,928,687,118

%N Smallest m_0 such that A118106(m_0) = n; smallest m_0 such that if we write m_0 = Product_{i=1..t} p_i^e_i, then lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) = n, where ord(a,r) is the multiplicative order of a modulo r.

%C For n != 1, 6, a(n) <= 2*A112927(n): suppose n != 1, 6, by Zsigmondy's theorem, 2^n - 1 has at least one primitive factor p. Here a primitive factor p means that ord(2,p) = n, where ord(a,r) is the multiplicative order of a modulo r. So we have A118106(2p) = lcm(ord(p,2),ord(2,p)) = lcm(1,n) = n. Specially, we have A118106(2*A112927(n)) = n for n != 1, 6.

%C There is another way to construct m such that A118106(m) = n > 1 (and usually this way generates smaller m's than the way above): let q be any prime factor of n, again, by Zsigmondy's theorem, q^n - 1 has at least one primitive factor p unless (n,q) = (6,2). Note that q^(p-1) == 1 (mod p), so q^gcd(p-1,n) == 1 (mod p). But n is the smallest positive number such that q^n == 1 (mod p), so gcd(p-1,n) = n. So we have A118106(pq) = lcm(ord(p,q),ord(q,p)) = lcm(1,n) = n. For example, if n = 5, then q = 5, p = 11, m = 55 (the way above gives A118106(62) = 5); if n = 7, then q = 7, p = 29, m = 203 (the way above gives A118106(254) = 7); if n = 13, then q = 13, p = 53, m = 689 (the way above gives A118106(16382) = 13). This gives a(q) <= q*A212552(q) for primes q.

%e A118106(203) = 7; for any m < 203, A118106(m) is not equal to 7, so a(7) = 203.

%o (PARI) a(n) = for(k=1, oo, if(A118106(k)==n, return(k))) \\ See A118106 for its program

%Y Cf. A118106, A112927, A212552.

%K nonn

%O 1,2

%A _Jianing Song_, Nov 03 2019