First index of number in the arithmetic progression (which is multiple of prime)
Time elapsed is almost all in overhead
I'm not sure you can do any better than what you've done.  I tested your program and it ran extremely fast.  In fact, I determined that most of the time was probably being spent bringing up the JVM.  I ran your program with varying test inputs (up to 100000 test case input), and also ran your program without computing the result (just reading the input and outputting one number per test case).  The timings showed that most of the time was being spent just bringing up the JVM (or some other Java related overhead):
100000 test case (times are in seconds)
0.14: bringing up the JVM
0.19: parsing the input and generating output
0.12: calculating the answer
0.45: total time

100 test case
0.14: bringing up the JVM
0.02: parsing the input and generating output
0.01: calculating the answer
0.17: total time

So I believe that your actual algorithm runs for about 0.01 seconds out of 0.17 total time.
C program was faster (less overhead?)
I converted your program to C and tested it to see if it would run any faster.  It did run faster, probably because of the lack of overhead:
100000 test case (C program)
0.29: total time

100 test case (C program)
0.01: total time

Here is the C program, just to show you that it is exactly the same as your java program:
#include &lt;stdio.h&gt;

static long long getPowerValue(long long base, long long primeNo);

int main(void)
{
    int noOfTestCaseT = 0;
    long long firstElement, commonDifference, primeNo;

    scanf(&quot;%d&quot;, &amp;noOfTestCaseT);

    while (noOfTestCaseT != 0){
        noOfTestCaseT--;
        scanf(&quot;%lld %lld %lld&quot;, &amp;firstElement, &amp;commonDifference, &amp;primeNo);
        firstElement %= primeNo;
        commonDifference %= primeNo;
        if(commonDifference == 0) puts(&quot;-1\n&quot;);
        else if (firstElement == 0) puts(&quot;0\n&quot;);
        else {
            long long inverseMod = getPowerValue(commonDifference, primeNo);
            int result = (int) ((inverseMod * (primeNo-firstElement))%primeNo);
            printf(&quot;%d\n&quot;, result);
        }
    }
    return 0;
}

static long long getPowerValue(long long base, long long primeNo)
{
    long long exp = primeNo -2;
    long long powerResult = 1;
    while (exp &gt; 0){
        if ((exp &amp; 1) == 1) powerResult = (powerResult * base) % primeNo;
        base = (base * base) % primeNo;
        exp = exp &gt;&gt; 1 ;
    }
    return powerResult;
}

A slightly faster inverse mod function
From wikipedia, I copied this algorithm for finding the inverse mod.  Supposedly, it is slightly faster than the algorithm you are using.  Using the 100000 test case input, I found that it was a little bit faster, but not by much (maybe 10% faster).  Here is the function (it replaces your getPowerValue function):
private static long inverse(long a, long n)
{
    long t    = 0;
    long newt = 1;
    long r    = n;
    long newr = a;

    while (newr != 0) {
        long quotient = r / newr;
        long tmp;

        tmp  = newt;
        newt = t - quotient * newt;
        t    = tmp;

        tmp  = newr;
        newr = r - quotient * newr;
        r    = tmp;
    }
    if (t &lt; 0)
        t += n;
    return t;
}