Thread: A problem about divisibility

Show that there exists infinitely many positive integers such that .


I am begging for seeing all 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 be the sequence with . Then i find that . Moreover , interestingly i can factorize into . But and is prime to . Therefore , if , we also have then it finishes the proof by induction .

Since the sequence contains the 'very large' integers ( !) , 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

Originally Posted by simplependulum

I am begging for seeing all 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.

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

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 . Choose , since we can find solution in the equation : . is solution then use this result to solve . I find that and .


Therefore ,

Also and . These are two integers satisfying the condition .

I choose because is small so may contain sufficiently large number of it as factors . By doing the congruence , the integer should be small enough so .

I am not sure if this is work :

Let where numerically lying between and . Then we have , because for some integers and . We have when , .When , the value of the equation is . Therefore , for , is negative , thus we have . should be divisible by and we have .


There is a problem , it is we are not sure whether there is enough to be divided by and ...