Elementary number theory - proving primality

[razmtaz]

Homework Statement

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

Homework Equations

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

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 I am 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? : )

 

[Dick]

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?

 

[razmtaz]

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 doesn't divide (n-1)! +1,

we have (n-1)! + 1 = a*n for a integer. I am having difficulty proceeding at this point. Will ruminate and return when I've got it... anybody feel free to nudge me though. I am tempted to say its obvious that this isn't true but apprehensive that I am missing some simple fact which makes it so, as I did in the original post in which i sort of avoided the actual problem.

 

[Dick]

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 doesn't divide (n-1)! +1,

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?

 

[razmtaz]

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?

 

[Dick]

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?

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.

 

[razmtaz]

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.

 

[Dick]

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.

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.

 

[razmtaz]

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.* <-- I am 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 I am done, right?

If you'd be more careful you'd catch stuff like that.

heh, ill do my best ;) Thanks again for the help

 

[Dick]

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.* <-- I am 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 I am done, right?




heh, ill do my best ;) Thanks again for the help

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.

 

[razmtaz]

Excellent.
A final thank-you, for the help and the timely responses. Expect me to bother these forums often : )