Find the remainder $1690^{2608} + 2608^{1690}$ when divided by 7?
My approach:-
$1690 \equiv 3(\bmod 7)$
$1690^{2} \equiv 2(\bmod 7)$
$1690^{3} \equiv-1 \quad(\mathrm{mod} 7)$[ quite easy to determine , $\frac{2*1690}{7}$..so on]
$\left(1690^{3}\right)^{869} \cdot 1690 \equiv(-1)^{869}1690 \quad(\mathrm{mod} 7)$
$1690^{2608} \equiv -1690 \quad(\mathrm{mod} 7)$….(1)
again for $2608$
$2608 \equiv 4(\bmod 7)$
$2608^{2} \equiv 2(\bmod 7)$
$2608^{3} \equiv1 \quad(\mathrm{mod} 7)$[ quite easy to determine , $\frac{2*2608}{7}$..so on]
$\left(2608^{3}\right)^{563} \cdot 2608 \equiv(1)^{563}2608 \quad(\mathrm{mod} 7)$
$2608^{1690} \equiv 2608 \quad(\mathrm{mod} 7)$…(2)
Now applying property
adding (1) + (2),
$1690^{2608} + 2608^{1690}=918 \quad(\mathrm{mod} 7)$
$\boxed{1690^{2608} + 2608^{1690} \equiv 1 \quad(\mathrm{mod} 7)}$
Is my approach best? or Anyother approach is there comparatively better than it
Best Answer
Seems fine. Try to use smaller number as fast as you can.
Using Fermat's little theorem,
$$1690^{2608}\equiv 3^{2608}\equiv 3^{6(434)+4} \equiv 3^4 \pmod{7}$$
$$2608^{1690}\equiv 4^{6(281)+4}\equiv 4^4 \pmod{7}$$
$$3^4+4^4 \equiv (-4)^4+4^4 \equiv 2(4^4) \equiv 2^9 \equiv 2^3 \equiv 1 \pmod{7}$$
Remark:
Also, I notice the way you compute $1690^3 \pmod{7}$ is by multiplying $2$ with $1690$ and then get the remainder when you divide by $7$. You don't have to do that. To compute $1690^3$, just multiply $2$ and $3$ and you get $6$ directly. That is once you figure out that $1690 \equiv 3\pmod{n}$, we know that $1690^n \equiv 3^n \mod{7}$, work with $3$ rather than $1690$. In fact, for prime $p$, $gcd(a,p)=1$, $a^n \equiv(a\pmod{p})^{(n \pmod{(p-1)})}\pmod{p}$ can reduce the magnitude of the number that you have to work wth.