How to handle "((9^x)-2)%5" without overflow at higher x?

user_17575088 0
Viewed 68

I'm doing some exam prep for my discrete mathematics course, and I have to implement the function

f(x) = ((9^x)-2)%5

Since the values of our x in the assignment is 100000 < x <= 1000000, I'm having some trouble handling the overflow

In our assignment there's a hint: "Find a way to apply the modulus throughout the calculations. Otherwise you will get much too big numbers very quickly when calculating 9^x"

I cannot figure out the logic to make this work tho, any help would be appreciated

/* This function should return 1 if 9^x-2 mod 5 = 2 and 0 otherwise */
int is2mod5(int x){
    int a;
    double b = pow(9, x);
    a = b;
    int c = (a-2)%5;

    if (c == 2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
integer-overflow discrete-mathematics c
1 Answers

Since you are calculating modulo 5, multiplications can be done modulo 5 as well. 9 is congruent to -1 modulo 5. Thus 9^x is congruent to (-1)^x modulo 5, i.e. 1 if x is even and -1 if x is odd. Subtracting 2 gives -1 and -3 which are congruent to 4 and 2 respectively.

Thus, f(x) is 4 if x is even and 2 if x is odd.

user_119931210
Related