10.1. Introduction to Linear Congruences

In regular algebra, you often come across linear equations of the forms a times x = b, that means you are given some real numbers a and b, and you have to find out the value of this unknown variable x such that this condition is satisfied. And how do we find out the solution for the above equation; by solution of the above equation, I mean to find out the value of this unknown x. And if you know that the value of a is not 0 then I can say that, if you multiply both sides by 1/a, and 1/a is considered as the inverse of a in your regular algebra, then I say that x = b/a. That is a solution for your linear equation here.

In regular algebra, a linear equation is presented in the form of ax = b, where 'a' is a known coefficient, 'b' is a known constant, and 'x' is the unknown variable we want to solve for. If 'a' is not zero, we can isolate 'x' by dividing both sides by 'a'. This gives us the solution 'x = b/a'. This method requires basic algebraic manipulation, and it shows a straightforward way to determine the value of a variable when given certain conditions.

Imagine you have a box of chocolates (the chocolates are represented by 'b') and you want to distribute them equally among your friends (the number of friends is represented by 'a'). If each friend gets an equal amount (that's the variable 'x'), you can easily figure out how much each person gets by dividing the total chocolates by the number of friends.

When I say linear congruence, we are more or less in the same situation except that we are in the modular world, that means everything is given some modulus. So, we will be given some a and b and a modulus N and our goal will be to find out x such that ax ≡ b mod N.

Linear congruences represent equations similar to linear equations, but they operate within a specific modulus or set of integers. This means that instead of finding an exact value of 'x', we are looking for values that satisfy a relationship concerning how numbers group when divided by 'N'. In simple terms, we want to find 'x' such that when you multiply 'a' by 'x', and then calculate the remainder when divided by 'N', you get 'b'.

Think of a clock that resets every 12 hours. If you're currently at 3 o'clock (that’s 'b'), and you want to determine what time you'll be at after multiplying it by (let's say) 2 (that’s 'a'), you perform the operation in terms of the clock face: 2 * 3 = 6, and since it’s less than 12, the answer is just 6; no resetting needed. But what if the operation gives you a number larger than 12? You keep subtracting 12 until you find the time on the clock.

For instance, if I say that I am given 6x congruent to 4 modulo 10, and if I want to find out the value of x, then the possible solutions are x = 4 and x = 9, with infinite solutions of the form 4 + 10k or 9 + 10k.

In this example, the congruence 6x ≡ 4 mod 10 means that if you multiply 6 by 'x' and divide by 10, the remainder should be 4. To solve for 'x', you can test possible values and find that both 4 and 9 work. Moreover, because of the nature of modular arithmetic, adding multiples of the modulus (10 in this case) to these solutions generates an infinite set of valid solutions. This indicates that there isn't just a single value for 'x', unlike traditional equations.

Imagine you receive a set of music playlist restrictions: every 10 songs (modulus), you must start over. If a song is '4' in your playlist after playing '6' songs, it indicates that you can find various ways to arrange your schedule with that given interval, along with many other schedules that might start from '9'.

It is not the case that these are the only solutions; you have an infinite number of solutions. That means any number of the form 4 + 10k, where k can be either positive or negative will also satisfy this linear congruence.

The fact that there are infinite solutions means that, once we’ve found a couple of base solutions (like 4 and 9), we can form more solutions by simply adding or subtracting multiples of the modulus (10). For example, if k = 1, we could add 10 to either 4 or 9, giving us 14 or 19 as more solutions. Similarly, if k = -1, we find 4 - 10 = -6 or 9 - 10 = -1 are also valid. Thus, solutions can stretch indefinitely in both directions.

Consider a bus that arrives every 10 minutes. If you catch it at 4 minutes past the hour, you could also catch it at 14 minutes past the hour, 24 minutes, or at negative times (like -6 minutes means you catch before the hour). Hence, there’s an infinite number of times you could arrive at the bus stop and still catch the bus.

So, now let us see how we can solve linear congruences using extended Euclid’s algorithm. The question is can we divide both sides by a. And divide both sides by 'a' by that I mean multiplying both sides by multiplicative inverse of 'a'. And that is possible only if GCD(a, N) is 1.

To solve linear congruences, especially in the modular system, we can use the extended Euclidean algorithm to find the multiplicative inverse of 'a'. This inverse helps us in effectively isolating 'x' in the congruential relationship, similar to how we isolate variables in typical algebra equations. However, it's crucial to note that this process works only when 'a' and 'N' are co-prime, i.e., their greatest common divisor (GCD) is 1. If they're not coprime, different techniques would be required.

Think of 'a' as a number of people standing in line for a show (modulus 'N'), and you want to find out who gets a ticket for a specific time slot (solving for 'x'). The line only shifts correctly when the number of people ahead (a) isn’t sharing tickets (not co-prime with the venue size N). If there's confusion, you might need a different setup to resolve the ticketing process correctly.

--