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
    10
    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
    10,211
    Thanks
    419
    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
    10
    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, 04:50 AM
  2. Linear Congruence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 06:11 AM
  3. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2009, 07:54 PM
  4. non-linear congruence proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 8th 2009, 02:05 PM
  5. Linear congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 1st 2009, 06:48 AM

Search Tags


/mathhelpforum @mathhelpforum