Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Testing primes using factorials

  1. Dec 29, 2015 #1
    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: Dec 29, 2015
  2. jcsd
  3. Dec 29, 2015 #2

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  4. Dec 29, 2015 #3
    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.
     
  5. Dec 29, 2015 #4
    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,
    (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).
     
  6. Dec 30, 2015 #5
    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
     
  7. Jan 3, 2016 #6
    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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook