11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Listed twice in the Online Encyclopedia of Number Sequences: oeis.org/A002312, oeis.org/A252496 $\endgroup$ – John Wayland Bales Jun 21 '17 at 22:16
  • $\begingroup$ oeis.org/A002312 $\endgroup$ – Santiago Jun 21 '17 at 22:16
  • $\begingroup$ Looks like you want to find a special form of $n^2+1$ that factors algebraically. $\endgroup$ – marty cohen Jun 21 '17 at 22:44
  • $\begingroup$ @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? $\endgroup$ – Jack D'Aurizio Jun 21 '17 at 23:12
10
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.