|
| |
|
|
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^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.
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).
See also A297573 for a similar conjecture involving the Fibonacci sequence.
|
|
|
LINKS
|
|
|
|
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^m-2^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)
m = n+1
mn = m*n
while pow(2, m, mn) != pow(2, n, mn):
m += 1
mn += n
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
