Saturday, 13 May 2017

abstract algebra - How to divide a number from both sides of from congruence equation from 7980equiv1pmod100 to 7979equivxpmod100?



This problem is to solve 7979x(mod100). I'm aware this may be solved by binomial expansion or other methods. But when we apply Euler's theorem we obtain 79801(mod100), which seems to be very close to our goal. I just need to divide 79 from both sides.



Now I can do this using a stupid method: by subtracting 100 from LHS to obtain -99, -199, -299,... until "X99" is divisible by 79. I then find that 79×(81)=6399. So we obtain 79806399(mod100) and divides 79 on both sides as 79 is coprime of 100. This gives me 79798119(mod100).



My question is if there is a more systematic/standard way of carrying out a division on both sides, perhaps something related to "inverse" etc. A group theory/ring theory approach is welcome as well.



Answer



Generally this form of the extended Euclidean algorithm is easiest, but here below is quicker.



mod100: (801)(80+1)1,  because  8020



therefore:    7918119  Generally if an0 this iinverts 1a [unit + nilptotent] by using a terminating geometric series:  11a1an||1a1+a++an1






Or using a fractional form of the Extended Euclidean Algorithm, and 7921:




mod 100: 010012155191 or, in equational form



      [[1]]:100x  0[[2]]:21x  1[[1]]+5[[2]]=:[[3]]:5x  5[[2]]+4[[3]]=:[[4]]:x19







Or mod100: 1799921337R|133719  by R= inverse Reciprocity.






Or by CRT: mod25: x179142446.  mod4: x179111,  so 1||x6+25j2+jj1 x=6+25(1+4n)=19|+100n



Beware Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. In particular it is valid to cancel 3 in 99/21 above. See here for further discussion.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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