Results 1 to 2 of 2

Thread: Congruence equation

  1. #1
    Senior Member I-Think's Avatar
    Joined
    Apr 2009
    Posts
    288

    Congruence equation

    Good day to the MHF. Here's my problem
    Find all integer solutions to $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 21)$

    Just making sure my solution is complete
    Solution
    $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 21)$
    By CRT, we can break this up to
    $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 3)$
    $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 7)$

    And now we deal with each separately
    For $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 3)$
    we use FLT to simplify: $\displaystyle x^2\equiv 1$ $\displaystyle (mod$ $\displaystyle 3)$
    Simplifying
    $\displaystyle x+3\equiv10$ $\displaystyle (mod$ $\displaystyle 3)$. Solves to give $\displaystyle x\equiv7$ $\displaystyle (mod$ $\displaystyle 3)$

    Now dealing with
    $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 7)$
    FLT: $\displaystyle x^6\equiv1$ $\displaystyle (mod$ $\displaystyle 7)$
    Simplifying
    $\displaystyle 3x^2+x\equiv10$ $\displaystyle (mod$ $\displaystyle 7) \rightarrow$, we solve this via guesswork

    Let $\displaystyle 3x^2+x-10=14\rightarrow3x^2+x-24=0$
    $\displaystyle (3x-8)(x+3)=0
    $Solution: $\displaystyle x\equiv-3$ $\displaystyle (mod $ $\displaystyle 7)$

    So now we use CRT to solve
    $\displaystyle x\equiv7$ $\displaystyle (mod$ $\displaystyle 3)$
    $\displaystyle x\equiv-3$ $\displaystyle (mod$ $\displaystyle 7)$
    $\displaystyle x-7=3m
    $$\displaystyle x+3=7n$

    $\displaystyle 7n-3m=10$ Solve to get $\displaystyle m=20, n=10$
    So $\displaystyle x=67$

    And a solution to our original equation is $\displaystyle x\equiv67$ $\displaystyle (mod$ $\displaystyle 21)$

    Is this all the solutions or am I missing some? If so, where is te error in my method preventing me from obtaining the others?
    Thanks in advance for the help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, I-Think!

    You're off to a good start . . .


    Find all integer solutions to: .$\displaystyle x^{19}+3x^2\:\equiv\:10\text{ (mod 21)}$


    Just making sure my solution is complete

    Solution

    $\displaystyle x^{19}+3x^2\equiv10 $ $\displaystyle (mod$ $\displaystyle 21)$

    By CRT, we can break this up to: .$\displaystyle \begin{Bmatrix}x^{19}+3x^2\:\equiv\:10 \text{ (mod 3)} \\
    x^{19}+3x^2\:\equiv\:10 \text{ (mod 7)} \end{Bmatrix}$


    And now we deal with each separately

    For $\displaystyle x^{19}+3x^2 \:\equiv\:10 \text{ (mod 3)}$
    we use FLT to simplify: .$\displaystyle x^2\:\equiv\: 1 \text{ (mod 3)}$

    Simplifying: .$\displaystyle x+3 \:\equiv\:10 \text{ (mod 3)}$.

    Solve to give: .$\displaystyle x\:\equiv\:7 \text{ (mod 3)}$

    Hence, we have: .$\displaystyle \boxed{x \:\equiv\:1\text{ (mod 3)}}$




    Now dealing with: .$\displaystyle x^{19}+3x^2\:\equiv\:10 \text{ (mod 7)}$

    FLT: .$\displaystyle x^6\:\equiv\:1 \text{ (mod 7)}$

    Simplifying: .$\displaystyle 3x^2+x \:\equiv\:10 \text{ (mod 7)}$

    We have: .$\displaystyle 3x^2 + x - 10 \:\equiv\:0\text{ (mod 7)}$

    Factor: .$\displaystyle (x+2)(3x-5) \:\equiv\:0\text{ (mod 7)}$


    . . $\displaystyle x+2\:\equiv\:0\text{ (mod 7)} \quad\Rightarrow\quad x \:\equiv\:-2\text{ (mod 7)} \quad\Rightarrow\quad \boxed{x \:\equiv\:5\text{ (mod 7)}}$


    . . $\displaystyle 3x-5\:\equiv\:0\text{ (mod 7)} \quad\Rightarrow\quad 3x \:\equiv\:5\text{ (mod 7)} $

    . . Multiply by 5: .$\displaystyle 15x\:\equiv\:25\text{ (mod 7)} \quad\Rightarrow\quad \boxed{x \:\equiv\:4\text{ (mod 7)}} $

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. congruence equation
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Sep 2nd 2010, 06:20 AM
  2. 2^x in a congruence equation
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Dec 15th 2009, 05:08 PM
  3. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Sep 28th 2008, 05:54 PM
  4. Congruence Equation
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 13th 2006, 05:00 PM
  5. Congruence equation
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 15th 2006, 07:10 PM

Search Tags


/mathhelpforum @mathhelpforum