

A297574


Least integer m > n such that 2^m == 2^n (mod m*n).


2



2, 6, 15, 6, 65, 8, 16, 12, 63, 30, 31, 16, 85, 26, 39, 20, 65, 72, 73, 24, 57, 32, 56, 32, 1025, 170, 513, 40, 85, 42, 91, 40, 93, 130, 155, 144, 73, 56, 111, 48, 341, 48, 127, 64, 585, 112, 2048, 60, 2107, 550, 195, 64, 157, 1026, 155, 80, 219, 86, 233, 64, 1261, 82, 171, 73, 257, 96, 595, 140, 201, 130, 281, 126
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

That a(n) exists for any n > 0 follows from the following theorem.
Theorem: For any integer a and positive integer n, there are infinitely many positive integers m such that a^m == a^n (mod m*n).
Proof. This is obvious for a = 0, 1, 1. Below we assume a > 1. Let v be the largest divisor of n coprime to a, and write n = u*v. By Dirichlet's theorem, there are infinitely many primes q > max{a,v} such that q == 1 (mod phi(v)), where phi(.) is Euler's totient function. Note that q, u and v are pairwise coprime. Set m = n*q. Then m*n = q*u^2*v^2. For any prime divisor p of a, clearly ord_p(a^ma^n) >= n >= 2*ord_p(n) since p^n >= n^2 except for the case p = 2 and n = 3. So u^2 divides a^ma^n. As q does not divide a, by Fermat's little theorem we have a^ma^n = a^n*(a^{(q1)n}1) == 0 (mod q). As v is coprime to a, and phi(v^2) = v*phi(v) divides (q1)*n = mn, by Euler's theorem we have a^m == a^n (mod v^2). Combining the above we see that m*n = q*u^2*v^2 divides a^ma^n. This ends the proof.
Conjecture: Let A and B be integers with A^2 not equal to 4*B. Let u(0) = 0, u(1) = 1, and u(n+1) = A*u(n)  B*u(n1) for n > 0. Also, let v(0) = 2, v(1) = A, and v(n+1) = A*v(n)  B*v(n1) for n > 0. Then, for any integer n > 0, there are infinitely many positive integers m such that u(m) == u(n) (mod m*n). Also, for any integer n > 0, there are infinitely many positive integers m such that v(m) == v(n) (mod m*n).
See also A297573 for a similar conjecture involving the Fibonacci sequence.


LINKS

Chai Wah Wu, Table of n, a(n) for n = 1..10000 (n = 1..1000 from ZhiWei Sun)


EXAMPLE

a(1) = 2 since 2^2  2^1 = 2*1.
a(2) = 6 since 2^6  2^2 = 60 = 5*(2*6).
a(3) = 15 since 2^15  2^3 = 32760 = 728*(3*15).
a(4) = 6 since 2^6  2^4 = 48 = 2*(4*6).


MATHEMATICA

Do[m=n+1; Label[aa]; If[Mod[2^m2^n, m*n]==0, Print[n, " ", m]; Goto[bb]]; m=m+1; Goto[aa]; Label[bb]; Continue, {n, 1, 80}]


PROG

(PARI) a(n) = my(m=n+1); while(1, if(Mod(2, m*n)^m==Mod(2, m*n)^n, return(m)); m++) \\ Felix FrÃ¶hlich, Jan 01 2018
(Python)
def A297574(n):
m = n+1
mn = m*n
while pow(2, m, mn) != pow(2, n, mn):
m += 1
mn += n
return m # Chai Wah Wu, Jan 04 2018


CROSSREFS

Cf. A000032, A000045, A000079, A247937, A297573.
Sequence in context: A222201 A130642 A133933 * A215081 A119416 A134891
Adjacent sequences: A297571 A297572 A297573 * A297575 A297576 A297577


KEYWORD

nonn


AUTHOR

ZhiWei Sun, Jan 01 2018


STATUS

approved



