C# similar to Java:

private static int gcdExtended(int a, int b, out int x, out int y)
{
    if (a == 0)
    {
        x = 0; y = 1;
        return b;
    }
    int gcd = gcdExtended(b % a, a, out int x1, out int y1);
    x = y1 - (b / a) * x1;
    y = x1;

    return gcd;
}
public static int solve(int a, int b, int x)
{
    int fa = a;
    if(b < 0)
    {
        int gcd = gcdExtended(a, x, out fa, out int fb);
        fa = fa < 0 ? fa + x : fa;
    }
    return (int)BigInteger.ModPow(fa, Math.Abs(b), x); // powRussPeas(fa, b, x);
}

passed all tests