How do I find the remainder when $11^{2013}$ is divided by $61$? Brute force? Without a calculator? How did people do that?
Asked
Active
Viewed 778 times
0
-
HINT: $11^2\equiv -1\bmod 61$ – asatzhh Aug 05 '13 at 14:33
-
What is that mod symbol? – Commander Shepard Aug 05 '13 at 14:34
-
Can someone explain what mod is? – Commander Shepard Aug 05 '13 at 14:35
-
x mod n means the remainder found when dividing x by n. Edit: Though the comment below mine has a more formal definition. – qaphla Aug 05 '13 at 14:38
-
Well,$a \equiv b\bmod p$ means that $a-b=kp$ for some integer k. – asatzhh Aug 05 '13 at 14:38
3 Answers
2
Pattern Observation :
reminder of $11^0 / 61 $ = $1$
reminder of $11^1 / 61 $ = $11$
reminder of $11^2 / 61 $ = $-1$
reminder of $11^3 / 61 $ = $-10$
There after the reminder repeats as 1, 11, -1 ,-10 ,1, 11, -1 ,-10.... so remainders repeat with period $4$
as $2013$ when divided by $4$ gives reminder $1$ , it will have same remainder as reminder of $11^1 / 61 $ . Hence answer is $11$
Harish Kayarohanam
- 1,980
- 2
- 15
- 24
-
$2013\equiv 1\bmod 4$ so the answer should 11. This has nothing to do with $11$ as period is $4$. – asatzhh Aug 05 '13 at 15:00
-
@asatzhh .Thanks for the correction . Enthusiasm made me mad . – Harish Kayarohanam Aug 05 '13 at 15:10
0
Hint:
$61$ is a prime.
Use Fermat's Little Theorem, which says: $a^{p-1} \equiv 1 \ ( \ \text{mod} \ p )$.
ANT
- 24
-
-
There's no variable in it, isn't there nothing to solve for? The x doesn't exist? – Commander Shepard Aug 05 '13 at 14:42
-
It might help to know for this that Fermat's little theorem requires that $p$ is prime, and states that $a^{p - 1} \equiv 1 (\mod p)$ for all $a$, given that $p$ is prime. – qaphla Aug 05 '13 at 14:48
0
Using what asatzhh notes it simply is $11$; because $$11^{2013} \equiv 11*(11^2)^{1006} \equiv 11*(121)^{1006}\equiv 11*(61*2-1)^{1006}\equiv 11*(-1)^{1006} \equiv 11$$
afiori
- 157