Results 1 to 5 of 5

Math Help - Linear Congruence

  1. #1
    Member
    Joined
    Oct 2006
    Posts
    84

    Linear Congruence

    The following was confusing me, so any help/explanations would be greatly appreciated!

    Find all incongruent solutions to the following linear congruence:

    21x ≡ 14 (mod 91)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by clockingly View Post
    The following was confusing me, so any help/explanations would be greatly appreciated!

    Find all incongruent solutions to the following linear congruence:

    21x ≡ 14 (mod 91)
    \gcd(21,91)=7 and 7|14 so there shall be 7 solutions in each congruence class. By inspection we see that x\equiv 5 is one equivalence class which solves this. By theorem it means 5 + \frac{91}{7}t for t=0,1,...,6 shall all be solutions.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,664
    Thanks
    298
    Awards
    1
    Quote Originally Posted by ThePerfectHacker View Post
    \gcd(21,91)=7 and 7|14 so there shall be 7 solutions in each congruence class. By inspection we see that x\equiv 5 is one equivalence class which solves this. By theorem it means 5 + \frac{91}{7}t for t=0,1,...,6 shall all be solutions.
    By "incongruent" solutions the question is asking for all distinct residue classes that solve the equation?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by topsquark View Post
    By "incongruent" solutions the question is asking for all distinct residue classes that solve the equation?

    -Dan
    Yes.

    For example x\equiv 2 (\bmod 4) the solutions x=2,6 are really the same ("congruent") solutions because they are contained in the same equivalence class (equivalence class mod 4*)


    *)The congruence classes are \{...,-4,0,4,...\} , \{...,-3,1,5,...\}, \{...,-2,2,6,...\}, \{...,-1,3,7,...\}. So x=2,6 are in the same equivalence class.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    hmm

    so if showing the incongruences would it be x=-12=14 (mod13)??
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solve linear congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 23rd 2010, 03:50 AM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 05:11 AM
  3. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 06:54 PM
  4. non-linear congruence proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 8th 2009, 01:05 PM
  5. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 05:48 AM

Search Tags


/mathhelpforum @mathhelpforum