Friday, January 11, 2019

discrete mathematics - Why can't I use Fermat's Small Theorem to calculate 121212pmod13?



The answer says it is 1, and I understand why. But why can't I use Fermat's Little Theorem on the exponent like this (by "exponent" I mean the entire 1212):




12121(mod13) Is this not a correct use of Fermat's small theorem? In such case the original problem becomes



12112(mod13) But this is clearly the wrong answer to 121212(mod13).


Answer




But why can't I use Fermat's Little Theorem on the exponent like this:



  12121(mod13) a1212a1a(mod13)





You used the wrong modulus 13 vs. 12 in the exponent. Correct is, by modular order reduction



by Fermat mod



by using the correct exponent reduction calculation: \bmod\color{#c00}{12}\!:\ N = \color{#0a0}{12^{\large 12}\!\equiv 0^{\large12}\!\equiv\color{#0a0}0}



Easier: \bmod 13\!:\ a\equiv 12\equiv -1\,\Rightarrow\,a^{\large\color{#90f} 2}\equiv (-1)^{\large 2}\equiv 1\, so we can take \,N\bmod\color{#90f} 2\, vs. \!\bmod 12


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f \colon A \rightarrow B and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...