Results 1 to 3 of 3

Math Help - remainder of [9!(16) + 4311]^8603 divided by 11 ?

  1. #1
    Newbie
    Joined
    Feb 2010
    Posts
    5

    remainder of [9!(16) + 4311]^8603 divided by 11 ?

    Hello dear all staff of mathhelpforum and everyone,
    I am a first time user and this is my first post threat.
    I approached this question starting with the relation that

    10 is congruent to (-1) (mod11), then with some calculation, it follows that:
    ----------------------------------
    4311 is congruent to (-1)(mod 11) (1)

    9! is congruent to 1(mod 11) (2)

    16 is congruent to 5 (mod 11) (3)
    ----------------------------------

    from (2) and (3), it follows that:
    9!(16) is congruent to (1*5) (mod 11), (4)

    combine (1) and (4) get,
    (9!(16) +4311) is congruent to (5+(-1)) (mod 11)
    = 4 (mod 11)

    => (9!(16) + 4311)^8603 is congruent to 4^8603 (mod 11).
    the remainder i got was 4^8603.

    This is obviously WRONG, but for now, I can't seem to recognize where the logic went wrong here.

    Could someone help me point it out?
    Thank you guys very much in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Hello !

    \Rightarrow Your result is nearly correct. You must simplify the exponent too, in order to be able to compute it efficiently (although this can be considered as a tractable exponent in most cases), and to perform the modulus operation to obtain your remainder in the ring \mathbb{Z} / 11 \mathbb{Z}.

    Here is a method to achieve this using Fermat's Little Theorem (with the Euler generalization).

    It states that a^{\varphi{(p)}} \equiv 1 \pmod{p} for any a, \ p. Note that 11 is prime, thus \varphi{(11)} = 11 - 1 = 10.

    Therefore, you know that a^{10} \equiv 1 \pmod{11}. Note that you can equally take a multiple of \varphi{(p)} as exponent without changing the congruence, thus you can extend this even further : a^{10k} \equiv 1 \pmod{11}, k \in \mathbb{Z} / 11 \mathbb{Z} [1].

    Let's attack our problem now : consider the base (9! \times 16 + 4311) as a whole, namely a, we will work with it later. The exponent is 8603. Thus you have :

    a^{8603} \equiv x \pmod{11}

    And you want to solve this for x. Note that a little bit of algebra can be done here, to be able to use [1] on this problem.

    a^{8603} = a^{8600} \times a^3

    Thus :

    a^{8600} \times a^3 \equiv x \pmod{11}

    Since 8600 is a multiple of 10, we can apply [1], and we get :

    1 \times a^3 \equiv x \pmod{11}

    Or, more simply :

    a^3 \equiv x \pmod{11}

    Now that we've simplified the astronomical exponent, let's work out a (this is what you have successfully done). Recall that :

    a = 9! \times 16 + 4311

    Easily enough, 4311 \equiv 10 \pmod{11}, 9! \equiv 1 \pmod{11}, 16 \equiv 5 \pmod{11}.

    Thus : a \equiv 1 \times 5 + 10 \equiv 15 \equiv 4 \pmod{11}

    Finally, we are left with :

    4^3 \equiv x \pmod{11}

    And this is easily solved :

    4^3 \equiv 64 \equiv 9 \pmod{11}

    Conclusion : (9! \times 16 + 4311)^{8603} \equiv 9 \pmod{11}.

    Please mention it if you do not understand any of these steps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    5

    thanks ray

    Thank you very much Ray,
    Now I understand where I went wrong.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 5th 2011, 01:27 PM
  2. [SOLVED] Remainder when large numbers divided
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 27th 2011, 07:13 PM
  3. remainder when divided by 7
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 14th 2011, 05:43 AM
  4. what is the remainder of the summation when divided by ten
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: July 24th 2010, 03:51 AM
  5. remainder of sum, divided by 4
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 6th 2008, 01:50 PM

Search Tags


/mathhelpforum @mathhelpforum