I'm glad someone else is interested :) I found I could remember the key tricks, and managed to put them back into the proofs -- compared to the rest of the course, they weren't as hard as I remember, though I don't know if I could ever have got it from scratch :)
(I would have thought it necessary to write it down (unless you're familiar with it) -- I find this sort of thing extremely prone to implicit assumptions, especially as going back to the beginning. I expect your proofs are right, though I admit doubt they're rigorous if they're not written down. But maybe that's just me.)
FWIW, you can probably find the proofs online, but what I have is:
(1) Have 1<a<p. Consider a,2a,3a,...,(p-1)a.
These are non-zero mod p, else p divides ai. But p is prime, so must divide one or the other (proof by fundamental theorem of arithmetic, that each number is a unique product of primes), contradiction, as both <p.
Also these must be distinct else some ia=ja (1<=j<i<p) hence (i-j)a==0 (p) hence p divides (i-j)a. Contradiction as before.
But then a,2a...(p-1)a must be equal (mod p) 1,2...,p-1 in some order, hence some ai==1 (p), so i is the required inverse.
(2) (a)(2a)...((p-1)a)==(1)(2)...(p-1) as both lists are the same rearranged (see before). Then ap-1(p-1)! == (p-1)! (mod p). (p-1)!=/=0 since no product of a,i<p can be a multiple of p. So cancel it from both sides and ap-1==1 (p)
(3) What are self-inverses? a^2==1 (p) <==> a^2-1==0 <==> (a+1)(a-1)==0 <==> a+1=p (since 1<=a<p, and p| a+1 or a-1 ). So p-1 is the only self-inverse.
Hence (p-1)! is a product of: 1, p-1, and (p-3)/2 pairs of inverses. All the inverses cancel, leaving (p-1)!==(p-1) mod p.
no subject
Date: 2007-07-24 04:15 pm (UTC)(I would have thought it necessary to write it down (unless you're familiar with it) -- I find this sort of thing extremely prone to implicit assumptions, especially as going back to the beginning. I expect your proofs are right, though I admit doubt they're rigorous if they're not written down. But maybe that's just me.)
FWIW, you can probably find the proofs online, but what I have is:
(1) Have 1<a<p. Consider a,2a,3a,...,(p-1)a.
These are non-zero mod p, else p divides ai. But p is prime, so must divide one or the other (proof by fundamental theorem of arithmetic, that each number is a unique product of primes), contradiction, as both <p.
Also these must be distinct else some ia=ja (1<=j<i<p) hence (i-j)a==0 (p) hence p divides (i-j)a. Contradiction as before.
But then a,2a...(p-1)a must be equal (mod p) 1,2...,p-1 in some order, hence some ai==1 (p), so i is the required inverse.
(2) (a)(2a)...((p-1)a)==(1)(2)...(p-1) as both lists are the same rearranged (see before). Then ap-1(p-1)! == (p-1)! (mod p). (p-1)!=/=0 since no product of a,i<p can be a multiple of p. So cancel it from both sides and ap-1==1 (p)
(3) What are self-inverses? a^2==1 (p) <==> a^2-1==0 <==> (a+1)(a-1)==0 <==> a+1=p (since 1<=a<p, and p| a+1 or a-1 ). So p-1 is the only self-inverse.
Hence (p-1)! is a product of: 1, p-1, and (p-3)/2 pairs of inverses. All the inverses cancel, leaving (p-1)!==(p-1) mod p.
Does that accord?