Results 1 to 4 of 4

Math Help - A problem about divisibility

  1. #1
    Super Member
    Joined
    Jan 2009
    Posts
    715

    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
    Last edited by simplependulum; July 29th 2010 at 09:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by simplependulum View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    715
    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 .

    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 ...
    Last edited by simplependulum; July 29th 2010 at 10:38 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility Problem(2)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 18th 2010, 02:02 PM
  2. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 8th 2010, 09:06 AM
  3. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: August 19th 2010, 09:21 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 24th 2010, 05:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 29th 2008, 06:13 AM

Search Tags


/mathhelpforum @mathhelpforum