Results 1 to 3 of 3

Math Help - Division Algorithm

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    4

    Division Algorithm

    Let a = 43^8765 - 34^5678,
    and let c = 43^8765 + 34^5678.

    Without evaluating:

    1. Show that a is divisible by 3
    2.Find the remainder when c is divided by 7
    3. Hence find the remainder when c^a is divided by 7.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    1) 43 \equiv 1(\text{mod}\, 3) and 34 \equiv 1(\text{mod}\, 3), so

    43^{8765}-34^{5678} \equiv 1-1=0(\text{mod}\, 3).

    2) 43 \equiv 1(\text{mod}\, 7) and 34 \equiv -1(\text{mod}\, 7), so

    43^{8765}+34^{5678} \equiv 1+(-1)^{5678}=2(\text{mod}\, 7).

    3)

    c \equiv 2(\text{mod}\, 7)
    c^2 \equiv 4(\text{mod}\, 7)
    c^3 \equiv 1(\text{mod}\, 7)
    c^4 \equiv 2(\text{mod}\, 7)

    \vdots

    , so the sequence is 2,4,1,2,4,1,2,4,1,... . Since a is divisible by 3, the remainder must be 1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    600
    Hello, nacknack!

    Are you allowed Modulo Arithmetic?


    Let \begin{array}{ccc}a &=& 43^{8765} - 34^{5678} \\c &=& 43^{8765} + 34^{5678} \end{array}

    Without evaluating:

    1. Show that a is divisible by 3.

    We have: . \begin{Bmatrix}43 & \equiv & 1 & \text{(mod 3)} \\ 34 &\equiv & 1 & \text{(mod 3)} \end{Bmatrix}


    Hence: . a \;=\;43^{8765} - 34^{5678}

    . - . . . . . \equiv\;\;1^{8765} - 1^{5678}\text{ (mod 3)} \;\;\equiv\;\; 1-1\text{ (mod 3)} \;\;\equiv\;\; 0 \text{ (mod 3)}


    Therefore: . a \;\equiv\;0\text{ (mod 3)} . . . . a is divisible by 3.




    2. Find the remainder when c is divided by 7.

    We have: . \begin{Bmatrix}43 &\equiv & 1 & \text{mod 7)} \\ 34 &\equiv & \text{-}1 & \text{(mod 7)} \end{Bmatrix}


    Hence: . c \;=\;43^{8765} + 34^{5678}

    . . . . . . . \equiv\;\;1^{8765} + (\text{-}1)^{5678} \text{ (mod 7)} \;\;\equiv\;\;1 + 1 \text{ (mod 7)} \;\;\equiv\;\;2 \text{ (mod 7)}


    When c is divided by 7, the remainder is 2.




    3. Hence find the remainder when c^a is divided by 7.

    We already have: . \begin{Bmatrix}43 & \equiv & 1 & \text{(mod 7)} \\ 34 &\equiv & \text{-}1& \text{(mod 7)} \end{Bmatrix}


    Hence: . a \;=\;43^{8765} - 34^{5678}

    . . . . . . . . \equiv\;\;(1)^{8765} - (\text{-}1)^{5678} \text{ (mod 7)} \;\;\equiv\;\;1 - 1\text{ (mod 7)} \;\;\equiv\;\; 0\text{ (mod 7)}


    We have: . c^a \;=\;\left(43^{8765} + 34^{5678}\right)^{43^{8765} - 34^{5678}}

    . . . . . . . . . . \equiv\;\;2^0\text{ (mod 7)} \;\;\equiv\;\;1\text{ (mod 7)}


    When c^a is divided by 7, the remainder is 1.



    But check my work . . . please!


    edit: Black was too fast for me (and briefer, too!) . . . *sigh*
    .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Algorithm.....
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 26th 2010, 06:53 AM
  2. Division algorithm/mod
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 13th 2010, 12:51 PM
  3. Division Algorithm
    Posted in the Algebra Forum
    Replies: 3
    Last Post: January 18th 2009, 03:11 PM
  4. Division Algorithm...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 8th 2008, 08:33 PM
  5. division algorithm
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: September 7th 2007, 01:39 PM

Search Tags


/mathhelpforum @mathhelpforum