A problem about divisibility

Printable View

July 29th 2010, 08:07 PM
simplependulum

A problem about divisibility

Show that there exists infinitely many positive integers $n$ such that $n^2+1 | n!$ .

I am begging for seeing all $n < 1000$ satisfying the above requirement . The job should belong to computer but i have no idea how to design a computer programme to look for the numbers .

Here's my attempt to the proof :

Let $a_n$ be the sequence with $a_1 = 21 ~,~ a_{n+1} = a_n^2 - a_n + 1$ . Then i find that $a_n \equiv 1 \bmod{5} ~,~ n\geq 1$ . Moreover , interestingly i can factorize $a_{n+1}^2 + 1$ into $( a_n^2 + 1 ) ( (a_n - 1 )^2 + 1 )$ . But $(a_n-1)^2 + 1 < a_{n+1}$ and $(a_n-1)^2 + 1$ is prime to $a_n^2 + 1$ . Therefore , if $a_n^2 + 1 | (a_n)!$ , we also have $a_{n+1}^2 + 1 | (a_{n+1})!$ then it finishes the proof by induction .

Since the sequence contains the 'very large' integers ( $a_4 = 31265489221$ !) , i wonder if it is true that the numbers could hardly be found in the integer line .... But i think that is not true , i believe by solving quadratic congruences we can construct many such integers !

Thank you
July 29th 2010, 08:36 PM
undefined

Quote:

Originally Posted by simplependulum

I am begging for seeing all $n < 1000$ satisfying the above requirement . The job should belong to computer but i have no idea how to design a computer programme to look for the numbers .

I'll just look at what seems to me the "easy" part of what you wrote. PARI/GP effortlessly executes

Code:

for(n=2,999,if(n!%(n^2+1)==0,print(n)))

in 78 ms user time on my system. The first few are 18, 21, 38, 43, 47. The last few are 965, 970, 993, 996, 999.

I guess Java with BigInteger or C++ with GMP would be similarly fast, haven't tried it. Maybe I will in a bit just for fun.
July 29th 2010, 08:57 PM
undefined

Java:

Code:

import java.math.BigInteger; public class SquarePlus1DivFactorial { public static void main(String[] args) { long t = time(); int i, sq, inc; BigInteger fact = BigInteger.ONE; for(i = 2, sq = 4, inc = 5; i < 1000; i++, sq+=inc, inc+=2) { fact = fact.multiply(BigInteger.valueOf(i)); if(fact.mod(BigInteger.valueOf(sq+1)).equals(BigInteger.ZERO)) System.out.print(i + ", "); } System.out.println(); System.out.println("Elapsed: " + (time()-t)/1000.0 + " seconds"); } static long time() { return System.currentTimeMillis(); } }

18, 21, 38, 43, 47, 57, 68, 70, 72, 73, 83, 99, 111, 117, 119, 123, 128, 132, 133, 142, 157, 172, 173, 174, 182, 185, 191, 192, 193, 200, 211, 212, 216, 233, 237, 239, 242, 251, 253, 255, 265, 268, 273, 278, 293, 294, 302, 305, 307, 313, 319, 322, 327, 336, 337, 338, 342, 343, 351, 360, 377, 378, 394, 395, 401, 403, 408, 411, 418, 421, 431, 437, 438, 443, 447, 448, 450, 460, 463, 467, 477, 485, 498, 499, 500, 507, 509, 512, 515, 524, 538, 552, 557, 560, 562, 565, 568, 577, 580, 593, 599, 601, 606, 612, 616, 621, 642, 648, 655, 657, 659, 660, 663, 675, 682, 684, 687, 693, 697, 701, 703, 717, 731, 743, 746, 748, 757, 767, 771, 772, 776, 782, 785, 787, 788, 795, 798, 800, 802, 805, 807, 811, 813, 818, 822, 829, 831, 837, 843, 850, 853, 857, 863, 871, 882, 889, 893, 905, 911, 914, 919, 922, 924, 931, 945, 948, 965, 970, 993, 996, 999

Elapsed: 0.033 seconds
July 29th 2010, 09:18 PM
simplependulum

Thanks , just few words my problem is solved , I can see that there are many integers in that range , this makes another question : is there any way to construct most of them , obviously my sequence fails to do so (Crying).

I have just thought of a way but i couldn't prove it valids for any $m>2$ . Choose $p = 5$ , since $5 \equiv 1 \bmod{4}$ we can find solution in the equation : $x^2 + 1 \equiv 0 \bmod{5}$ . $x = 2$ is solution then use this result to solve $x^2 + 1 \equiv 0 \bmod{25} \bmod{125}$ . I find that $7^2 + 1 \equiv 0 \bmod{25}$ and $57^2 + 1 \equiv 0 \bmod{125}$ .

Therefore , $57^2 + 1 = 2\cdot 5^3 \cdot 13 | 57!$

Also $68^2 + 1 \equiv 0 \bmod{125}$ and $68^2 + 1 = 5^3(37) | 68!$ . These are two integers satisfying the condition .

I choose $p = 5$ because $5$ is small so $n !$ may contain sufficiently large number of it as factors . By doing the congruence $x^2 + 1 \equiv 0 \bmod{5^m}$ , the integer $\frac{x^2 + 1 }{5^m}$ should be small enough so $x^2 + 1 | x!$ .

I am not sure if this is work :

Let $x^2 + 1 \equiv 0 \bmod{5^m} ~~,~ m > 2$ where $x$ numerically lying between $1$ and $p^m - 1$ . Then we have $x^2 + 1 | x!$ , because $x^2 + 1 = 5^m N$ for some integers $N$ and $x^2 - 5^m x + 1 = 5^m ( N -x )$ . We have when $0 \leq x \leq 5^m$ , $x^2 - 5^m x + 1 \leq 1$ .When $x = 1 ~,~ x= 5^m - 1$ , the value of the equation is $2 - 5^m < 0$ . Therefore , for $1 \leq x \leq 5^m - 1$ , $x^2 - 5^m x + 1$ is negative , thus we have $N < x$ . $x!$ should be divisible by $N$ and we have $x^2 + 1 | x!$ .

There is a problem , it is we are not sure whether there is enough $5$ to be divided by $5^m$ and $N$ ...