login
Least integer m>1 such that 1^2,2^2,...,n^2 are pairwise incongruent modulo 2^m-1.
1

%I #15 Dec 06 2018 16:35:06

%S 2,3,3,5,5,5,5,5,5,5,5,5,5,5,5,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,

%T 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,13,13,13,

%U 13,13,13,13

%N Least integer m>1 such that 1^2,2^2,...,n^2 are pairwise incongruent modulo 2^m-1.

%C Conjecture: a(n) is the least prime p such that 2^p-1 is a Mersenne prime greater than 2n-1.

%C This conjecture implies that there are infinitely many Mersenne primes.

%C Zhi-Wei Sun also conjectured that for each n>17 the least Fibonacci number modulo which 1^2,2^2,...,n^2 are pairwise incongruent is just the first Fibonacci prime greater than 2n-1.

%C This phenomenon might happen for some other Lucas sequences u_0,u_1,... given by u_0 = 0, u_1 = 1, and u_{k+1} = A*u_k-B*u_{k-1} for k>0, with A>0 and B (nonzero) relatively prime and A^2 > 4B.

%H Zhi-Wei Sun, <a href="/A225577/b225577.txt">Table of n, a(n) for n = 1..5000</a>

%H Zhi-Wei Sun, <a href="http://arxiv.org/abs/1304.5988">The least modulus for which consecutive polynomial values are distinct</a>, arXiv:1304.5988 [math.NT], 2013-2015.

%H Zhi-Wei Sun, <a href="https://doi.org/10.1016/j.jnt.2013.02.003">On functions taking only prime values</a>, J. Number Theory, 133 (2013), 2794-2812.

%e a(4)=5 since 1^2,2^2,3^2,4^2 are incongruent modulo 2^5-1=31, but 1^2==4^2 (mod 2^4-1), 3^2==4^2 (mod 2^3-1) and 2^2==4^2 (mod 2^2-1).

%t R[n_,m_]:=Union[Table[Mod[k^2,m],{k,1,n}]]

%t s=2

%t Do[Do[If[Length[R[n,2^m-1]]==n,s=m;Print[n," ",m];Goto[aa]],{m,s,100000}];

%t Print[n," ",counterexample];Label[aa];Continue,{n,1,20}]

%Y Cf. A000043, A000668, A001605, A005478.

%K nonn

%O 1,1

%A _Zhi-Wei Sun_, May 10 2013