Results 1 to 6 of 6

Math Help - Solutions in a congruence class

  1. #1
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17

    Solutions in a congruence class

    How do you find one and what is it exactly? For example, 2x is congruent to 3 (mod 5), what is a solution, what would it look like, how would you write it?
    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 Eagle3 View Post
    How do you find one and what is it exactly? For example, 2x is congruent to 3 (mod 5), what is a solution, what would it look like, how would you write it?
    When you write 2x\equiv 3(\bmod 5) you are asking to find all x\in \mathbb{Z} so that 5 divides 2x-3.

    Notice that 2x\equiv 3(\bmod 5) if and only if 2x\equiv 8(\bmod 5) if and only if x\equiv 4(\bmod 5). That is it! We found the solution. When we write x\equiv 4(\bmod 5) it means x = 5k+4 for some k\in \mathbb{Z}. Therefore, all solutions to 2x\equiv 3(\bmod 5) have the form x=5k+4.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Notice that 2x\equiv 3(\bmod 5) if and only if 2x\equiv 8(\bmod 5) if and only if x\equiv 4(\bmod 5). That is it! We found the solution. When we write x\equiv 4(\bmod 5) it means x = 5k+4 for some k\in \mathbb{Z}. Therefore, all solutions to 2x\equiv 3(\bmod 5) have the form x=5k+4.[/quote]

    I guess my problem is that I do not see why 2x must equal 8.
    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 Eagle3 View Post
    I guess my problem is that I do not see why 2x must equal 8.
    If a\equiv b(\bmod c) then a\equiv b + c(\bmod c) and the other way around.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jan 2009
    From
    Phoenix, Arizona
    Posts
    17
    Notice that 2x\equiv 3(\bmod 5) if and only if 2x\equiv 8(\bmod 5) if and only if x\equiv 4(\bmod 5). That is it! We found the solution. When we write x\equiv 4(\bmod 5) it means x = 5k+4 for some k\in \mathbb{Z}. Therefore, all solutions to 2x\equiv 3(\bmod 5) have the form x=5k+4.[/quote]

    So if I understand this correctly, in the case 6x is congruent to 10 (mod 15), then there is no solution since 6 never divides evenly into 10+15k, where k is an integer.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Eagle3 View Post
    So if I understand this correctly, in the case 6x is congruent to 10 (mod 15), then there is no solution since 6 never divides evenly into 10+15k, where k is an integer.
    The congruence 6x\equiv 10(\bmod 15) never has a solution. So see this say there is such an x then 15 | (6x - 10) which means 15k = 6x - 10 for some k\in \mathbb{Z}. But then 15k - 6x = 10 \implies 3(5k - 2x) = 10. This is a problem because 10 has no factor of 3.

    Once you understood what I wrote above try generalizing the result. Let a,n be positive integers and consider ax \equiv  b(\bmod n). Let d=\gcd(a,n). Prove that if the congruence is solvable then d divides b.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rewording of a congruence class problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 14th 2010, 05:50 AM
  2. Congruence/Residue Class
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: August 30th 2009, 01:14 AM
  3. conjugacy class and class equation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 1st 2009, 07:52 PM
  4. find all solutions to the congruence
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: June 18th 2008, 10:30 AM
  5. The determinant of the solutions of a linear congruence
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: March 3rd 2008, 08:02 PM

Search Tags


/mathhelpforum @mathhelpforum