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

Question

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.

Answer 1

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$

Answer 2

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

Answer 3

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)

Answer 4

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

Answer 5

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

Answer 6

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