Tuesday, 25 February 2014

elementary number theory - Solve congruence equation 3373xequiv2485pmod168



3373x \equiv 2^{485} \pmod{168}



Uhm...I don't even know how to start.




GCD(3373,168)=1, so solution exists.



Usually I would use extended Euclidean algorithm and get the outcome, but it would require multiplying by 2^{485} later, so...well, is there some easier way?


Answer



First of all, 168=2^3\cdot3\cdot7, so you want to solve the three congruences:



3373x\equiv2^{485} \pmod 8 \\ 3373x\equiv2^{485} \pmod 3 \\ 3373x\equiv2^{485} \pmod 7




The first of these three is really 3373x\equiv_8 0, which just implies x\equiv_8 0



For the second, 3373\equiv_3 1, and any odd power of 2 is congruent modulo 3 to 2, so we have x\equiv_32



Thirdly, 3373\equiv_76, and 2^3\equiv_71 \Rightarrow 2^{485}\equiv_72^2=4. Thus, we have 6x\equiv_74, or x\equiv_73



Finally, we use the Chinese Remainder Theorem to find a number satisfying:



x\equiv_80 \\ x\equiv_32 \\ x\equiv_73



In this way, we obtain x\equiv 80 \pmod {168}.


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