What is the remainder when $6^{99} + 8^{99}$ is divided by $49$? How can we solve this using the Binomial Theorem? I tried it as $(7-1)^{99} + (7+1)^{99}$ divided by $49$. I am getting stuck after this. Please help.
Hint: Expand each of $(7-1)^{99}$ and $(7+1)^{99}$ using the Binomial Theorem. Note which factors are divisible by $49 = 7^2$, and see what's left over.
how about using modular-exponentiation ?
It's very simple and I think it could help you...

int b_power_of_n_mod_m(int b, int n, int m) {
    //convert n to binary and save in A array 
    int A[] = new int[20];
    int i = 0;
    // n must be positive
    while (n &gt; 0) {
        A[i++] = n &amp; 1;
        n = n &gt;&gt; 1;
    }
    int x = 1;
    int power = b % m;
    for (int j = 0; j &lt; i; j++) {
        if (A[j] == 1) x = (x * power) % m;
        power = (power * power) % m;
    }
    return x;
}


just use it and you can see that it is very fast :)