4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

$$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$$

$\endgroup$
  • $\begingroup$ I don't understand why are you doing mod 100? $\endgroup$ – user262291 Jun 9 '16 at 8:50
  • $\begingroup$ Checked the answer on a calculator it is 30 $\endgroup$ – user262291 Jun 9 '16 at 8:51
  • $\begingroup$ @user262291, Just because you have terms like $$10^2,10^3$$ in the binomial expansion. Now $\pmod{100}$ can be easily reduced to $$\pmod{50}$$ $\endgroup$ – lab bhattacharjee Jun 9 '16 at 8:51
  • 1
    $\begingroup$ @user262291, The answer will be $$7+3\cdot41\equiv30\pmod{50}$$ $\endgroup$ – lab bhattacharjee Jun 9 '16 at 8:52
2
$\begingroup$

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}$.

$\endgroup$
2
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.