Thread: Similar to Wilson's Theorem

Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilson’s Theorem).

a.) Give an example of this theorem for a m (a compositive number) that is greater than 10

b.) Give an example that shows the result of this theorem will not always be true if m doesn't have primitive roots.

c.) Prove the theorem.
HINT: for all primes p, if gcd(a,p) = 1, then a^((p-1)/2) = +/- 1 (mod p)
This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
then r^(phi(m)/2) = -1 (mod m)

Originally Posted by Ideasman

a.) Give an example of this theorem for a m (a compositive number) that is greater than 10

b.) Give an example that shows the result of this theorem will not always be true if m doesn't have primitive roots.

a) Let m=14; then the product (mod 14) is 3*5*9*11*13=15*99*13=1*1*-1=-1 (because 98=7*14)

b) Let m=12; sqrt(12)=2sqrt(3), so 12 does not have primitive roots, and the product (mod 12) is 5*7*11=35*11=-1*-1=1

Originally Posted by Ideasman

c.) Prove the theorem.
HINT: for all primes p, if gcd(a,p) = 1, then a^((p-1)/2) = +/- 1 (mod p)

What theorem? Wilson's theorem? I do not know what you want me to prove.

This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
then r^(phi(m)/2) = -1 (mod m)

r^phi(m) = 1 (mod m)
Thus,
r^(phi(m))-1=0(mod m)
If m>2 then phi(m) is even, thus,
[r^(phi(m)/2) - 1][r^(phi(m)/2 + 1] = 0 (mod m)
We need to show that none of these two factors are divisors or zero.
Once we show that then either the first or second is zero.
Note it cannot be the first because that implies:
r^(phi(m)/2) = 1 (mod m).
And phi(m)/2 < phi(m) a contradiction because phi(m)=ord_m(r)
Thus,
r^(phi(m)/2) = -1 (mod m)
Q.E.D.

Thanks for the proof, TPH, but I have to prove

"Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilson’s Theorem)."

That part.

The professor, then, suggests to prove that by using the following:

"This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
then r^(phi(m)/2) = -1 (mod m)"

So using THAT, you prove the first theorem that I need to find a proof for.

Originally Posted by Ideasman

Thanks for the proof, TPH, but I have to prove

"Suppose that m is an int. and has primitive roots; then, we know that the product of the pos. integers less than m and also relatively prime to m is congruent to -1 (mod m). (Notice that if m were prime, this would just be Wilson’s Theorem)."

That part.

The professor, then, suggests to prove that by using the following:

"This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
then r^(phi(m)/2) = -1 (mod m)"

So using THAT, you prove the first theorem that I need to find a proof for.

I expect you two things about primitive roots.

Theorem 1: If r is a primitive root for a number m>1 then the set {r,r^2,r^3,...,r^[phi(m)]} are exactly all the integers relatively prime to m (and less than m).

The above theorem is the fundamental property of the primitive root.

Theorem 2: If m>2 then phi(m) is even.

Theorem 3: If r is a primitive root then r^[phi(m)] =1 (mod m).

Actually that is basically the definition of what a primitve root is.

Okay, here is the fundamental part in this proof.
If A_1,A_2,...,A_[phi(m)] are all the integers >=1 and relatively prime to m (and less than it) then there product is,
A_1*A_2*...*A_[phi(m)]
But by Theorem 1, it is r*r^2*....*r^[phi(m)]
(Note necessarily in that order. But they can be rearranged by Dirichlet's Pigeonhole Principle).

Now follow the attachment. (That "p" should really be a "m" in the last line).

Originally Posted by Ideasman

"This idea then leads to this next theorem which you may want to use in your proof: Theorem: If m (composite or prime) has a primitive root r,
then r^(phi(m)/2) = -1 (mod m)"

We still never proved this. My professor suggests the following simple and elegant proof.

Let r be a primitive root of m. Then there exists a positive integer k such that r^k = -1 (mod m). Now what can k be? Note if k<phi(m)/2 then (r^k)^2 = r^(2k) = 1 (mod m) with 2k<phi(m). Contradicting the fact the r is a primitive root. If k>phi(m)/2 then the order of an interger must divide phi(m) [This is a theorem]. But then that is impossible because phi(m)/2 does not divide phi(m). Thus k=phi(m)/2 is the only possible exponent for r to produce -1 under modulo m.
Q.E.D.