Results 1 to 7 of 7

Math Help - Existence proof

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    78

    Existence proof

    Show that for every integer a not divisible by 11 there is another integer b with
    a*b == 1 (mod 11).

    This problem has me stumped...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by paulrb View Post
    Show that for every integer a not divisible by 11 there is another integer b with
    a*b == 1 (mod 11).

    This problem has me stumped...
    Actually there are infinite. The problem stated another way: show that if a \not \equiv 0\pmod{11} then a has a multiplicative inverse mod 11. It follows immediately from fermat's little theorem / euler's theorem.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2008
    Posts
    78
    Thanks...I should have specified though, I've only been in this number theory class for 3 weeks and we have only covered basic theorems about congruence / number theory. Nothing with fermat's little theorem / euler's theorem so I don't think it would be acceptable for me to use that in a proof.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by paulrb View Post
    Thanks...I should have specified though, I've only been in this number theory class for 3 weeks and we have only covered basic theorems about congruence / number theory. Nothing with fermat's little theorem / euler's theorem so I don't think it would be acceptable for me to use that in a proof.
    I think we can do as follows. It will be a stronger result than what you need to prove.

    Let p be any prime, and let a be an integer not divisible by p.

    Consider the set S=\{0,a,2a,\,\ldots\,,(p-1)a\}. Claim: each element of S is distinct modulo p.

    Proof: Suppose the opposite. Then there exist integers x, y such that x\not\equiv y\pmod{p} and ax\equiv ay\pmod{p}. The latter implies a(x-y)\equiv 0\pmod{p}. So we have a product of two non-multiples of p being divisible by p; contradiction.

    Now consider that there are p distinct equivalence classes in S modulo p, thus it is the set of all equivalence classes modulo p, and \overline{1}\in S.
    Last edited by undefined; September 22nd 2010 at 02:24 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2008
    Posts
    78
    That's a great proof, thank you!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    I'd just like to point out that a more standard approach would be to use Bezout's identity.

    If 11 does not divide a, then \gcd(a,11)=1. By Bezout's identity, there exist integers x,y such that ax+11y=1. Taking everything modulo 11, ax+11y\equiv 1\pmod{11}, and ax\equiv 1\pmod{11}. The term x is what we are looking for.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by roninpro View Post
    I'd just like to point out that a more standard approach would be to use Bezout's identity.

    If 11 does not divide a, then \gcd(a,11)=1. By Bezout's identity, there exist integers x,y such that ax+11y=1. Taking everything modulo 11, ax+11y\equiv 1\pmod{11}, and ax\equiv 1\pmod{11}. The term x is what we are looking for.
    Thanks, I wasn't sure if Bezout's identity was available after 3 weeks of intro number theory, I should study standard progression of theorems from axioms.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: July 16th 2011, 12:22 PM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. existence proof, how to start?
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: April 12th 2010, 09:34 PM
  4. proof of existence of z in x < z < y
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: May 24th 2009, 10:54 AM
  5. existence of proof in connection to x^2 = y^2 mod n
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 13th 2008, 04:24 PM

/mathhelpforum @mathhelpforum