Let a number $x = 135792468135792468$. Find the remainder when $x$ is divided by $13$.
Is it possible to use Fermat's little theorem on this? I notice that the number is also repeating after $8$.
Would really appreciate any help, thanks!
[Math] Finding the remainder when a large number is divided by 13
elementary-number-theorymodular arithmetic
Related Solutions
According to Fermat's theorem $a^{p-1}\equiv 1 \pmod p$. Here $p=59$ hence $a^{58} \equiv 1 \pmod {59}$.
Now $a^{119}=a^{2\times58+3}=a^{58\times2}a^3\equiv 1\times a^3 \pmod {59}$
In your case $a=5$, therefore $5^{119}\equiv 5^3\equiv 7 \pmod {59}$
So the answer is $7$.
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}$
Best Answer
Brute force isn't demanding so much effort, actually a handful of two-digits subtractions, using the table $13,26,39,52,65,78,91,104,117$.
$$\color{blue}{13}5792468135792468\\\color{blue}{57}92468135792468\\\color{blue}{59}2468135792468\\\color{blue}{72}468135792468\\\color{blue}{74}68135792468\\\color{blue}{96}8135792468\\\color{blue}{58}135792468\\\color{blue}{61}35792468\\\color{blue}{93}5792468\\\color{blue}{25}792468\\\color{blue}{127}92468\\\color{blue}{109}2468\\\color{blue}{52}468\\\color{blue}{46}8\\\color{blue}{78}\\\color{blue}0.$$