Infinitely many positive integers $n$ such that $n^2+1 \mid 1 \cdot 2 \cdot 5 \cdot 10 \cdots ((n-1)^2+1)$

Prove that there exist infinitely many positive integers $n$ such that $$n^2+1 \mid 1 \cdot 2 \cdot 5 \cdot 10 \cdots ((n-1)^2+1).$$

We need to prove that there are infinitely many $n$ such that $\prod_{m=0}^{n-1}(m^2+1)$ is divisible by $n^2+1$. Some examples I found for when it is divisible are $n = 3,7,8,13,17,18,21$, but I didn't see how to find infinitely many.

Solution 1:

There are infinitely many integer solutions to $$ (1+u^2)(1+v^2) = (1+w^2) $$ with $u,v,w>0.$ Any such $w$ serves as an $n$ in the question, as both $u,v<w.$

Tea is ready.

For example, fix $u=1,$ we get $2 + 2 v^2 = 1 + w^2,$ $$ w^2 - 2 v^2 = 1. $$

Fix $u=2,$ we get $5 + 5 v^2 = 1 + w^2,$ $$ w^2 - 5 v^2 = 4. $$ The $w$ are every other Lucas number, $3,7,18,47, 123,$ and $w_{n+2} = 3 w_{n+1} - w_n.$

If we fix $u=3,$ we get $$ w^2 - 10 v^2 = 9; $$ there are three families of $w,$ one begins $7, 253, 9607, 364813$ and $w_{n+2} = 38 w_{n+1} - w_n.$

jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
  Automorphism matrix:  
    19   60
    6   19
  Automorphism backwards:  
    19   -60
    -6   19

  19^2 - 10 6^2 = 1

 w^2 - 10 v^2 = 9

Wed Jun 21 18:07:53 PDT 2017

w:  7  v:  2 ratio: 3.5  SEED   KEEP +- 
w:  13  v:  4 ratio: 3.25  SEED   BACK ONE STEP  7 ,  -2
w:  57  v:  18 ratio: 3.16667  SEED   BACK ONE STEP  3 ,  0
w:  253  v:  80 ratio: 3.1625
w:  487  v:  154 ratio: 3.16234
w:  2163  v:  684 ratio: 3.16228
w:  9607  v:  3038 ratio: 3.16228
w:  18493  v:  5848 ratio: 3.16228
w:  82137  v:  25974 ratio: 3.16228
w:  364813  v:  115364 ratio: 3.16228
w:  702247  v:  222070 ratio: 3.16228
w:  3119043  v:  986328 ratio: 3.16228
w:  13853287  v:  4380794 ratio: 3.16228
w:  26666893  v:  8432812 ratio: 3.16228
w:  118441497  v:  37454490 ratio: 3.16228

Wed Jun 21 18:09:53 PDT 2017

 w^2 - 10 v^2 = 9

jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$

If we fix $u=4,$ we get $$ w^2 - 17 v^2 = 16; $$ there are three families of $w,$ one begins $13, 837, 55229, 3644277$ and $w_{n+2} = 66 w_{n+1} - w_n.$

jagy@phobeusjunior:~$ 
jagy@phobeusjunior:~$  ./Pell_Target_Fundamental
  Automorphism matrix:  
    33   136
    8   33
  Automorphism backwards:  
    33   -136
    -8   33

  33^2 - 17 8^2 = 1

 w^2 - 17 v^2 = 16

Thu Jun 22 11:41:39 PDT 2017

w:  13  v:  3 ratio: 4.33333  SEED   KEEP +- 
w:  21  v:  5 ratio: 4.2  SEED   BACK ONE STEP  13 ,  -3
w:  132  v:  32 ratio: 4.125  SEED   BACK ONE STEP  4 ,  0
w:  837  v:  203 ratio: 4.12315
w:  1373  v:  333 ratio: 4.12312
w:  8708  v:  2112 ratio: 4.12311
w:  55229  v:  13395 ratio: 4.12311
w:  90597  v:  21973 ratio: 4.12311
w:  574596  v:  139360 ratio: 4.12311
w:  3644277  v:  883867 ratio: 4.12311
w:  5978029  v:  1449885 ratio: 4.12311
w:  37914628  v:  9195648 ratio: 4.12311

Thu Jun 22 11:43:39 PDT 2017

 w^2 - 17 v^2 = 16

jagy@phobeusjunior:~$ 

The way i currently have the program, a solution with $v=0$ is not listed. For this problem, we are looking at $w^2 - (1+u^2) v^2 = u^2,$ so $(u,0)$ is one of the solutions. Indeed, we can take all solutions to $w^2 - (1+u^2) v^2 = 1,$ and just multiply both $w,v$ by $u.$ But there are also families of solutions that are not divisible by $u.$ There are two such families guaranteed, containing ( for $u > 1$) $$ \left( u^2 - u + 1 \right)^2 - \left( 1 + u^2 \right) (u-1)^2 = u^2, $$ $$ \left( u^2 + u + 1 \right)^2 - \left( 1 + u^2 \right) (u+1)^2 = u^2. $$ Oh, the "automorphism matrix" of the form $x^2 - (1+u^2)y^2$ is $$ \left( \begin{array}{rr} 2 u^2 + 1 & 2 u^3 + 2 u \\ 2 u & 2 u^2 + 1 \end{array} \right) $$ The determinant is $1$ and the trace is $4 u^2 + 2,$ which, by Cayley-Hamilton, is where we get the coefficients $6, 18, 38, 66$ above, where I probably did not explicitly write the $6$ or the $18.$ I see what happened: for $u=2,$ we get a stroke of luck and the numbers combine as Lucas numbers, so we can talk about a single orbit instead of three or more.

Solution 2:

Since $(m-i)(m-1+i)=\left(m^2-m+1\right)+i$, multiplying both sides by their conjugates gives $$ (m^2-m+1)^2+1=\left(m^2+1\right)\left((m-1)^2+1\right)\tag{1} $$ For $m\ge2$, we have that $n=m^2-m+1\gt m$. Therefore, $(1)$ shows that $$ \left.n^2+1\,\,\middle|\,\,\prod_{k=0}^{n-1}\left(k^2+1\right)\right.\tag{2} $$

Solution 3:

I conjecture that $n=2^{2k+1}$ is always a solution. We have that $$2^{4k+2}+1=(2^{2k+1}+1)^2-2^{2k+2}=(2^{2k+1}-2^{k+1}+1)(2^{2k+1}+2^{k+1}+1)$$ Now we can pick $m=2^{k+1}+1$ then $$m^2+1=2^{2k+2}+2^{k+2}+2=2(2^{2k+1}+2^{k+1}+1)$$ and $m=2^{k+1}-1$ then $$m^2+1=2^{2k+2}-2^{k+2}+2=2(2^{2k+1}-2^{k+1}+1)$$ And both $m$'s are obviously part of the RHS product (if $k>1$) the conjecture is true hence infinitely many solutions.