Question

Given a==1(mod 7), b== 2 (mod7), and c == 6 (mod7), what is the remainder when a^81 b^91 c^27 is divided by 7?

Answer 1

$a\equiv1\mod7$ means there is an integer $k_1$ such that $a+7k=1$, or $a=1-7k$.

Raising both sides to an arbitrary integer power, we have

$a^n=(1-7k)^n=\displaystyle\sum_{k=0}^n\binom nk(-7k)^k$

Notice that each term in the expansion on the right is a multiple of 7 when $1\le k\le n$, which means modulo 7, the right side reduces to 1. Therefore if $a\equiv1\mod7$, then $a^n\equiv1\mod7$ as well.

More generally, the remainder of a number $N$ upon dividing by 7 will be determined by the constant term (independent of $k$) in the binomial expansion, because any term with a contributing factor of $(-7k)$ necessarily is a multiple of 7.

You then have

$a\equiv1\mod7\implies a^{81}\equiv1^{81}\equiv1\mod7$
$b\equiv2\mod7\implies b^{91}\equiv2^{91}\mod7$
$c\equiv6\mod7\implies c^{27}\equiv6^{27}\mod7$

Now,

$a^{81}b^{91}c^{27}\equiv1^{81}2^{91}6^{27}\mod7=2^{118}3^{27}\mod7$

Recall that for $a_1\equiv b_1\mod n$ and $a_2\equiv b_2\mod n$, we have $a_1a_2\equiv b_1b_2\mod n$, which means we can determine the remainder above by multiplying the remainders given by $2^{118}\mod7$ and $3^{27}\mod7$.

In particular, if $a_1=a_2a_3$, then

$a_1\mod7=\bigg((a_2\mod7)(a_3\mod7)\bigg)\mod7$

Now, we get by this property in conjunction with Fermat's little theorem that

$2^{118}\mod7=\bigg((2^{115}\mod7)(2^6\mod7)\bigg)\mod7$
$=2^{112}\mod7$
$=\bigg((2^{106}\mod7)(2^6\mod7)\bigg)\mod7$
$=2^{106}\mod7$
$=2^{100}\mod7$
$=\cdots$
$=2^4\mod7$
$=\bigg((2^3\mod7)(2\mod7)\bigg)\mod7$
$=2\mod7$

$3^{27}\mod7=\bigg((3^{21}\mod7)(3^6\mod7)\bigg)\mod7$
$=3^{21}\mod7$
$=3^{15}\mod7$
$=3^9\mod7$
$=3^3\mod7$
$=\bigg((3^2\mod7)(3\mod7)\bigg)\mod7$
$=6\mod7$

So we obtain

$2^{118}3^{27}\mod7=\bigg((2\mod7)(6\mod7)\bigg)\mod7$
$=12\mod7$
$=5\mod7$