Remainder of a remainder

Let $P(x)=ax+b$ , then there exists a polynomial $Q(x)$ with integer coefficicients such that $(x+7)^{100} = (x^2 - x - 1)Q(x) + ax + b.$ Note that $x^2 - x - 1 = 11$ is divisible by 11 for $x=4$ and $x=-3$ .

For $x = 4$ we have: $\begin{aligned} (4+7)^{100} &= (4^2 - 4 - 1)Q(4) + 4a + b\\ 11^{100} &= 11 \ Q(4) + 4a + b\\ 4a + b &\equiv 0 \mod 11. \tag{1} \end{aligned}$ For $x = -3$ , we have: $\begin{aligned} ((-3)+7)^{100} &= ((-3)^2 - (-3) - 1)Q(-3) +(-3)a + b\\ 4^{100} &= 11 \ Q(-3) + b - 3a\\ b - 3a &\equiv 4^{100} \mod 11. \end{aligned}$ Since $4^{10} = 1024 \equiv 1 \mod 11$ then $4^{100} = (4^{10})^{10} \equiv 1 \mod 11$ , thus:
$\begin{aligned} b-3a \equiv 1 \mod 11. \tag{2} \end{aligned}$ From (1) and (2) we get $(4a+b) - (b-3a) \equiv 0 - 1 \equiv -1 \mod 11,$ then , $7a \equiv -1 \mod 11 \Longrightarrow a \equiv 3 \mod 11.$ Replacing in (1) we obtain $b \equiv -4(3) \equiv -1 \mod 11.$ Finally, $P(2) = 2a+b \equiv 2(3) + (-1) \equiv 5 \mod 11.$

using the factor theorem

$(x+7)^{100} = (x-2)(x+1)Q(x) + ax + b$

using x = 2

$9^{100} = 2a + b$

using x=1

$6^{100} = -a + b$

using elimination method

$9^{100} - 6^{100} = 3a$

$a = \frac {9^{100} - 6^{100}}{3}$

substituting to either of the equations

$b = \frac {9^{100} - 2 \times 6^{100}}{3}$

therefore the remainder will be

$\frac {9^{100} - 6^{100}}{3}x - \frac {9^{100} - 2 \times 6^{100}}{3}$

evaluating P(2)

$\frac {2 \times 9^{100} - 2 \times 6^{100}}{3}x - \frac {9^{100} - 2 \times 6^{100}}{3}$

simplifying the equation

$\frac {9^{100}}{3} = 3^{199}$

we know that the cycle of 3 will repeat after 4 so

dividing 199 to 4 will have a remainder of 3

from 3, 9, 27, 81, 243 we will use 27

dividing 27 by 11 will have a remainder of 5

I just don't know if this will be correct too at other questions like this

Bashing can solve many problems. Denote $P = x^2 - x - 1$ . By the properties of remainders, it doesn't matter what order you take the remainder, whether in modulo 11 or in 'modulo' $P$ .

Now a useful tactic is finding the remainder for powers of 2. Let $R(n)$ denote the remainder when $(x + 7)^n$ is divided by $P$ with simplified coefficients modulo 11. Since $R(100) \equiv R(64)\cdot R(32) \cdot R(4) \pmod{11}$ if we can find those remainders we can quickly compute $R(100)$ .

Clearly $R(1) = x + 7$

Proceeding by squaring $R(1)$ and taking the remainder when divided by first $P$ then by 11, we obtain, $R(2) = x^2 + 14x + 49 - P = 15x + 50 \equiv 4x + 6 \pmod{11}$

Next, $R(4) = 16x^2 + 48x + 36 - 16P = 64x + 52 \equiv 9x + 8 \pmod{11}$

We continue squaring and dividing and find $R(8) = 5x + 2$ , $R(16) = x + 7$ :: and starting from this point it cycles, quickly giving us $R(32) = 4x + 6, R(64) = 9x + 8$ .

Thus, $R(100) \equiv (9x + 8)(4x+6)(9x+8) \equiv 3x + 10 \pmod{11}$

Finally, $3(2) + 10 \equiv \boxed{5} \pmod{11}$