In M381 Number Theory Unit 3 I read "...The way to become proficient at solving linear congruences is through plenty of practice at applying the above strategy. ..." - What did I just read?!

Well. This is NOT how it should be done. You need as much 'strategies' for solving linear congruences as you would need for solving a linear equality equation in x. There is a simple formula that solves -any- linear congruence equation.

a x ~ b mod m <=> x = Mod[a PowerMod[b, -1, m], m] where a, b can be ( negative ) fractions. ( Understanding the formula only requires understanding Greatest Common Divisors and the Euclidean Algorithm or one of its improved alternatives )

Example.

7 x ~ 41 mod 101 <=> x = Mod[41 PowerMod[7, -1, 101], 101] <=> x ~ 78 mod 101

Since:

7 * ( 78 + 101k ) - 41 = 505 + 707k which is clearly a multiple of 101 for any k.

3 bloggers

1 week ago

I found this information very helpful in solving the linear equations.The best method to solve these equations is graphical method.

ReplyDelete