Hi,

Firstly, how would you prove that if p is prime then for all k coprime with p there exists j s.t. kj = 1 mod p. (I can see why its true but cannot prove it thorougly)

Secondly, how do we explain that in the residue class of p that all terms pair up to give 1modp.

Thanks

Are you allowed to use Wilson's theorem in proving (1), or is Wilson's theorem what you are trying to prove?

Olof

Well, the first relies on this rather neat result, which comes up all over the place in number theory:

If a and b are coprime integers, there exist integers l and m such that la+mb=1
Have you come across this before? If not I will give you the proof.

Given this result, it follows that for any m not divisible by p, we can find l, m such that lm+mp=1; that is, there is a l such that lm=1 mod p. Which is the required result.

David

Yes,

If we have

1,2,3,...,k,...,j,...p-1 where p is prime

then (k,p) = 1 which implies kx+py = 1 where x,y are integers. Thus, p divides kx-1 and thus kx = 1 mod p. Now dont you have to prove that x is a member of the residue class of p? or is that trivial since x = j mod p for whatever x?

thanks

Hi,

I'm not entirely sure I have the right definition of residue classes, but if I do, then you don't really need to prove anything else for (1). Suppose that x isn't a member of the residue class of p, and x = j+np for integers j and n > 0. Substituting this in kx = 1 mod p, you find that j will also work.

If you need to find an integer j for a given k, then you can use Wilson's theorem (although I suspect that this is what you are trying to prove?):

You know that (p-1)! = -1 mod p

Therefore let j = -(p-1)!/k.

Regards,
Olof

Yes, but you'd have fun calculating that for p = 37, say. You can find x and y by Euclid's algorithm very quickly.

Indeedy. I was just pointing it out in case one just needs an example of a solution, with no calculation whatsoever needed. Another way to show that j exists is to give an example. You could simply let j = 1/k (which makes sense mod p).

Regards,
Olof

I agree with you Olof that case one has been proven.

But i am still not sure about case 2. Why is it that the terms pair up to give 1 mod p (except of course for 1 and p-1)

Thanks

And (just clearing it up) i am trying to prove Wilsons theorem

thanks

Hi,

Could I just ask what you mean by the terms 'pairing up'? Adding 2 terms together?

Regards,
Olof

Am I right in thinking that you have been looking at this site ? Your terminology suggests so. The reason that one can pair off the integers from 2 to p-2 is that each must have an inverse, and since only 1 and -1 can be their own inverse, the inverse of each of 2..p-2 is another one of 2..p-2. So they fall neatly into pairs with product 1.

Hence (p-1)! = (1)(1)(1)...(p-1) = -1 mod p.

Just adding that my original query is solved by the fact that (Z*, multplication mod p) forms a group only when p prime.

So, as David said we can pair off the integers from 2 to p-2 since each of these elements will have a unique inverse.

By the way, how do you prove that (Z*, multplication mod p) forms a group only when p prime.

regards
dimitri

If p is not prime then there is a problem with the existence of certain inverses. The following is true:

For all integers a, b there exist integers x, y, such that ax+by=1 if and only if gcf(a,b)=1. (*)

Proof:
Suppose gcf(a,b)=1. Euclid's algorithm provides a proof that x and y exist. (Post if u want further info.)
If ax+by=1 then gcf(a,b)|a and gcf(a,b)|b so gcf(a,b)|ax+by equivalently gcf(a,b)|1. We deduce gcf(a,b)=1.

To say that m in (Z*, mod p) has an inverse is to say that there exists an integer s in (Z*, mod p) such that ms=1 (mod p). Equivalently that there exist integers s and k with ms-pk=1. We know from the result (*) above that this is true when and only when (m,p)=1. If p is not prime there will exist an m with m|p which has no inverse.


Apologies if this explanation is unclear.

Will.