Results 1 to 5 of 5

Math Help - Modulo/congruence proof help

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    8

    Modulo/congruence proof help

    1. If (a,n) = 1, then  \exists b \in Z s.t. ab\equiv1 (mod n).

    2. Every positive integer is congruent to the sum of its digits (mod 9).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    1. Use the fact that there exists x,y \in \mathbb{Z} such that: (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1

    You can also show that this b is unique. by supposing that there exists more than one unique solution, i.e. ar \equiv 1 \ (\text{mod } n) and as \equiv 1 \ (\text{mod } n) for some r,s \in \mathbb{Z} and arriving at a contradiction.

    2. Here: Congruence
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Thanks for the link for the second one! We just had to prove that  10^n \equiv 1 (mod 9) so I guess I should have been able to figure that one out but I needed a push in the right direction!

    For the first one, I'm still unsure. I actually had what you have written on my paper, but I'm still unsure of how the "b" fits into the problem. I have  ny=1-ax but I need  a-b=nq or  b-a=nq right? I could divide by x, giving  \frac {ny}{x}=\frac {1} {x} -a but can I let  b=\frac {1} {x} since that's a fraction?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    We know that there exists some x,y \in \mathbb{Z} such that: (a,n) = 1 \ \Leftrightarrow \ ax + ny = 1 \ \Leftrightarrow ax = 1 + (-y)n

    By definition, this is the same as saying: ax \equiv 1 \ (\text{mod } n)

    But since x has already been determined, this is the b we were looking for !
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2009
    Posts
    8
    Oh, duh! Haha for some reason I was thinking I needed to prove  a\equiv b (mod n) . Thanks for all of your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence modulo 2^n
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 3rd 2009, 06:47 PM
  2. proof of a congruence modulo prime powers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 21st 2009, 03:41 AM
  3. Congruence & Modulo Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 15th 2009, 06:00 PM
  4. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 27th 2007, 07:59 PM
  5. congruence modulo m
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: February 22nd 2007, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum