¿Cuál es el resto al $6^{99} + 8^{99}$ se divide por $49$? ¿Cómo podemos solucionar esto usando el Teorema del Binomio?

Question

He probado como $(7-1)^{99} + (7+1)^{99}$ dividido por $49$. Estoy pegado después de esto. Por favor, ayudar.

Answer 1

Sugerencia: Expanda cada una de las $(7-1)^{99}$ $(7+1)^{99}$ usando el Teorema del Binomio. Nota que los factores son divisibles por $49 = 7^2$, y ver lo que queda.

Answer 2

Usted ha comenzado con razón, como

$$6^{99}=(7-1)^{99}\equiv(-1)^{99}+\binom{99}17\pmod{49}\equiv-1+99\cdot7$$

Asimismo, para $\displaystyle8^{99}=(7+1)^{99}\cdots\equiv1+99\cdot7$

Answer 3

Trate de trabajar mod $7$.

La razón detrás de esto es que, a continuación, se trabaja con potencias de $±1$, que es significativamente más fácil que trabajar con potencias de $6$$8$. Y en este caso, esto va a dar la respuesta.

Answer 4

cómo sobre el uso de modular-exponenciación? Es muy simple y creo que te podría ayudar...

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;
}

acaba de usar y usted puede ver que es muy rápido :)