Thread: A Congruence Proof

Hi everybody,

Is there any proof that shows the following:

If p is prime, then each of the integers (lower to p) are relatively prime to p. So for each of these integers a there is another b such that ab = 1 (mod p). It is important to note that this b is unique modulo p.

I have encounter many times this conguence, however how is this comes up?

Also is there any similar congruence for integers bellow p^n?

Thank you all for your time.

Two integers are relatively prime if there greatest common denominator is 1. The definition of prime is that p can only be divided by 1 and itself. So every integer less than p does not divide p hence their gcd = 1 and hence they are relatively prime.

If you want an proper proof... Might look like this...

Let p be prime, then if p = ab then either a or b = 1. If a=1, b=p and if b=1, a=p.
Let be an integer less than p that divides p, hence p = kl for some integer l. Since ,l must be equal to 1. Hence k must be equal to p which contradicts our statement the k is an integer LESS THAN p that divides p, hence there doesnt exist an integer less than p that divides p.

Im not that good at proofs but i think that is the general idea...

First of all thank you for your answer.
Indeed what you say is correct. However why bellow any p (prime) for a given number K you ALWAYS find and an other number L (which also L<p) that k*L = 1 mod p. Why L is always exist (as L<p). ?
Note than there is no inverse for p-1 number.

Oh i see. I think this is connected to the fact that is a field. Am i right in thinking that has no zero divisors..?

Here's the proof of the fact that it's a field taken from my uni notes.

Suppose p is prime and let . To show that is a field we must find an element such that . We know that doesnt divide , since is nonzero. Hence , that is, they are coprime. Therefore there exist integers such that . Then and so . By commutativity, . So is a multiplicative inverse for and is a field.

Yes...
This make sense - commutativity of a field.
In addition in a field defined from a number p^n (p prime, n possitive integer), there are also multiplication inverse pairs of numbers, for all numbers that are not divisible by p.
(In other words if we exlude the zero diviosors of Zp field).

Thank you