Results 1 to 5 of 5

Thread: 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 $\displaystyle z$ so that $\displaystyle 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 $\displaystyle z \in \mathbb{Z}$ such that $\displaystyle 34 z \equiv 3 \pmod{173}$. Then $\displaystyle \exists n \in \mathbb{Z}$ such that $\displaystyle 34z - 3 = 173n$, so $\displaystyle 34z + 173n = 3$. Now apply the extended Euclidean algorithm to $\displaystyle 34$ and $\displaystyle 173$:

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

    Hence$\displaystyle x = -5$ is a solution.

    This method holds more generally. If $\displaystyle a, b \in \mathbb{Z}, n \in \mathbb{N}^+$, then $\displaystyle \exists x \in \mathbb{Z}$ such that $\displaystyle ax \equiv b \pmod{n}$ if and only if $\displaystyle \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
    $\displaystyle 173 = 5 \cdot 34 + 3$
    $\displaystyle 34 = 11 \cdot 3 + 1$
    $\displaystyle \Rightarrow 1 = 34 - 11 \cdot 3 = 34 - 11 \cdot (173 - 5 \cdot 34) = 56 \cdot 34 - 11 \cdot 173$
    $\displaystyle \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$\displaystyle 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 $\displaystyle 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: Apr 27th 2010, 12:38 AM
  2. Mods and BN
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 17th 2010, 12:58 PM
  3. mods
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 23rd 2010, 04:08 AM
  4. mods
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 2nd 2009, 04:42 AM
  5. Mods
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 24th 2007, 04:24 PM

Search Tags


/mathhelpforum @mathhelpforum