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

1. ## 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

2. 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.

3. ## thanks ray

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