Solving Linear Congruences Using Extended Euclid's Algorithm (10.2) - Linear Congruence Equations and Chinese Remainder Theorem

Learn content

Interactive Audio Lesson

Session 1: Introduction to Linear Congruences

Unlock the classroom podcast

The transcript is free to read. A free account plays the conversation back.

SarahInstructor

Welcome everyone! Today we're diving into linear congruences. Does anyone know how a linear equation translates into the world of modular arithmetic?

Noah

I think it relates to solving equations where we're looking for remainders when divided by a number?

SarahInstructor

Exactly! Linear congruences are like linear equations, but we're interested in remainders instead of exact values. If we have $ax \equiv b \mod N$ , we need to find $x$ such that both $x$ and $b$ give the same remainder when divided by $N$ .

Isabella

So, can you show us an example of that?

SarahInstructor

Certainly! For instance, if $6x \equiv 4 \mod 10$ , can anyone suggest a solution?

Akash

I think $x = 4$ works because $6 imes 4 = 24$ which is congruent to 4 modulo 10.

SarahInstructor

Great! And remember, there's not just one solution; we can express all solutions in the form of $4 + 10k$ . This highlights the infinitely many solutions concept.

SarahInstructor

To summarize, linear congruences provide infinitely many solutions, unlike standard linear equations!

Session 2: Using Extended Euclid’s Algorithm

Unlock the classroom podcast

The transcript is free to read. A free account plays the conversation back.

Create a free account

RobertInstructor

Now, let’s discuss how we can solve linear congruences using the Extended Euclid's Algorithm. What condition do we need about the numbers involved?

Ananya

Is it about the GCD? The GCD of $a$ and $N$ must be 1, right?

RobertInstructor

Exactly! If $ext{gcd}(a, N) = 1$ , we can find the multiplicative inverse of $a$ modulo $N$ .

Noah

And how do we find that inverse?

RobertInstructor

We can use the Extended Euclidean Algorithm. If we have our congruence as $ax \equiv b \mod N$ , after finding $a^{-1}$ , we multiply both sides by this inverse to get $x \equiv b imes a^{-1} ext{ mod } N$ .

Akash

So, after finding $a^{-1}$ , how do we express our solution?

RobertInstructor

Correct! The final result is $x ext{ mod } N = (b imes a^{-1}) ext{ mod } N$ giving us a solution.

RobertInstructor

To recap, we solve linear congruences when GCD is 1 using the Extended Euclidean Algorithm to find multiplicative inverses!

Session 3: Chinese Remainder Theorem (CRT)

Unlock the classroom podcast

The transcript is free to read. A free account plays the conversation back.

Create a free account

SarahInstructor

Now let's shift gears to the Chinese Remainder Theorem, or CRT. What sets CRT apart from what we've learned so far?

Isabella

Isn't it about solving multiple linear congruences at once?

SarahInstructor

Exactly! CRT provides a way to find an unknown $x$ that satisfies a system of linear congruences, especially when each modulus is pairwise co-prime!

Ananya

Can you give us an example of how that would work?

SarahInstructor

Sure! Suppose we have the following system: $x \equiv 2 ext{ mod } 3$ , $x \equiv 3 ext{ mod } 5$ , and $x \equiv 2 ext{ mod } 7$ . How might we approach this?

Noah

So, we first establish the equations and ensure that the moduli are co-prime to apply CRT?

SarahInstructor

That's right! Using CRT, we can express our solution as a linear combination of remainders, leading to unique solutions modulo the product of these moduli.

SarahInstructor

In summary, CRT efficiently resolves systems of linear congruences when moduli are co-prime, giving unique solutions modulo the product.

Audio Book

Voice:

Introduction to Linear Congruences

Unlock the audio lesson

The script is above and free to read. A free account plays it back, in the voice you pick.

Create a free account

So, now let us see how we can solve linear congruences using extended Euclid’s algorithm that is our method number one. So, you are given a, b and N, goal is to find out this unknown x. Now, as we did for our equation in the linear algebra where we said that divide both sides by a provided a is not 0. The question is can we do something similar in the modular world as well that is can we say 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. So, remember, in the earlier; in the last lecture, we proved that the multiplicative inverse modulo N exists only if the number for which you want to find out the inverse is co-prime to your modulus.

Detailed Explanation

In this chunk, the concept of linear congruences is introduced in the context of extended Euclid's algorithm. A linear congruence is similar to a linear equation, but instead of working with real numbers, we deal with integers under a modulus. The goal is to determine an unknown variable x where the linear congruence takes the form 'ax ≡ b (mod N)'. To solve this, we first need to check if the greatest common divisor (GCD) of 'a' and 'N' is 1. If it is, we can find a multiplicative inverse of 'a' in the modular system, which allows us to effectively divide both sides of the congruence by 'a'.

Examples & Analogies

Think of linear congruences like sharing pizzas among friends. If each friend has several pizza slices (represented by integers), but you want to ensure everyone has the same number after sharing (the modulus), you can only divide fairly if the number of slices each friend has and the total number of slices are not entangled (co-prime). If they are, you can easily distribute them evenly (find the inverse).

Using the Extended Euclid's Algorithm

Unlock the audio lesson

The script is above and free to read. A free account plays it back, in the voice you pick.

Create a free account

So, if your GCD(a, N) is 1 then by running the extended Euclid’s algorithm, compute the multiplicative inverse of a namely b, I stress that it is not 1/a in the modular world it is an integer. And now I multiply both the sides of this linear congruence by this a-1. So, I will get this linear congruence and I know that a into a-1 is 1 modulo N and 1 into x modulo N is x. So, I get that x is congruence to b-1 modulo N that means; I can say that the value of x being this plus any multiple of N is a solution for this linear congruence (x = ba-1 mod N + kN).

Detailed Explanation

Once we establish that the GCD(a, N) equals 1, we can find the multiplicative inverse of 'a' using the extended Euclid's algorithm. This gives us an integer 'a⁻¹' such that when multiplied by 'a' gives 1 under modulo N. Multiplying the linear congruence 'ax ≡ b (mod N)' by 'a⁻¹' transforms it to 'x ≡ ba⁻¹ (mod N)'. This means that the value of 'x' can be expressed as 'x =ba⁻¹ + kN', where 'k' can be any integer, thus generating infinitely many solutions of the congruence.

Examples & Analogies

Imagine you've brought various gifts for your friends, and you want to equally distribute them (the congruence). If you have just the right number of gifts (GCD = 1), you can determine how many each friend gets (the inverse). The gifts can come back to you as well (the multiples of N), allowing you to create different combinations of distributions (different values of k).

Handling Non-Coprime Cases

Unlock the audio lesson

The script is above and free to read. A free account plays it back, in the voice you pick.

Create a free account

However, this method will work only if your number a is co-prime to your modulus N. What if the number a is not co-prime to your modulus N, then we have to follow a slightly different approach which is complicated and I am not going to discuss that matter.

Detailed Explanation

This portion outlines a limitation of the method discussed so far. If 'a' and 'N' are not co-prime (i.e., GCD(a, N) is not 1), the existing approach to solve the linear congruence cannot be used directly, and a more complex method would need to be looked into, which goes beyond the introductory explanation in this context. Recognizing when you cannot use the immediate method is important, as it opens up discussions of other techniques or methodologies in modular arithmetic.

Examples & Analogies

Consider trying to share a set of keys among a group. If some of the keys are duplicates and wouldn't fit in some locks (the GCD isn't 1), you can't distribute them equally among your friends in the straightforward way you could if all keys were unique. Instead, you might need to resort to other techniques to find a way to distribute them effectively.

--

10.2. Solving Linear Congruences using Extended Euclid's Algorithm

Interactive Audio Lesson

Overview

Short Summary

Medium Summary

Detailed Summary