Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-10-17 08:28:08

Fyodor
Guest

Abstract algebra proof help

I calculated (p-1)! mod p for some prime values of p as shown below:

(3-1)! mod 3 = 2
(5-1)! mod 5 = 4
(7-1)! mod 7 = 6
(11-1)! mod 11 = 10

As you can see, the value of (p-1)! mod p is always p-1.  How would show that the value of (p-1)! mod p is always p-1 using a proof?

#2 2007-10-17 08:53:47

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Abstract algebra proof help

So the first thing to do is to look at the integers modulo p.  For example, if p = 5:

1, 2, 3, 4

2*3 = 6 = 1 (mod p)

If p = 13

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

2*7 = 14 = 1 (mod 13)
3*9 = 27 = 1 (mod 13)
4*10 = 40 = 1 (mod 13)
5*8 = 40 = 1 (mod 13)
6*11 = 66 = 1 (mod 13)

Come up with a general theorem based upon the above noting that 1 and p-1 are not included, the simply calculate (p-1)! mod p


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#3 2007-10-17 09:57:12

b300y
Member
Registered: 2007-10-17
Posts: 1

Re: Abstract algebra proof help

help

Offline

#4 2007-10-17 11:30:31

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: Abstract algebra proof help

Since you have “abstract algebra” in the title of your thread, I’ll presume that you can use abstract-algebra techniques to prove the result (known as Wilson’s theorem). Very well, then.

Now, you have verified separately that Wilson’s theorem is true for p = 2 and p = 3. In what follows, we’ll assume that p > 3.

Note that if p is prime, the integers modulo p form a field with respect to addition and multiplication. So the nonzero elements of ℤ[sub]p[/sub] form a multiplicative group. Take an element a ∈ ℤ[sub]p[/sub] such that a ≠ 1 and ap−1. Then its order is p > 2 and so a is not its own inverse in the group. That means there must be an element b ∈ ℤ[sub]p[/sub] with ba such that ab ≡ 1 (mod p). Hence all the numbers 2, 3, … p−2 pair up in mutually distinct fashion to form multiplicative inverses, so if you multiply all of them, the answer is ≡ 1 (mod p). That is to say:

Multiply the above by p−1 and you get your result.

Last edited by JaneFairfax (2007-10-17 11:32:34)

Offline

#5 2007-10-17 12:54:23

Fyodor
Guest

Re: Abstract algebra proof help

Is this a good way of writing out the proof?

In order to compute (p-1)!, you have to find the product of the integers 1 through p-1.  In this set of integers, there are groups of two elements (excluding the group 1 and p-1) that can be multiplied together to get a number (p-1)!/(p-1), which equals p-1, which is congruent to 1 mod p.

#6 2007-10-17 13:42:28

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Abstract algebra proof help

That is precisely the way a number theory text would have you do.  I don't see the difference between what you wrote and what I was hinting at.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

Board footer

Powered by FluxBB