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.
 A: 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.
A: You have started rightly as
$$6^{99}=(7-1)^{99}\equiv(-1)^{99}+\binom{99}17\pmod{49}\equiv-1+99\cdot7$$
Similarly for $\displaystyle8^{99}=(7+1)^{99}\cdots\equiv1+99\cdot7$
A: Try working mod $7$.
The rationale behind that is that then you are working with powers of $±1$, which is significantly easier than working with powers of $6$ and $8$. And in this case, this will actually give you the answer.
A: 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 > 0) {
        A[i++] = n & 1;
        n = n >> 1;
    }
    int x = 1;
    int power = b % m;
    for (int j = 0; j < 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 :)
