$$2014^{2015}\pmod 7$$ How do you find the mod of above without using a calculator.
Asked
Active
Viewed 645 times
1
-
Do the method of repeated squaring. Basically whats 2014^1 mod 7, 2014^2 mod 7, 2014^4 mod 7, until you can get 2015 in terms of the resulting squares. – stackErr May 02 '14 at 18:08
-
Or you could find a pattern such as 2014^(4k) mod 7 = 1...This is just an example – stackErr May 02 '14 at 18:10
-
Is this a question from an on-going contest? – JRN Mar 17 '15 at 04:22
2 Answers
3
The key idea here is Fermat’s little theorem, which tells us that if $p$ is a prime and $a$ is an integer coprime to $p$, then $$a^{p-1} \equiv 1 \mod p$$ Since $7$ is prime and $2014/7$ isn't an integer, we have $$2014^{7-1} \equiv 2014^6 \equiv 1 \pmod 7$$ We can also note that $$2015 = 335 \times 6 + 5,$$ and so we have $$2014^{2015} \equiv (2014^6)^{335} \times 2014^5 \equiv 2014^5 \pmod 7$$ That gets us most of the way, then we observe that $$2014 = 287 \times 7 + 5,$$ and so $$2014^5 \equiv 5^5 \equiv 25^2 \times 5 \equiv 4^2 \times 5 \equiv 16 \times 5 \equiv 3 \pmod 7$$ We can now roll up these congruences to observe that $$\boldsymbol{2014^{2015} \equiv 3 \pmod 7}$$
alexwlchan
- 2,060
2
$$2014^{2015}\equiv 5^{2015}=5^{3\times 671 +2}\equiv 125^{671}\times 5^2\equiv -1^{671}\times 4\equiv -4\equiv 3\text{(mod 7)} $$
Shaswata
- 5,068