GATE CS 2016 Set 2 Q29 — Combinatorics: Counting, Recurrence Relations, Generating Functions

We need to find the value of $13^{99} \pmod{17}$.

Since $17$ is a prime number and $\gcd(13, 17) = 1$, we can apply Fermat's Little Theorem:

Substituting $a = 13$ and $p = 17$ gives:

Now, we divide the exponent $99$ by $16$:

Using this, we can simplify the expression:

To compute $13^3 \pmod{17}$ easily, we can use negative residues:

Since $17 \times 4 = 68$:

Thus, the value of $13^{99} \pmod{17}$ is 4.