Results 1 to 3 of 3

Thread: More congruence trouble

  1. #1
    Junior Member Nerdfighter's Avatar
    Joined
    May 2009
    From
    Washington
    Posts
    25

    More congruence trouble

    for which integers $\displaystyle c$ with $\displaystyle 0 \leq c < 1001$ does the congruence $\displaystyle 154x \equiv c$ $\displaystyle (\bmod 1001)$ have solutions? For each case when there are solutions, find how many solutions are not congruent modulo 1001.

    Originally, I thought this problem might have something to do with multiplicative inverses, but I didn't get anywhere on that front.

    If it matters, I calculated $\displaystyle \gcd (154,1001)$ to be 77.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    $\displaystyle ax \equiv b \mod n $ has a solution iff $\displaystyle (a,n) \mid b $. So $\displaystyle 154x \equiv c \mod 1001 $ is solvable iff $\displaystyle (154,1001)=77 \mid c $.
    Therefore $\displaystyle c = 77n, \; n \in \mathbb{N} $.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by chiph588@ View Post
    $\displaystyle ax \equiv b \mod n $ has a solution iff $\displaystyle (a,n) \mid b $. So $\displaystyle 154x \equiv c \mod 1001 $ is solvable iff $\displaystyle (154,1001)=77 \mid c $.
    Therefore $\displaystyle c = 77n, \; n \in \mathbb{N} $.
    Since we're working with modulos, I would say that it's 77n mod 1001.

    And since 1001/77=13, there are 13 different values for c...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] congruence
    Posted in the Geometry Forum
    Replies: 0
    Last Post: Jan 15th 2011, 02:58 AM
  2. [SOLVED] More Congruence
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Jun 26th 2010, 01:48 PM
  3. Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 6th 2010, 06:50 AM
  4. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Nov 10th 2008, 01:52 PM
  5. congruence and gcd
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 26th 2008, 01:59 AM

Search Tags


/mathhelpforum @mathhelpforum