Wednesday, January 1, 2020

elementary number theory - Find 11644mod645


Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem with the solution is attached.


Thanks in advance..


Find 11^{644} \mod 645


enter image description here


Answer



Note that 645=3\cdot 5\cdot 43. Then



11^{644}\equiv (-1)^{2\cdot 322}\equiv 1^{322}\equiv 1\pmod 3 11^{644}\equiv 1^{644}\equiv 1\pmod 5 For the last modulus, we should determine the order of 11\pmod{43}. To this end we first try 11^q for q\mid p-1: 11^2\equiv 35\equiv -8, 11^3\equiv -8\cdot 11\equiv -2, 11^7\equiv (-8)^2\cdot(-2)\equiv -128\equiv 1. So with this 11^{644}\equiv 11^{7\cdot 46}\equiv 1^{46}\equiv 1\pmod{43} and so by the Chinese Remainder Theorem also 11^{644}\equiv 1\pmod {645}


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...