Question: I'm trying to digitally sign a message m using El Gamal. So far I've been unable to verify the digital signature ive made using El Gamal.

I am using prime number, **p = 8369**. prime root **g = 3031**. Private key parameter **x = 61**. and the message **m = 9876**

I am calculating **y** and **r** to be:

* y = 3031^61 mod 8369 = 3400
* r = 3031^11 mod 8369 = 2954

Signed message s, s = k^-1 (m – xr) mod (p-1)

* s = 11^-1(9876 – 61\*2954) mod 8368
* s = 13788/11 which cannot be right

I then tried removing the inverse power from 11 which I had seen in another example which produced the following 

* s = 11(9876 – 61\*2954) mod 8368 = 934

When i used **v = g^m mod p** and **w = y^r r^s mod p** I got 

* v = 3031^9876 mod 8369 = 6346
* w = 3400^2954 \* 2954^934 mod 8369 = 855

V and W dont match meaning the signature is invalid and I've made a mistake in my verification. Where did I go wrong and am i on the right track?

Answer: 
In general case, $k^{-1}$ is equal to $x$ such that $x \cdot k=1$. In your question, to computing $11^{-1}$, you must find $x$ such that $x\cdot11=1 \pmod {8368}$. You can compute $x$ by using the extended Euclidean algorithm.
In this case it should be 11^(-1)= 3043 mod 8368

You can use [this calculator](http://public.hochschule-trier.de/~knorr/multiplikativesInverse.php?a=11&n=8368&submit=Berechnen) for example.