Find $3^{333} + 7^{777}\pmod{ 50}$

Question

As title say, I need to find remainder of these to numbers. I know that here is plenty of similar questions, but non of these gives me right explanation. I always get stuck at some point (mostly right at the beginning) and don't have idea how to start.

Thanks in advance.

Answer 1

$$7^2\equiv-1\pmod{50}$$

$$\implies7^{777}\equiv(7^{2})^{388}\cdot7\equiv(-1)^{388}7\equiv7$$

and

$$3^{333}=3(10-1)^{166}$$

Now $$(10-1)^{166}=(1-10)^{166}\equiv1-\binom{166}110\pmod{100}\equiv1-60\equiv41$$

Answer 2

You can seperate and do it $\pmod{2}$ and $\pmod{25}$ and use chinese remainder: They are both odd so their sum is even and thus $\equiv 0 \pmod{2}$. The euler function of 25 gives 20 and thus $3^{333}\equiv 3^{13}\pmod{25}$ and $7^{777}\equiv 7^{17} \pmod{25}$.

Now, $7^2=49\equiv -1 \pmod{25}$. Thus $7^{17}=7^{16}\cdot 7 \equiv 7\pmod{25}$.

$3^3=27\equiv 2 \pmod{25}$. Thus $3^{13}=3^{12}\cdot 3\equiv 2^4\cdot 3 \equiv -2 \pmod{25}$.

Thus their sum is $5\pmod {25}$.

In conclusuion, $3^{333}+7^{777} \equiv 30 \pmod{50}$.

Answer 3

The sequence $\{3^k\pmod{25}\mid k=1,\cdots\}$ is as follows: $$\{3,9,2,6,-7,4,12,11,8,-1,\cdots\}.$$
Hence the order of $3$ modulo $25$ is $20,$ and then $3^{333}\equiv3^{13}\equiv-3^3\equiv-2\pmod{25}.$
Also, $7^2\equiv-1\pmod{25}$ so $7^{777}\equiv(-1)^{388}7\equiv7\pmod{25}.$
Thus $3^{333}+7^{777}\equiv5\pmod{25}$ and is even, so it is $\equiv 25+5=30\pmod{50}.$

Hope this helps.

Answer 4

I always start by writing a couple of powers, in this case modulo $50$:

$$\begin{align}3^1\equiv 3&\mod 50\\ 3^2\equiv 9&\mod 50\\ 3^3\equiv 27&\mod 50\\ 3^4=81\equiv 31&\mod 50\\ 3^5\equiv 93\equiv 43&\mod 50\\ 3^6\equiv 129\equiv 29&\mod 50\\ 3^7\equiv 87\equiv 37&\mod 50\\ 3^8\equiv 111\equiv 11&\mod 50\\ 3^9\equiv 33&\mod 50\\ 3^{10}\equiv 99\equiv-1&\mod 50\\ \end{align}$$

Oh look, a pattern! If $3^{10}\equiv -1\pmod {50}$, this means that $3^{20}\equiv 1\pmod {50}$,

so from here, I know that $3^{333}=(3^{20})^{16}\cdot 3^{10}\cdot 3^3\equiv 1\cdot(-1)\cdot 27=-27\equiv 23\pmod {50}$.

---

For the $7$, it's even easier, since $7^2\equiv -1\pmod {50}$, meaning that $7^{777}=(7^2)^{388}\cdot 7\equiv (-1)^{388}\cdot 7=7\pmod {50}$

Answer 5

First, let us compute $\varphi(50)=\varphi(2\cdot 25)=\varphi(2)\varphi(25)=20$. By Euler's theorem, if $a$ is relatively prime to 50, $a^{20}\equiv 1 \pmod{50}$. Therefore

$$3^{333}+7^{777}\equiv 3^{16*20+13}+7^{38*20+17}=1^{16}*3^{13}+1^{38}*7^{17}\pmod{50}.$$

Thus, we have reduced the problem to computing $3^{13} \pmod{50}$ and $7^{17}\pmod{50}$. There are a number of ways to proceed from here, but one that I like is repeated squaring. I will demonstrate the procedure for one of the terms.

Write $13$ in base $2$ as $13=8+4+1=1+2(2(1+2))$. Then $3^{13}=3*((3^{1+2})^2)^2$. We then compute $3^3=27$, $27^2\equiv 29\pmod{50}$, $29^2\equiv (-21)^2\equiv 41 \equiv -9 \pmod{50}$, and finally $3*(-9)\equiv -27 \pmod{50}$. With this method, we can compute $a^b \pmod{n}$ in less than $2\log_2 \varphi(n)$ steps where each step is either a squaring or a multiplication by $a$, and we never have any intermediate terms bigger than $n^2$.