Breaking a small-scale Example Diffie-Hellman? I started to read about Diffie-Hellman exchange and I encountered a problem which I don't know how to solve.

Given $g=3$, $p=131$, $g^x\bmod p=112$, $g^y\bmod p=74$, compute $g^{xy}\bmod p$


$113$
$110$
$112$
$111$


How could I compute $g^{xy} \bmod p$? Or at least verify which one is correct.
Any idea?
Actually, given $p,g,g^x\bmod p,g^y\bmod p$ deciding whether a given number is actually $g^{xy}\bmod p$ is also known as the Decisional Diffie-Hellman Problem (DDH), which sits at the basis of the (formal) security for the ElGamal cryptosystem and is assumed to be hard for properly chosen values of $p,g$ and $x,y$ in general.

For your particular scenario the best solution is to "just" solve the discrete logarithm problem, ie computing $x$ or $y$ and then computing $g^{xy}\bmod p$ to see which number falls out (113).