1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Elementary number theory - proving primality

  1. Oct 3, 2011 #1
    1. The problem statement, all variables and given/known data

    if an integer n >= 2 and if n divides ((n-1)! +1) prove that n is prime.


    2. Relevant equations

    a divides b iff b = ma for integers a, b, m.


    3. The attempt at a solution

    by contrapositive:

    Assume n is not prime. Then we have by definition of divisibility
    ((n-1)*(n-2)*...*2) + 1 = n*a for integer a
    but since n is greater than all of the individual factors of (n-1)!, then clearly it shares no factors with the LHS above, so we have a contradiction. thus, n is prime.

    This seems correct to me, but Im unsure about the part where I say clearly it shares no factors with the LHS. I would think that it doesnt, but am not 100% sure. Can somebody tell me where my reasoning went wrong and how i should go about fixing it? or perhaps tell me a better proof method to attack the problem with? or tell me i am correct? : )
     
  2. jcsd
  3. Oct 3, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Your proof isn't convincing. Try showing that if n is not prime, i.e. n is composite then n divides (n-1)!. Can you show that?
     
  4. Oct 3, 2011 #3
    Ah i think I see... let me try.

    if n is composite then it has some positive divisors ie. n = p1^d1 * p2^d2 * .. * pm^dm where the p_is are prime with multiplicity d_i. From the definition of the factorial, some terms in (n-1)! will be the p_i's and therefore we have that n | (n-1)!.

    Now I need to show that n doesnt divide (n-1)! +1,

    we have (n-1)! + 1 = a*n for a integer. im having difficulty proceeding at this point. Will ruminate and return when Ive got it... anybody feel free to nudge me though. Im tempted to say its obvious that this isnt true but apprehensive that im missing some simple fact which makes it so, as I did in the original post in which i sort of avoided the actual problem.
     
    Last edited: Oct 3, 2011
  5. Oct 3, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If n divides (n-1)! then you shouldn't have any problem showing n doesn't divide (n-1)!+1. But go back to the first part. Just take ANY factorization of n, like n=a*b. Clearly a and b are both in (n-1),(n-2),...,2,1. If a is not equal to b then you are home free. But suppose a=b? For example, what happens if n=9?
     
  6. Oct 3, 2011 #5
    How about this:

    since n is composite we have n = p1^d1 * p2^d2 * .. * pm^dm
    now, we know that n | (n-1)! = n-1 * n-2 * .. * 2
    want to look at n | (n-1)! + 1 = n-1 * n-2 * .. * 2 + 1 and show its not possible
    since n >= 2 and n | (n-1)!, then n cannot divide 1 + (n-1)! since the smallest number greater than that that it could possibly divide is (n-1)! + 2 (since it is at its smallest a multiple of 2)

    And to reply to your question, if n = ab and a=b, then still we have that a and b are less than n, and would be in some of n-1, n-2,..
    if n = 9 , then n = a * b for a = b = 3. in this case n still divides (n-1)! since 3 is a factor of 8!

    I feel like we are still home free as you put it. Do I need to ruminate more?
     
  7. Oct 3, 2011 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes, ruminate just a little more. 9=3*3. 8! is not divisible by 9 just because 3 is in 8!. It's divisible by 9 because both 3 and 6 are in the expansion of 8!. Expand your proof to include the case where n is the square of a prime.
     
  8. Oct 4, 2011 #7
    mmm.... okay, since a = b < n, it is obvious that at least one of a and b will itself be a factor in (n-1)! Since n >= 2 then at the very least we will have 2 * a also as a factor, and thus n | (n-1)!

    Look good?
    From this point should I argue as I have above, that n cannot divide (n-1)! + 1 since n > 2 because blah blah.... ?

    And Dick, I appreciate your help immensely. Thank-you.
     
  9. Oct 4, 2011 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Pretty sloppy still. a*a=n >= 2 isn't enough to show 2a<n. You'll need n>4 to conclude that. In fact, n=4 is an exception to the statement n | (n-1)! if n is composite. You'll need to make it another special case. If you'd be more careful you'd catch stuff like that.
     
  10. Oct 4, 2011 #9
    Showing that n | (n-1)! for the case that n = a*2 for a prime:


    the exceptional case of n =4: we have n does not divide 3!, but n also does not divide 3! + 1, so does not disagree with what we are trying to show in the first place, which is that if n is composite then n does not divide (n-1)! + 1, so this special case is "taken care of"


    for n >= 9: we have n = a^2, and a < n implies that a appears in (n-1)! at least once. to show it appears at least twice, the easiest thing (that i can think of) is to show that 2*a also appears as a factor, so we need to show that 2*a < n = a^2

    *Since square functions grow more quickly than linear functions (asymptotically), and we know that 2a < a^2 for a = 3(since 6 < 9), we can say 2a < a^2 for a>=3.* <-- im unsure how rigorous i need to be about this statement, but I doubt I would lose marks for taking it for granted

    now 2a < a^2 = n for a >=3, so we now know that 2a will appear in (n-1)!, as well as a (since a < n), so for the case of n being a perfect square >= 9, we have n | (n-1)!


    In a previous post we showed that if n is composite and not a perfect square then n | (n-1)!
    so now we have that for n composite, n >= 6, we have n | (n-1)!. As you said it should be easy enough to show that if n | (n-1)! then n does not divide (n-1)! + 1. So once I (rigorously) write out that n | (n-1)! implies n does not divide (n-1)! + 1 for n composite and > 4, then I can say by method of contrapositive if n | (n-1)! + 1, for n > 4, then n is prime. And then I can include the case of n = 4, and then Im done, right?


    heh, ill do my best ;) Thanks again for the help
     
  11. Oct 4, 2011 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ok, I think it's basically all there. Concluding 2a<a^2 doesn't need anything fancy about quadratic functions. If 2<a then 2*a<a*a. And the rest of the argument is ok. Now you just need to show n | (n-1)! implies n does not divide (n-1)!+1. It's a pretty simple conclusion and doesn't really have anything to do with (n-1)!. n | k implies n does not divide k+1 for any k.
     
  12. Oct 4, 2011 #11
    Excellent.
    A final thank-you, for the help and the timely responses. Expect me to bother these forums often : )
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Elementary number theory - proving primality
Loading...