Results 1 to 5 of 5

Math Help - Mods help

  1. #1
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517

    Mods help

    Hey guys, jsut wondering how to figure out this question: Find an integer  z so that  34z \equiv 3 mod 173.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Suppose you have z \in \mathbb{Z} such that 34 z \equiv 3 \pmod{173}. Then \exists n \in \mathbb{Z} such that 34z - 3 = 173n, so 34z + 173n = 3. Now apply the extended Euclidean algorithm to 34 and 173:

    173 = 5 \cdot 34 + 3
    34 = 11 \cdot 3 + 1
    \Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173
    \Rightarrow 3 = (3 \cdot 56) \cdot 34 - 33 \cdot 173 \equiv -5 \cdot 34 \pmod{173}.

    Hence x = -5 is a solution.

    This method holds more generally. If a, b \in \mathbb{Z}, n \in \mathbb{N}^+, then \exists x \in \mathbb{Z} such that ax \equiv b \pmod{n} if and only if \text{hcf}(a,n) \mid b. If this is the case, then the same method works.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Quote Originally Posted by Giraffro View Post
    173 = 5 \cdot 34 + 3
    34 = 11 \cdot 3 + 1
    \Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173
    \Rightarrow 3 = (3 \cdot 56) \cdot 34 - 33 \cdot 173 \equiv -5 \cdot 34 \pmod{173}. <---- I DONT KNOW HOW YOU GOT THIS LINE....

    Hence x = -5 is a solution.
    Hey my writting in blue explains what my problem is.. I understand how you got the line 1 = ...... but dont know how you got the 3 = .....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2007
    From
    Santiago
    Posts
    517
    Anyone can explain? thank you
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    36
    Quote Originally Posted by jvignacio View Post
    Hey my writting in blue explains what my problem is.. I understand how you got the line 1 = ...... but dont know how you got the 3 = .....
    Just multiply the '1=...' line by 3 to get the '3=...' line and 3 \cdot 56 =168 \equiv -5 \pmod{173}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mods Help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 27th 2010, 12:38 AM
  2. Mods and BN
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 17th 2010, 12:58 PM
  3. mods
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 23rd 2010, 04:08 AM
  4. mods
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 2nd 2009, 04:42 AM
  5. Mods
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 24th 2007, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum