Every day I have a problem while having simple calculations.
Can anyone give a Tip how to overcome? For Example :
How one will calculate the remainder of $ 2^{546}\pmod{43} $ ? Without a calculator ??
And how to go about this?
Asked
Active
Viewed 72 times
3 Answers
3
Hints applying modular arithmetic and Fermat's Little Theorem:
$$546=43\cdot 12+30\implies 2^{546}=2^{42}=1\pmod{43}$$
DonAntonio
- 211,718
- 17
- 136
- 287
-
how would you manage $2^{30}\pmod{43}?$ – lab bhattacharjee Aug 03 '13 at 11:14
-
1$$2^7=128=-1\pmod{43}\implies 2^{30}=(2^7)^4\cdot 2^2=4\pmod{43}$$ – DonAntonio Aug 03 '13 at 11:24
-
that could safely be starting point like DepeHb's answer:) – lab bhattacharjee Aug 03 '13 at 11:31
-
I guess it could be, but I chose another approach. Is there something in my answer unclear to you, @labbhattacharjee ? – DonAntonio Aug 03 '13 at 11:33
3
43 and 2 are coprimes .
Euler number of 43 is 42 .
546 is multiple of 42 .
so remainder is 1 (fermat's theorem ). So no calculator used , yet solved just by observing numbers .
Harish Kayarohanam
- 1,980
- 2
- 15
- 24
2
Notice that $2^7 = 128$ and also $3\cdot 43 = 129$, so $2^7 = -1 \mod 43$. Now $546 = 7 \cdot 78$, so $2^{546} = (2^{7})^{78} = (-1)^{78} \mod 43 = 1 \mod 43$.
Spine Feast
- 4,770