Use Fermat's Little Theorem to find the remainder of $5^{15}$ divided by $1337$.
I know Fermat's Little Theorem, but failed to understand how to use it in this.
output.944
Finding remainder using Fermat’s Little Theorm
arithmeticelementary-number-theorymodular arithmeticperfect-powers
Related Solutions
$\require{begingroup}\begingroup\newcommand\Z{\mathbb Z}$Fermat's little theorem tells us something modulo a prime $p$: $a^{p-1}\equiv1\pmod p$: the 'modulus' of the congruence is $p$, not $a$. Now if you're asked to find some residue modulo $13$, then you would use congruences to reduce the given value modulo $13$, i.e., the congruences will have modulus $13$.
If for example you want to find the remainder of $50^{50}$ when divided by (='modulo') $13$, probably the calculations would look like
$$50^{50}\equiv\ldots\equiv\ldots\equiv\ldots\equiv\ldots\pmod{13}$$
and the rightmost dots should contain a number between $0$ and $12$ (inclusive).
I'm not sure why you want to use congruence classes for finding $50^{50}\bmod13$, but, as you're asking: a congruence class modulo $m$ is defined as a (non-empty) subset of $\Z$ in which all elements are (pairwise) congruent modulo $m$. Moreover, the congruence class should contain all integers congruent to its elements.
For example, the congruence classes modulo $2$ are precisely the set of even integers and the set of odd integers. The congruence classes modulo $3$ are the integers of the form $3k$, those of the form $3k+1$, and those of the form $3k+2$. In general, there are $|m|$ congruence classes modulo $m$, and a shorthand to write them is $m\Z,\,m\Z+1,\,m\Z+2,\,\ldots,\,m\Z+|m|-1$.
Now if you're asked to find $50^{50}\bmod13$, since $50^{50}$ is a big number probably you want to reduce the exponent and base, without affecting the value modulo $13$. Fermat's Little Theorem (FLT) is a handy tool to reduce exponents: as $13\nmid50$, FLT gives $50^{12}\equiv1\pmod{13}$. We can use this as follows:
$$50^{50}=50^{4\cdot12}\cdot50^2=(50^{12})^4\cdot50^2\overset{\rm\small FLT}\equiv1^4\cdot50^2=50^2\pmod{13}$$
and look, we've reduced the exponent from $50$ to $2$ by subtracting a multiple of $12=13-1$.
Because $50^2$ is still not so small, let us try to reduce the base modulo $13$. We could replace $50$ by its remainder modulo $13$, which is $11$. This would leave use with calculating $11^2\bmod13$. A little easier is to subtract $13$ one more time:
$$50^2\equiv(50-4\cdot13)^2=(-2)^2=4\pmod{13}.$$
In problem (a), use Fermat's little theorem, which says (or a rather, a very slightly different version says) that for any prime number $p$, and any integer $n$ that's not divisible by $p$, we have $$n^{p-1}\equiv 1\bmod p$$ In particular, use $n=2$ and $p=17$. Keep in mind that $2017=(126\times 16)+1$.
In problem (b), note that $30\equiv 61\equiv -1\bmod 31$ (you don't even have to use Fermat's little theorem here).
In problem (c), use Andre's hint above: if $p$ is any prime number other than $3$, then $p^2\equiv 1\bmod 3$ (which you can see is an application of Fermat's little theorem). What does that mean $8p^2$ is congruent to modulo $3$? What does that mean $8p^2+1$ is congruent to modulo $3$? Can a prime number be congruent to that modulo $3$?
Best Answer
We'll forego using any 'heavy' theory and see what we can come up with to manually crank out the answer.
Anticipating what is to come we write out,
$\tag 1 \;(13 + k)10^2 \equiv k10^2 - 37 \pmod{1337}$
Getting to work,
$\tag 2 5^5 = 3125 = 3100 + 25$
Since $31 = 13\cdot2 + 5$,
$\tag 3 5^5 = (13*2 + 5) 10^2 + 25 = 2(13 + 3) 10^2 - 75$
and so by $\text{(1)}$,
$\tag 4 5^5 \equiv 2(3\cdot10^2-37)-75 \equiv 2 (263) -75\equiv 451 \pmod{1331} $
With the $\text{(4)}$ work behind us, and observing that
$\quad 451 = 450+1 \land 450 = 2 \cdot 3^2 \cdot 5^2$
we apply the binomial theorem,
$\tag 5 (2 \cdot 3^2 \cdot 5^2 + 1)^3= 2^3 \cdot 3^6 \cdot 5^6 + 3\cdot 2^2 \cdot 3^4 \cdot 5^4 + 3\cdot 2 \cdot 3^2 \cdot 5^2+ 1$
Lets us modulo reduce the first (and largest) term on the rhs of $\text{(5)}$ using mental arithmetic and $\text{(1)}$ and, at the start, $\text{(4)}$:
$\quad 2^3 \cdot 3^6 \cdot 5^6 \equiv 8 \cdot 9 \cdot 9 \cdot 9 \cdot 5 \cdot 451 =$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot 9 \cdot 2255 =$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot 9 \cdot (2300 -45) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot 9 \cdot (1000-37 -45) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot 9 \cdot 419 \cdot (-1) =$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot (3600 + 90 + 81) \cdot (-1) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot (2300 -37 + 90 + 81) \cdot (-1) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot (1000 - 37 -37 + 90 + 81) \cdot (-1) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot 9 \cdot 240 =$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot (2100 + 60) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot (800-37 +60) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 9 \cdot (514) \cdot (-1) = $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot (4500 + 90 + 36) \cdot (-1) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot (3200 - 37 + 90 + 36) \cdot (-1) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot (1900 -37 - 37 + 90 + 36) \cdot (-1) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot (600 - 37 -37 - 37 + 90 + 36) \cdot (-1) = $
$\quad \quad \quad \quad \quad \quad \; \; 8 \cdot 615 \cdot (-1) = $
$\quad \quad \quad \quad \quad \quad \; \; 2 \cdot 4 \cdot 615 \cdot (-1) = $
$\quad \quad \quad \quad \quad \quad \; \; 2 \cdot (2400 +60) \cdot (-1) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 2 \cdot (1160 - 37) \cdot (-1) \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 2 \cdot 214 \equiv $
$\quad \quad \quad \quad \quad \quad \; \; 428 \pmod{1337}$
Next we modulo reduce the second term on the rhs of $\text{(5)}$:
$\quad 3\cdot 2^2 \cdot 3^4 \cdot 5^4 =$
$\quad \quad \quad \quad \quad \quad \; \; 3^5 \cdot 50^2 =$
$\quad \quad \quad \quad \quad \quad \; \; 3^5 \cdot 2500 \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 3^5 \cdot (1200 -37) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 3^5 \cdot 174 \cdot (-1) =$
$\quad \quad \quad \quad \quad \quad \; \; 3^3 \cdot (1500 + 30 + 36) \cdot (-1)\equiv$
$\quad \quad \quad \quad \quad \quad \; \; 3^3 \cdot (200 - 37 + 30 + 36) \cdot (-1)=$
$\quad \quad \quad \quad \quad \quad \; \; 3^3 \cdot 229 \cdot (-1)=$
$\quad \quad \quad \quad \quad \quad \; \; 3^1 \cdot (1800 + 180 + 81) \cdot (-1)=$
$\quad \quad \quad \quad \quad \quad \; \; 3^1 \cdot (2000 + 61) \cdot (-1) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 3^1 \cdot 724 \cdot (-1) \equiv$
$\quad \quad \quad \quad \quad \quad \; \; 502 \pmod{1337}$
After modulo reducing the final two terms $\text{(5)}$ we can write
$\tag 6 5^{15} \equiv 451^3 \equiv 428 + 502 + 13 + 1 \equiv 944 \pmod{1337}$