Results 1 to 7 of 7

Math Help - Modular arithmetic ; Solutions to 6x = 9 (mod 15)

  1. #1
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    559
    Thanks
    2

    Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    In Abstract Algebra by Hungerford, Problem 11 (c) page 29 is as follows:

    Find all solutions for the following congruence:

    6x = 9 (mod 15)

    Can anyone help me solve this congruence. What is the method or approach?

    Bernhard
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    If x is solution of the 'congruence equation'...

    6 x \equiv 9\ \text{mod}\ 15 (1)

    ... then must be...

    6\ x = k\ 15 +9 \implies x= \frac{5\ k + 3}{2} (2)

    Now the (2) is verified for...

    k=1 \implies x=4

    k=3 \implies x=9

    k=5 \implies x=14

    ... so that the (1) has three solutions...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    559
    Thanks
    2

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    Thanks for the help

    Peter (Math Hobbyist)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    Another version: solve the equation \bar{6}\bar{x}=\bar{9} in \mathbb{Z}_{15}=\{\bar{r}:r=0,1,\ldots,14\} .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,416
    Thanks
    1853

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    Notice that the solutions, x= 4, 9, and 14, to 6x= 9 (mod 15) so NOT satisfy 2x= 3 (mod 15) but do satisfy 2x= 3 (mod 5). That is because the equation ChiSigma got, 6x= 9+ 15k, is the same as 2x= 3+ 5k.

    Another way to solve the Diophantine equation, 2x- 5k= 3, useful for problem where the modulus is too large to conveniently "try" integer values for k, is to note that 2 divides into 5 twice with remainder 1. That is, 5(1)- 2(2)= 1 so that 2(-2)- 5(-1)= 1 and then, multiplying by 3, 2(-6)- 5(-3)= 3. That is, one solution is x= -6, k= -3. But notice that is we replace x with x+ 5n and y with y+ 2n, we have 2(x+ 5n)- 5(k+ 2n)= 2x+ 10n- 5k- 10n= 2x- 5k which equals three if and only if x and k satisfy the equation. That is, all solutions are of the form x= -6+ 5n. In particular, taking n= 2 3, and 4 give x= 4, 9, and 14, the three solutions between 0 and 15.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    Quote Originally Posted by HallsofIvy View Post
    Notice that the solutions, x= 4, 9, and 14, to 6x= 9 (mod 15) so NOT satisfy 2x= 3 (mod 15) but do satisfy 2x= 3 (mod 5). That is because the equation ChiSigma got, 6x= 9+ 15k, is the same as 2x= 3+ 5k.

    Another way to solve the Diophantine equation, 2x- 5k= 3, useful for problem where the modulus is too large to conveniently "try" integer values for k, is to note that 2 divides into 5 twice with remainder 1. That is, 5(1)- 2(2)= 1 so that 2(-2)- 5(-1)= 1 and then, multiplying by 3, 2(-6)- 5(-3)= 3. That is, one solution is x= -6, k= -3. But notice that is we replace x with x+ 5n and y with y+ 2n, we have 2(x+ 5n)- 5(k+ 2n)= 2x+ 10n- 5k- 10n= 2x- 5k which equals three if and only if x and k satisfy the equation. That is, all solutions are of the form x= -6+ 5n. In particular, taking n= 2 3, and 4 give x= 4, 9, and 14, the three solutions between 0 and 15.
    Unlike the congruence equation of the OP, both the congruence equations 2\ x \equiv 3\ \text{mod}\ 15 and 2\ x \equiv 3\ \text{mod}\ 5 have only one solution...

    a)

    2\ x \equiv 3\ \text{mod}\ 15 (1)

    The multiplicative inverse of 2\ \text{mod}\ 15 is 8 so that if we multiply both terms of (1) by 8 we obtain x= 9\ \text{mod}\ 15 ...

    b)

    2\ x \equiv 3\ \text{mod}\ 5 (2)

    The multiplicative inverse of 2\ \text{mod}\ 5 is 3 so that if we multiply both terms of (1) by 3 we obtain x= 4\ \text{mod}\ 15 ...

    It is easy to verify that there are no more solutions neither for (1) nor for (2)...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bernhard's Avatar
    Joined
    Jan 2010
    From
    Hobart, Tasmania, Australia
    Posts
    559
    Thanks
    2

    Re: Modular arithmetic ; Solutions to 6x = 9 (mod 15)

    Thanks again for the help

    Peter
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular arithmetic
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: May 6th 2011, 03:14 AM
  2. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 12th 2010, 09:53 PM
  3. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: October 31st 2009, 02:56 AM
  4. Modular arithmetic HELP!!
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 16th 2009, 01:02 PM
  5. modular arithmetic
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 25th 2007, 09:39 PM

Search Tags


/mathhelpforum @mathhelpforum