Please show your steps so I may know how you came to your conclusion. What I hav
ID: 2969592 • Letter: P
Question
Please show your steps so I may know how you came to your conclusion.
What I have so far is:
Let n be a set of positive integers with n greater or equal to 2. Suppose that (n-1)(n-2) ... 1 ? -1(mod n) and that n is not prime meaning n is composite. So we establish a base case such that n is greater than or equal to 4. We can rewrite (n-1)(n-2) ... 1 ? -1(mod n) to be n|(n-1)! +1.
If we look at the base case for n = 4.
4|(4-1)! +1 = 4|3!+1 = 4|7
which is incorrect since 4 does not divide 7.
How can I get to the conclusion that n must be prime I am at a lost.
Let n Z+ with n 2. Suppose that (n - l)(n - 2) 1 -1 (mod n). Prove that n must be prime. Hint: Try proof by contradiction.Explanation / Answer
We are showing that if n is not prime that (n-1)(n-2)...(1) is not equal to -1 (mod n)
Let's consider 2 cases for n, n = 4 and all other non-prime n.
If n = 4, then (n-1)(n-2)...1 = 3*2*1 = 6, which = 2 mod 4 = -2 mod 4.
Then, consider all other composite numbers equal to n.
It may either have 2 distinct factors or be equal to p^2.
If it has 2 distinct factors, say q and r, then these factors are in 1,2, ...,n-1.
Then, the product 1*2*...*n-1 = qr*the product of all other numbers in 1 - n-1.
Thus, qr divides the product.
Thus, n divides the product.
Thus, the product = 0 (mod n)
Next, let n = p^2.
Then, p is in 1, 2, ..., n-1
As we have already taken care of the case n = 4, 2p will also be in 1, 2, ...,n-1 as n = p^2 = p * p, so 2p < p * p
Thus, we have the product 1*2*...*n-1 including p and 2p
Then the product has p*2p=2p^2 as a factor. Then, if 2p^2 is a factor, of course, p^2 = n is a factor.
Then, 1 * 2 * ... * n-1 = 0 mod n
Thus, we have shown that if n is composite, then n-1! = -2 mod n if n = 4 and 0 mod n for all other composite n. Thus, it is never equal to -1 mod n.