[SOLVED] Linear Congruence Theory
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.