# How to determine the remainder of $\frac{7^{369}}{350}$?

How to determine the remainder of the following :

$$\frac{7^{369}}{350}$$

Is there any tricky way to determine this?

I start as $$\frac{7^{368}}{50} \ \ ,$$

This type of problem are highly asked in aptitude exam.

• Notice that $\ 7^2 \ = \ 50 \ - \ 1 \$ and $\ 7^4 \ = \ (50 - 1)^2 \ = \ 50^2 \ - \ 2 \cdot 50 \ + \ 1 \$ . What might other even powers of 7 give? (There are theorems that cover this, but I'm assuming from your tag that you are not taking number theory.) – colormegone Jun 7 '16 at 6:13

hint : $$7^{368}=49^{184}=(50-1)^{184}$$

This is called Modular Exponentiation and can be solved in many different ways. The most efficient is Right-to-Left Binary Method (on Wikipedia). It is possible to do by hand and will only take 8 iterations of the algorithm, but may be tedious.

Also by removing the gcd of 7 from the numerator and denominator you are essentially changing the question. The remainder is now being limited and will not be the same.
Essentially: $$7^{369}\mod{350} \neq 7^{368}\mod{50}$$ and $$7^{369}\mod{350} \neq 1$$ however if you multipy by the gcd that you divided by in the beginning then you will get the correct answer $$7^{369}\mod{350}=7*(7^{368}\mod{50}) = 7$$

• I think this answer is in the right track – Hailey Jun 7 '16 at 8:56
• @Hailey Thanks, everyone else hasn't realized that by reducing the denominator you are also changing the remainder. Like 16/6 = 8/3 but the remainder for 16/6 = 4 and the remainder for 8/3 = 2. – Noah Geren Jun 7 '16 at 9:01
• thats why after getting 1,we have to multiply with 7 to get 7 – Hailey Jun 7 '16 at 10:47

Modulo arithmetic works here like magic!!

$$7^2\equiv (-1)|50$$ $$\therefore (7^2)^n=(-1)^n|50=1|50$$

The remainder is $7\times 1=7$ !! (as you initially cancelled numerator and denominator with 7)

• though answer won't change mod value is $-1$ and because $n$ is even it works out , so i suggest you edit to remove confusion – avz2611 Jun 7 '16 at 6:18

One thing you can sometimes do with problems like this is to find the remainder modulo the different prime powers and then piece the information together to find the original remainder. Essentially this amounts to using the Chinese Remainder Theorem which you may not have learned yet but one doesn't really need to know it here.

Since $350 = 2\cdot 5^2 \cdot 7$ we compute $$7^{369} \equiv 1^{369}=1 \pmod{2}$$ and $$7^{369} = 7\cdot (7^2)^{184} \equiv 7\cdot(-1)^{184} = 7\cdot 1 = 7\pmod{5^2}$$ and
$$7^{369} \equiv 0^{369}=0\pmod{7}.$$ Now only possible remainders $r< 350$ sastisfying $r\equiv 7 \pmod{5^2}$ are $7, 25+7, \ldots, 325+7$. Since we must also have $r\equiv 0 \pmod{7}$ we are only left with $r=7$ or $r=7\cdot 25+7=182$. Finally using $r\equiv 1\pmod{2}$, we see that $r=7$.

The remainder is 7. \begin{align} & 7^{369} \mod 350 \\ = & 7^{1 + 368} \mod 350 \\ = & 7 \ast 7^{368} \mod 350 \\ = & 7 \ast 7^{4 * 92} \mod 350 \\ = & 7 \ast 2401^{92} \mod 350 \\ = & 7 \ast 1^{92} \mod 350 \\ = & 7 \mod 350 \\ = & 7 \end{align}

• $2401 \not\equiv 1 \bmod 350$. Luckily for you, though, $7^5 \equiv 7 \bmod 350$, so reducing the exponent $\bmod 4$ does in fact work, provided you don't reduce it to zero. – Joffan Jun 7 '16 at 13:53

If I can represent the form $\frac{f(x)}{(x-a)}$,then a will be the remainder.

So,

$$\frac{7^{369}}{350}=\frac{7^{368}}{50}$$

$$=\frac{(7^2)^{184}}{7^2-(-1)}$$

therefore,remainder will be $(-1)^{368}=1$

As I cancelled the fraction with $7$,then again we have to multiply with $7$.

Therefore ultimate remainder will be $7$