cp's OEIS Frontend

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

%I A297574 #30 Jan 04 2018 11:56:31
%S A297574 2,6,15,6,65,8,16,12,63,30,31,16,85,26,39,20,65,72,73,24,57,32,56,32,
%T A297574 1025,170,513,40,85,42,91,40,93,130,155,144,73,56,111,48,341,48,127,
%U A297574 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
%N A297574 Least integer m > n such that 2^m == 2^n (mod m*n).
%C A297574 That a(n) exists for any n > 0 follows from the following theorem.
%C A297574 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).
%C A297574 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^m-a^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^m-a^n. As q does not divide a, by Fermat's little theorem we have a^m-a^n = a^n*(a^{(q-1)n}-1) == 0 (mod q). As v is coprime to a, and phi(v^2) = v*phi(v) divides (q-1)*n = m-n, 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^m-a^n. This ends the proof.
%C A297574 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(n-1) for n > 0. Also, let v(0) = 2, v(1) = A, and v(n+1) = A*v(n) - B*v(n-1) 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).
%C A297574 See also A297573 for a similar conjecture involving the Fibonacci sequence.
%H A297574 Chai Wah Wu, <a href="/A297574/b297574.txt">Table of n, a(n) for n = 1..10000</a> (n = 1..1000 from Zhi-Wei Sun)
%e A297574 a(1) = 2 since 2^2 - 2^1 = 2*1.
%e A297574 a(2) = 6 since 2^6 - 2^2 = 60 = 5*(2*6).
%e A297574 a(3) = 15 since 2^15 - 2^3 = 32760 = 728*(3*15).
%e A297574 a(4) = 6 since 2^6 - 2^4 = 48 = 2*(4*6).
%t A297574 Do[m=n+1; Label[aa]; If[Mod[2^m-2^n, m*n]==0, Print[n, " ", m]; Goto[bb]]; m=m+1; Goto[aa]; Label[bb]; Continue, {n, 1, 80}]
%o A297574 (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
%o A297574 (Python)
%o A297574 def A297574(n):
%o A297574     m = n+1
%o A297574     mn = m*n
%o A297574     while pow(2,m,mn) != pow(2,n,mn):
%o A297574         m += 1
%o A297574         mn += n
%o A297574     return m # _Chai Wah Wu_, Jan 04 2018
%Y A297574 Cf. A000032, A000045, A000079, A247937, A297573.
%K A297574 nonn
%O A297574 1,1
%A A297574 _Zhi-Wei Sun_, Jan 01 2018