Saturday, 17 February 2018

modular arithmetic - What is 2632bmod12?




What is the correct answer to this expression:



26^{32} \pmod {12}



When I tried in Wolfram Alpha the answer is 4, this is also my answer using Fermat's little theorem, but in a calculator the answer is different, 0.


Answer



First, note that 26 \equiv 2 \pmod {12}, so 26^{32} \equiv 2^{32} \pmod {12}.




Next, note that 2^4 \equiv 16 \equiv 4 \pmod {12}, so 2^{32} \equiv \left(2^4\right)^8 \equiv 4 ^8 \pmod {12}, and 4^2 \equiv 4 \pmod {12}.



Finally, 4^8 \equiv \left(4^2\right)^4 \equiv 4^4 \equiv \left(4^2\right)^2 \equiv 4^2 \equiv 4 \pmod {12}.



Then we get the result.



There are slicker solutions with just a few results from elementary number theory, but this is a very basic method which should be easy enough to follow.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...