I have a question on the calculations in linear congruences if somebody could please clear up for me?
Say for example, the linear congruence:
We check that there are solutions: & incongruent solutions.
Then simplify to:
Then check if they are relatively prime s.t. there exists a multiplicative inverse, , such that :
, such that .
The we use the Euclidean Algorithm to find :
Then going back to the original question:
This was an example in class, but I do believe the last line should say:
My question is:
1. - How do we get the multiplicative inverse from the Euclidean Algorithm?
- Specifically, how does one get from the Euclidean Algorithm?
- Which 3 are we looking at in the algorithm?
2. - How does the original question of translate to ?
- Why is suddenly changed to 7?
Other than that, I think I understand all of the other steps. Just couple of small hiccups in the theory I don't understand. Any help would be much appreciated. Thanks.
(1) Recall that:
So by using the algorithm, we have:
This is equivalent to saying:
Thus, is the multiplicative inverse of 3. But since we usually work with least residues, we consider: to be the inverse.
(2) We're just using the fact that the multiplicative inverse of 3 is 7 (modulo 10), i.e. :
(1) We are just using GCD theorem to find & for , so whatever is, that should be the multiplicative inverse since the GCD is 1, right?
(2) The purpose of multiply both sides of the congruence by the multiplicative inverse is to isolate so that we can find its congruence modulo m to find all solutions?
(1) Yes. Remember, a number has a multiplicative inverse if and only if it is coprime with the modulus, i.e. . And we know that "GCD theorem" of yours (i.e. Bézout's identity).
(2) Exactly. They just wrote it on one line so it may have been a bit confusing that way.