Results 1 to 5 of 5

Math Help - A Congruence Proof

  1. #1
    Member
    Joined
    May 2009
    Posts
    77

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    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 k \neq 1 be an integer less than p that divides p, hence p = kl for some integer l. Since k \neq 1 ,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...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    77
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Oh i see. I think this is connected to the fact that \mathbb{Z}_p is a field. Am i right in thinking that \mathbb{Z}_p 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 [0]_p \neq [a]_p \in \mathbb{Z}_p. To show that \mathbb{Z}_p is a field we must find an element [b]_p such that [a]_p[b]_p = [1]_p = [b]_p[a]_p. We know that p doesnt divide a, since [a]_p is nonzero. Hence (a, p) = 1, that is, they are coprime. Therefore there exist integers b, c such that  ba + cp = 1. Then  p | 1 - ba = cp and so [ba]_p = [b]_p[a]_p = [1]_p. By commutativity, [a]_p[b]_p = [1]_p. So [b]_p is a multiplicative inverse for [a]_p and \mathbb{Z}_p is a field.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    77
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 02:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2009, 10:03 AM
  3. another congruence proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 02:41 PM
  4. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2008, 07:16 AM
  5. Proof congruence
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 19th 2007, 09:13 AM

Search Tags


/mathhelpforum @mathhelpforum