Results 1 to 3 of 3

Math Help - [SOLVED] Linear Congruences - Classes of Solutions

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    119

    [SOLVED] Linear Congruences - Classes of Solutions

    For linear congruences of the form

     ax \equiv b (\bmod c)

    Let gcd(a, c) = d. I know that if d = 1, then there is one unique class of solutions.
    If  d \nmid b , there there is no solutions.

    However, I did a problem in the book and the answer said that there are three classes of solutions:

     3x \equiv 6 (\bmod 9)

    By the Euclidean Algorithm

    9 = 3*3 + 0

    Thus, (3, 9) = 3 | 6, then there are three solutions. This part I do not understand.

    It follows by solving the Diophantine equation  3x + 9 y = 6 we get  x = 2 + 3t , where  t \in \mathbb{Z} and  0 \leq t \leq 2

    So, then  x \equiv 2 (\bmod 9) ,  x \equiv 5 (\bmod 9) ,  x \equiv 8 (\bmod 9)

    Is there a theorem that states how many solutions there are? From the problem, I believe that the number of solutions is equal to the gcd.
    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 Paperwings View Post
    However, I did a problem in the book and the answer said that there are three classes of solutions:

     3x \equiv 6 (\bmod 9)
    Note that 2 is a solution and 3=\gcd(3,9) therefore, 2, 2+\tfrac{9}{3}, 2 + 2\cdot \tfrac{9}{3} are solutions.

    Yes, the number of solutions, up to congruences, is equal to the the gcd.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2008
    Posts
    119
    Ah, I see. Thank you ThePerfectHacker
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Solutions of four linear systems
    Posted in the Algebra Forum
    Replies: 2
    Last Post: January 14th 2010, 12:42 PM
  2. [SOLVED] Solutions of Congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: November 29th 2008, 09:11 AM
  3. Congruences classes, Quadratic Field
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 4th 2008, 06:40 PM
  4. question on distinct solutions to congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 17th 2008, 04:47 PM
  5. Replies: 0
    Last Post: March 21st 2007, 09:18 AM

Search Tags


/mathhelpforum @mathhelpforum