What is $2^7 + 3^8 \bmod 11$?

Question

What is the most important thing that i should think of first when am faced with such kind of a problem. My tutor was like $2^7 = (2^5)(2^2)$. But why not raise it to different powers like 4 and 3 instead?

Because 2^5 mod 11 is easy to manipulate (did you try to compute it?), but 2^4 and 2^3 not so much. Likewise for 3^5 mod 11. Re an explanation of these (nice) facts, whan can you say about x^(p-1) mod p when p is prime? — Did, Oct 23 '15 at 15:49

score 1 · Answer 1 · answered Oct 23 '15 at 17:05

By recalling that $a^{\frac{p-1}{2}}\equiv\left(\frac{a}{p}\right)\!\!\pmod{p}$, the latter being a Legendre symbol, we have:

$$2^7+3^8\equiv 2^2\left(\frac{2}{11}\right)+3^3\left(\frac{3}{11}\right) \equiv 3^3-2^2 \equiv \color{red}{1}\pmod{11}$$ since $3$ is a quadratic residue $\!\!\pmod{11}$, due to $5^2\equiv 3\pmod{11}$, but $2$ is not.

score 0 · Answer 2 · answered Oct 23 '15 at 15:50

0

$2^7 + 3^8 \pmod{11}$

Note that $3^2 = 9 = -2$, so $3^8 = (-2)^4 = 2^4$.

Therefore $2^7 + 3^8 = 2^4(2^3+1)$.

answered Oct 23 '15 at 15:50

Patrick Stevens

36,135

What is $2^7 + 3^8 \bmod 11$?

2 Answers2