Testing primes using factorials

AI Thread Summary
The discussion explores the relationship between factorials and prime numbers, specifically through the equations n!/n^2=x and n-1!/n=x. It suggests that if x is a natural number, n is composite, while if x is a non-natural number, n is prime, except for the case of 4. A key argument is presented that if n is prime, then (n-1)!/n cannot be an integer, reinforcing the connection between factorials and primality. The method discussed is deemed impractical for testing large primes, especially given the demands of modern encryption systems. Overall, while the approach is interesting, it lacks efficiency for large number testing.
binbots
Messages
170
Reaction score
3
As far as I can tell for the equation n!/n^2=x or n-1!/n=x, if x is a natural number then it seems n is composite. If x is a non-natural number then it is prime (excluding 4). I am aware that this is not very practical since I am using factorials and the numbers get very large. But it still seems interesting non the less. As of now I can only test up to n=86. Is there a easier way to check very large numbers? A better on line calculator perhaps? Or is all this something already known and/or disproving?

I also noticed that the remainder left over from each prime number increases in value from .5- to .999999... Since these remainders are generated by primes they seem to grow in prime proportions.
 
Last edited:
Mathematics news on Phys.org
binbots said:
As far as I can tell for the equation n!/n^2=x or n-1!/n=x, if y is a natural number then it seems n is composite. If y is a non-natural number then it is prime (excluding 4).
I'm assuming you mean x throughout instead of y. You're trying to show that (n-1)!/n is a whole number if and only if n is not prime. There are lots of ways to play around with this statement, but I'll just leave some food for thought here. Assume that n is prime. This means that none of the numbers 2, 3, ..., (n-1) divide it. But of course, n doesn't divide any number less than it, and it doesn't divide their product either (by the fundamental theorem of arithmetic). So if n is prime, then n and (n-1)! are relatively prime (greatest common divisor = 1), meaning that the fraction (n-1)!/n is irreducible: that is, it can never be an integer.

I've just outlined an argument for "If n is prime, then (n-1)!/n is not an integer," which is equivalent to the contrapositive statement, "If (n-1)!/n is an integer, then n is not prime." The converse statement, "If n is not prime, then (n-1)!/n is an integer," is a little trickier to prove, but I'll let you take a crack at it first.
 
Thanks for the correction. As for your food for thought I see now what I did. Makes sense. Seems I confused myself into some circular logic.
 
This would be a much easier fraction to deal with:

With the (n-1)!/n fraction, you would be pretty much checking all the numbers that could not divide n. For example, if we picked 101, we would be checking all numbers up to 100, but with the fraction above, we would be checking only up to 10, which is the square root of 100 rounded down to the nearest integer [floor function] (it already is an integer, so 10).
also,
TeethWhitener said:
I've just outlined an argument for "If n is prime, then (n-1)!/n is not an integer," which is equivalent to the contrapositive statement, "If (n-1)!/n is an integer, then n is not prime." The converse statement, "If n is not prime, then (n-1)!/n is an integer," is a little trickier to prove, but I'll let you take a crack at it first.
(I deleted the first part) The converse statement just basically says that if n isn't prime, a combination of factors smaller than n multiply up to n with each factor not repeated, which is true for all composite numbers (excluding 4).
 
I get it now. Thanks. When I couldn't find anything about this on line I thought It was either wrong or just uninteresting. Glad to know I am not wrong. Sad to hear it is just uninteresting. lol
 
This method is more of an inefficient and therefore unpractical method of testing primes. With the RSA encryption system being used, computers are required to test primes up to hundreds of digits long, and with this method, even the floor-square root factorial, which would be around [15 to 100's] factorial.
However, another method like this but also impractical is to take the LCM of all the numbers up to the floor of the square root of n-1, and putting that over n. (so if it's an integer)
 
  • Like
Likes binbots
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Back
Top