I'm trying to solve $2014^{2015}$ $\pmod {11}$, is there a trick or tip to break the problem down to make it easier to solve?
Asked
Active
Viewed 1,584 times
-1
-
1What do you mean by solve? To simplify it? – Hakim Oct 08 '14 at 14:45
-
Is there a method to solve it without a calculator? – RustyShackleford Oct 08 '14 at 14:47
-
1What do you mean by "solve it"? – Hakim Oct 08 '14 at 14:48
-
1I guess you really want something along the lines of $2014^{2015} \bmod m$? – Daniel Fischer Oct 08 '14 at 14:50
-
I actually made a mistake and forgot the modulus, I edited it – RustyShackleford Oct 08 '14 at 14:52
-
Then note that $a\equiv b \pmod{m} \implies a^k \equiv b^k\pmod{m}$ for all $k$, and recall Fermat's (so-called little) theorem. – Daniel Fischer Oct 08 '14 at 14:54
-
@DanielFischer: In this case, Fermat's little theorem is overkill. – Ross Millikan Oct 08 '14 at 15:01
-
@RossMillikan Yeah, I only looked at the remainder of $2014$ modulo $11$ after I wrote the comment. But since in general, that's useful, I've left it stand. – Daniel Fischer Oct 08 '14 at 15:02
-
To show a modulus in $\LaTeX$, you can use \pmod {modulus}. You don't need the braces for a single digit. It gets you the font and the parentheses. – Ross Millikan Oct 08 '14 at 15:04
3 Answers
1
Your result will have $6658$ digits in base $10$. Alpha seems up to the task, but I got tired of clicking on More Digits. Are you sure you don't want this modulo some number?
Now that you added the $\pmod {11}$, it becomes much easier. Note that $2014 \equiv 1 \pmod {11}$
Ross Millikan
- 374,822
-
-
@NovaDenizen: The $\pmod {11}$ was not there when this answer was written. I have accounted for it now. – Ross Millikan Oct 08 '14 at 14:59
-
-
In the specific case here, you have $1^{2015}$, which is easy. If the base is not $1$, you use Euler's theorem to reduce the exponent modulo $\phi(n)$, Euler's totient function of the modulus. In this case, $\phi(11)=1, 2015 \equiv 5 \pmod {10}$, so the exponent becomes $5$ – Ross Millikan Oct 08 '14 at 19:44
1
It's important to remember that if $a \equiv b \mod m$ then $a \cdot c \equiv b \cdot c \mod m$. From this you can prove if $a \equiv b \mod m$ then $a^c \equiv b^c \mod m$.
So what is the remainder of 2014 divided by 11?
NovaDenizen
- 4,216
- 15
- 23
-
-
-
-
-
okay I'm tracking now, 2014 Mod 11 = 1. What is the next step? – RustyShackleford Oct 09 '14 at 11:13
0
If you are trying to do this efficiently on a computer or something, you can use a binary expansion of $2015$ to calculate the number.
$$2015 = 1 + 2 + 4 + 8 + 16 + 64 + 128 + 256 + 512 + 1024$$
thus
$$x^{2015} = x\cdot x^2\cdot x^4\cdot x^8\cdot x^{16}\cdot x^{64}\cdot x^{128}\cdot x^{256}\cdot x^{512}\cdot x^{1024}$$
This method is much faster than $x \cdot x \cdot x \cdots $.
Bruce Zheng
- 1,039
- 5
- 11