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 Extended Euclidean algorithm

Since the gcd = 1 i look at the the fact that


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.


I think you've got it backwards. Given your equation, you have


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.

  • $\begingroup$ 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? $\endgroup$ – user2166592 Apr 4 '14 at 22:08
  • $\begingroup$ @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}$ $\endgroup$ – Mike Apr 4 '14 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.