If I'm asked to calculate $319^{566} \pmod{23}$, and I know $319 \equiv 20 \pmod{23}$, is it mathematically correct to then calculate $20^{566}$ instead? I feel the answer is yes, but I've an exam tomorrow and would rather a concrete notion rather than an inclination.
Thank you guys!
On
The answer is yes ;here is the concrete explanation of this:-
$ $
we will use the Binomial Expansion of $(x+y)^n$
As we know that
$$(x+y)^n=nC_0y^n+nC_1xy^{n-1}+......+nC_nx^n \tag {1} $$
Now we have $x=(319-20)i.e. 299$,which is divisible by $23$ and $y=20$, which is indivisible by $23$
In equation (1) all the terms of expansion except the $nC_0$ (first) term, are multiples of x i.e. of $299$ so we have to calculate the remainder of only first term i.e $$(x+y)^n\pmod n=y^n{\pmod{23}} = 20^{566}\pmod{23}$$
For integers $a,a',b,b'$ and non-zero integer $c$, if $a\equiv b\pmod c$ and $a'\equiv b'\pmod c$ then $a a'\equiv b b' \pmod c$. This follows by writing the congruences in the terms of their def'ns : We have $x\equiv y\pmod c \iff x=y+c n$ for some integer $n$...... This implies that $a\equiv b\pmod c\implies a^m\equiv b^m\pmod c$ for any positive integer $m$.... for example, by induction on $m$. ( For $m=2$ let $a'=a$ and $b'=b$. For $m=3$ let $a'=a^2$ and $b'=b^2$... etc.)... We also have Fermat's Little Theorem : $$\text {If $p$ is prime and } a \text { is not divisible by $p$ then } a^{p-1}\equiv 1\pmod p.$$ So modulo $23$, we have $319^{566}\equiv 20^{566}\equiv (-3)^{566}\equiv (-3)^{22\cdot 25+16}\equiv (-3)^{16}\equiv ((-3)^4)^4\equiv 81^4\equiv 12^4\equiv (12^2)^2\equiv 6^2\equiv 13.$