MHB Modulos with regards to Congruence

[shamieh]

Can someone explain to me what exactly is taking place on Section 4.4 Problem 6b) in the reversing part of the problem? I understand the first part - that's easy, but I have no idea what is going on in the reversing part of the problem. Thanks in advance.

Here is a link instead of me typing tediously:
The problem reads:
Solve $34x ≡ 77 (mod 89)$
http://www.cs.ucsb.edu/~omer/cs40/hw4_solutions.pdf

 

[chisigma]

Can someone explain to me what exactly is taking place on Section 4.4 Problem 6b) in the reversing part of the problem? I understand the first part - that's easy, but I have no idea what is going on in the reversing part of the problem. Thanks in advance.

Here is a link instead of me typing tediously:
The problem reads:
Solve $34x ≡ 77 (mod 89)$
http://www.cs.ucsb.edu/~omer/cs40/hw4_solutions.pdf

A congruence equation of the type...

$\displaystyle n\ x \equiv m\ \text{mod}\ p\ (1)$

... is solved as follows... indicating with $n^{-1}$ the multiplicative inverse of n mod p [if it exists...], You have...

$\displaystyle n\ n^{-1} x = x \equiv m\ n^{-1}\ \text{mod}\ p\ (2)$

You can find $n^{-1}\ \text{mod}\ p$ applying, for example, the extended Euclidean algorithm [see Modular multiplicative inverse - Wikipedia, the free encyclopedia ]... in Your case is n = 34, m = 77 and p = 89, so that is $34^{-1}\ \text{mod}\ 89 = 55$ and the solution is $\displaystyle x \equiv 77 \cdot 55\ \text{mod}\ 89 = 52$ ...

Kind regards

$\chi$ $\sigma$