×

A primality test

Sebastian Garth wrote in sci.math (his original article is here) that an integer number n is prime iff

«math xmlns=¨http://www.w3.org/1998/Math/MathML¨»«mfenced close=¨]¨ open=¨[¨»«mrow»«mfenced»«mrow»«mfenced»«mrow»«munderover»«mo»§#8721;«/mo»«mrow»«mi»i«/mi»«mo»=«/mo»«mn»1«/mn»«/mrow»«mi»n«/mi»«/munderover»«msup»«mi»i«/mi»«mrow»«mi»n«/mi»«mo»-«/mo»«mn»1«/mn»«/mrow»«/msup»«/mrow»«/mfenced»«mi»mod«/mi»«mo»§nbsp;«/mo»«mfenced»«mfrac»«mrow»«mi»n«/mi»«mo»§#183;«/mo»«mo»(«/mo»«mi»n«/mi»«mo»+«/mo»«mn»1«/mn»«mo»)«/mo»«/mrow»«mn»2«/mn»«/mfrac»«/mfenced»«/mrow»«/mfenced»«mo»+«/mo»«mn»1«/mn»«/mrow»«/mfenced»«mi»mod«/mi»«mo»§nbsp;«/mo»«mi»n«/mi»«mo»§nbsp;«/mo»«mo»=«/mo»«mo»§nbsp;«/mo»«mn»0«/mn»«/math» .

The double module makes it such a weird statement that I just had to check it... and it seems to be true!

Just write your prime candidate and click on the = sign:

The above program is useful only for n up to 2,000 , since computing the powers results in huge numbers and it runs ut of time. Now, if we compute the powers modulo n·(n+1)/2 from the beginning, we can save a lot of time; this other program can go up to n=250,000: