Results 1 to 4 of 4

Thread: 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 $\displaystyle n $ such that $\displaystyle n^2+1 | n! $ .


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

    Since the sequence contains the 'very large' integers ( $\displaystyle 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; Jul 29th 2010 at 08: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 $\displaystyle 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 $\displaystyle m>2 $ . Choose $\displaystyle p = 5 $ , since $\displaystyle 5 \equiv 1 \bmod{4} $ we can find solution in the equation : $\displaystyle x^2 + 1 \equiv 0 \bmod{5} $ . $\displaystyle x = 2 $ is solution then use this result to solve $\displaystyle x^2 + 1 \equiv 0 \bmod{25} \bmod{125} $ . I find that $\displaystyle 7^2 + 1 \equiv 0 \bmod{25} $ and $\displaystyle 57^2 + 1 \equiv 0 \bmod{125} $ .


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

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

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

    I am not sure if this is work :

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


    There is a problem , it is we are not sure whether there is enough $\displaystyle 5 $ to be divided by $\displaystyle 5^m $ and $\displaystyle N $ ...
    Last edited by simplependulum; Jul 29th 2010 at 09: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: Sep 18th 2010, 01:02 PM
  2. problem with divisibility
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 8th 2010, 08:06 AM
  3. A divisibility problem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Aug 19th 2010, 08:21 PM
  4. divisibility problem?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 24th 2010, 04:18 AM
  5. help this divisibility problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 29th 2008, 05:13 AM

Search Tags


/mathhelpforum @mathhelpforum