We showed in one direction of Wilsons Theorem that if p is p

We showed in one direction of Wilson’s Theorem that if p is prime, then p | (p1)! + 1. Complete the proof of Wilson’s Theorem by showing the following strong form of the converse: If n is composite, gcd(n,(n 1)! + 1) = 1. Suggestion: Show that when when n is composite and greater than 4, n | (n1)!. b) Use the multiplicativity of the Legendre symbol to decide whether there is an integer n such that 1009 divides n^2 150.

Solution

n is composite greater than 4, then n divides (n-1)!

n > 4 (composite number) will be equal to (n=6)

Base case( n=6)

Is 6 divides 5! or Is 6 divides 120

Since 6 divides 120 with zero remainder, hence the base case hold true

Now we need to prove the statement for a general n

n being a composite number can be written as n = a*b, where a and b are two factors

Case 1: If (a==b)

n = a * a = a^2

n divides (n-1)!

(n-1)! = (n-1) * (n-2) * ... * (n-a) * ... * 1

since n=a^2 it will be divisible by n as well

Hence (n-1)! will be divisible by n^2 giving 0 remainder

Case 2: (a is not b)

hence a divides n and b divides n, that implies a divides (n-1)! and b divides (n-1)!

(n-1)! = (n-1) * (n-2) * ... * (n-b) * (n-a) *....*1

Hence it divides both a and b, hence it is divisible by n

since n divides (n-1)!

(n-1)! = 0 mod(n)

adding 1 on both sides we get

(n-1)! + 1 = 1 mod n

Hence the given statement is true