By Inspection #1: Linear Congruences

It always amuses me when the phrase “by inspection” is juxtaposed against a subject that’s very hard to grok. I recently had that experience where together with my two other colleagues (one had a Masters degree and one was taking his Masters degree), we were left staring at a computer screen trying to make sense of an explanation that started with “by inspection”. “By inspection” usually means that if you looked at it casually, the solution to a problem or the understanding of a concept is easily arrived at in a few seconds and not minutes. For some reason though, this is usually what doesn’t happen. Case in point, let’s start with this abstract from A Novel Solution of Linear Congruences:

Although the solutions of linear congruences have been of interest for a very long time, they still remain somewhat pedagogically difficult. Because of the importance of linear congruences in fields such as public-key cryptosystems, new and innovative approaches are needed both to attract interest and to make them more accessible. While the potential for new ideas used in future research is difficult to assess, some use may be found here. In this paper, the authors make use of the remodulization method developed in a previous paper as a vehicle to characterize the conditions under which solutions exist and then determine the solution space. The method is more efficient than those cited in the standard references. This novel approach relates the solution space of cx = a mod b to the Euler totient function for c rather than that of b, which allows one to develop an alternative and somewhat more efficient approach to the problem of creating enciphering and deciphering keys in public-key cryptosystems.”

Did your nose bleed? Cool. Get some tissue. It’s obvious from the abstract that not only are linear congruences particularly hard to understand – it’s also hard to teach. Let’s now to try to go to a linear congruence tutorial in a university website:

Example 5: Solve 1000x º 750 ( mod 7 ).

First we notice that (1000, 7) = 1, and 1 divides 750. Hence we have one solution.

Next we observe that since ( 1000, 7) = 1, we can divide by 250 and get 4x º 3 ( mod 7 ).

This congruency is easy to solve by inspection, and we get x º 6 ( mod 7) as the solution.

( Now, put this value in the original congruency and verify that 6000 and 750 leave the same

remainder when divided by 7. )”

Did you get that? You can probably stare at that problem for days, mkay, a few minutes, and the solution will not dawn at you by “mere” inspection! Let’s try to find a few more of these shall we? 😛


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s