Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Idea

Thread: Solving linear congruence

  1. #1
    Newbie
    Joined
    Jun 2016
    From
    london
    Posts
    16

    Solving linear congruence

    Hello guys

    I got a system of linear congruences, having some trouble in solving it.

    $x\equiv1\left(\bmod5\right)$
    $x\equiv2\left(\bmod6\right)$
    $x\equiv3\left(\bmod7\right)$

    By the following theorem:

    $a,b\in INTEGER \Rightarrow a\equiv b \bmod m \Leftrightarrow a=b+km$ where $k\in INTEGER$
    $x\equiv1\left(\bmod5\right)$

    $\Rightarrow x=5t+1 \equiv 2 \left(\bmod6\right)$ where $t\in INTEGER$

    which can be easily solved to show that

    $t\equiv5\left(\bmod6\right)$

    Using the above theorem, we write

    $t=6u+5$ where $u\in INTEGER$

    $\Rightarrow x=5(6u+5)+1=30u+26$

    -----------------------------------


    I am really having difficulty understanding how to get from

    $\Rightarrow x=5t+1 \equiv 2 \left(\bmod6\right)$

    to

    $t\equiv5\left(\bmod6\right)$

    My first attempt to solve it was to consider $x=5t+1 \equiv 2 \left(\bmod6\right)$ as a linear Diophantine equation and solve it using the Euclidean algorithm:

    $5t+1-6y=2$
    $\Rightarrow 5t-6y=1$
    $\Rightarrow 6 = 5 \cdot 1 + 1$
    $\Rightarrow 5 \cdot 1 = 1 \cdot 5$

    This gives $gcd(5,6)=1$ which isn't that helpful really ?

    Thanks for your advice guys.



    EUCLIDEAN ALGORITHM

    Let $r_{0}=a , r_{1}=b \in INTEGER$ such that $a\geq b > 0 $

    If the division algorithm is successively applied to obtain

    $r_{j}=r_{j+1}\cdot q_{j+1} + r_{j+2}$ where $0<r_{j+2}<r_{j+1}$ for $j=0,1,2,...,n-2$ and $r_{n+1}=0$

    then $\left(a,b\right)=r_{n}$, the last non-zero remainder
    DIVISION ALGORITHM

    $a,b\in INTEGER$ st. $b>0$ $\Rightarrow$ there exist unique $q,r\in INTEGER$ such that $a=bq+r$ with $0\leq r <b$
    This theorem shows how many solutions there are to a congruence.

    Let $a,b,m \in INTEGERS $ such that $ m>0 , \left(a,m\right)=d $

    $NOT \left(d \mid b\right) \Rightarrow ax=b \left(\bmod m\right)$ has no solutions

    $d \mid b \Rightarrow ax=b \left(\bmod m\right)$ has $d$ incongruent solutions modulo $m$
    Last edited by shakra; Feb 13th 2017 at 05:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    688
    Thanks
    310

    Re: Solving linear congruence

    5t = 1 (6)

    multiply by 5

    25t = 5 (6)

    therefore

    t = 5 (6)

    since 25 = 1 (6)
    Thanks from shakra
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2016
    From
    london
    Posts
    16

    Re: Solving linear congruence

    Quote Originally Posted by Idea View Post
    5t = 1 (6)

    multiply by 5

    25t = 5 (6)

    therefore

    t = 5 (6)

    since 25 = 1 (6)
    thank you my friend. The problem is solved.

    To give more information on the method, I post this example from A friendly introduction to number theory 2nd Ed, J. Silverman P53

    Solve $4x\equiv3 \left(\bmod19\right)$

    Multiply both sides by 5:

    $\Rightarrow 20x\equiv15\left(\bmod19\right)$

    We know that

    $20\equiv1\left(\bmod19\right)$

    $\Rightarrow 20x\equiv x\left(\bmod 19\right)$

    Thus the solution is

    $x\equiv15\left(\bmod19\right)$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 9th 2015, 07:56 PM
  2. Solving modular congruence
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: Dec 17th 2012, 03:03 PM
  3. Solving a congruence equation.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 31st 2009, 06:22 AM
  4. Solving a linear congruence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 29th 2009, 07:54 PM
  5. Solving a congruence
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Aug 15th 2008, 09:10 AM

Search tags for this page

Click on a term to search for related topics.

/mathhelpforum @mathhelpforum