Proving a Prime Divides a Polynomial Congruence?

[talolard]

Homework Statement

if p is prime, prove that p divides A, where A satisfis $$1+\frac{1}{2}+...+\frac{1}{p-1}=\frac{A}{\left(p-1\right)!}$$

Homework Equations

The chinese remainder theorem? Eulers theorem?

The Attempt at a Solution

So as the question marks imply, I'm at a loss as to how to start. The problem set is all about polynomial congruence and that's really as much as I've managed to figure out. A little nudge in the right direction would help a lot.
Thanks
Tal

 

[Dick]

Ok, first note A is an integer. Why? Then try to figure out what it is mod p. You'll find it useful that the nonzero integers mod p where p is a prime form a group under multiplication.

 

[talolard]

Maybe instead of a nudge i need a good shove. Here's what I've gotten

So $$A=\underset{i=1}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{i}$$ which is an integer.

Assume that $$A\equiv aMod(p)$$

$$A=\underset{i=1}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{i}=\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{i}+\frac{\left(p-1\right)!}{a}=a\left(\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{ai}\right)+\frac{\left(p-1\right)!}{a}=\frac{\left(p-1\right)!}{a}\left(1+a\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{1}{i}\right)$$
And by the modulous $$p=r\frac{\left(p-1\right)!}{a}\left(1+a\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{1}{i}\right)+a=r\frac{\left(p-1\right)!}{a}+r\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{i}+a$$
$$r\frac{\left(p-1\right)!}{a}+r\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{\left(p-1\right)!}{i}+a=a\left(1+\underset{\begin{array}{c} i=1\\ i\neq a\end{array}}{\overset{p-1}{\sum}}\frac{r\left(p-1\right)!}{ia}\right)+r\frac{\left(p-1\right)!}{a}$$
I'd like to show that a=0. I think this is too much brute force, I don't see the smart way to do this, in fact, this dumb way isn't working either.

 

[Dick]

The smart way is to notice you can get (p-1)!/k by multiplying instead. It's (p-1)!*(k)^(-1) where k^(-1) is the inverse of k mod p. Try an example, say mod 5. What's the sum of the inverses of all of the nonzero elements?

 

[icystrike]

Don't know if this works ... Have not attended any course on number theory :X

$$\sum_{i=1}^{p-1}\left( \frac{1}{i}\right)$$

$$=\sum_{i=1}^{\frac{p-1}{2}}\left( \frac{p}{i\left( p-i\right) }\right)$$

$$A=p\sum_{i=1}^{\frac{p-1}{2}}\frac{\left( p-1\right) !}{i\left( p-i\right) }$$

since $$\left( p-1\right) !\mid i\left( p-i\right) ,$$

$$A=pk$$ k is some constant

 

[Dick]

It works, and that's one way to do it. But try a little harder to guide by giving hints, not solutions, ok? talolard should probably try to find an alternate solution that uses the notion of congruence.

 

[talolard]

Thanks for the responses.
Dick, I tried the approach that you proposed and I solved the problem but I think i used icystrikes argument.
Could you take a look and let me know if I could have used a more number theoritic arguemnt?
Thanks
Tal

By eulers theorem, the inverse of an element k is $$k^{p-2}.$$

Then$$A=\sum\frac{\left(p-1\right)!}{k!}\equiv\left(p-1\right)!\sum k^{p-2}.$$ Since the set off all inverses in a finite field is the same as all members of the field. So

$$A\equiv\left(p-1\right)!\sum k . Now Z_{P}=\left\{ 1,2,...p-1\right\} .$$

Index these we notice that $$a_{p-i}+a_{i}=p.$$

Therefore$$\sum k=p\cdot\frac{\left|Z_{p}\right|}{2}.$$
and so $$A\equiv\left(p-1\right)!\cdot p\cdot\frac{\left|Z_{p}\right|}{2}$$

 

[Dick]

Oh, I think that's all right. For me the point was just that the sum 1/k mod p is the same as sum k mod p, since it's the sum of all the multiplicative inverses. How you show sum k mod p is zero mod p probably isn't that important. I would think of it as just saying if i is invertible then -i is invertible, so they cancel and the case i=(-i) doesn't happen if p>2.

 

[talolard]

Cool.
You passed the point along, thanks!
Tal