# 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.

• Listed twice in the Online Encyclopedia of Number Sequences: oeis.org/A002312, oeis.org/A252496 – John Wayland Bales Jun 21 '17 at 22:16
• oeis.org/A002312 – Santiago Jun 21 '17 at 22:16
• Looks like you want to find a special form of $n^2+1$ that factors algebraically. – marty cohen Jun 21 '17 at 22:44
• @martycohen: we may probably achieve a parametric solution by considering $n$ as a Fibonacci or Lucas number, due to $$F_{2n-1}F_{2n+1} = F_{2n}^2+1$$ Have you already attempted that? – Jack D'Aurizio Jun 21 '17 at 23:12

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.$

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.

• You spoiled all the fun and I prefer beer on tea. This is a painful (+1) :D – Jack D'Aurizio Jun 21 '17 at 23:55

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}$$

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.