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

**rickykkk2000** · February 4th 2010, 09:59 PM

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

**Bacterius** · February 4th 2010, 11:36 PM

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.

**rickykkk2000** · February 5th 2010, 09:38 AM

Thank you very much Ray,
Now I understand where I went wrong.

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

LinkBack

Thread Tools

Display

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

thanks ray

Similar Math Help Forum Discussions

What is the remainder when 11^ 8577314 is divided by 97?

[SOLVED] Remainder when large numbers divided

remainder when divided by 7

what is the remainder of the summation when divided by ten

remainder of sum, divided by 4

Search Tags