# Solving mod congruence

So i have a problem like this

34x ≡ 77 (mod 89)


This is how i try to solve it but it doesn't seem to work :( If anyone can give me a hint on how to proceed from what i have down below would mean a lot thanks.

I first use the Extended Euclidean algorithm to find the inverse down below Since the gcd = 1 i look at the the fact that

37*77-(-32)*89=1


Therefore going from there since we live under mod 89 we can cancel out (-32)*89 so i continue with multiplying the inverse to my original equation.

37*34x ≡ 37*77 (mod 89)


Shouldn't it come out to be: x ≡ 2849 (mod 89) and let that be the answer? I know i am going wrong somewhere all help is appreciated.

Also sorry for formatting if it is bad quite new at this.

$$37(77)\equiv1\pmod{89}$$
In other words, you have that $37$ is the inverse of $77$. What you want is the inverse of $34$. Multiplying both sides by that will yield $x$ on the left hand side.
• I don't quite understand... So would i need to do is plug in the numbers 34, 89 into that sheet and it says -34 13 Since the -34 is with the 34 i multiply them and get -1,156 and that mod 89 = 1? – user2166592 Apr 4 '14 at 22:08
• @user2166592 That second term in your sum is a multiple of $89$. Therefore, if you take both sides $\pmod{89}$, that term drops out completely. And yes, $-1156=-13\times89+1$, so $-1156x\equiv1x\pmod{89}$ – Mike Apr 4 '14 at 22:19