GATE CS 2019 Q21 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the value of $3^{51} \pmod 5$, we can use Fermat's Little Theorem.

Fermat's Little Theorem states that if $p$ is a prime number and $a$ is an integer such that $\gcd(a, p) = 1$, then:

Here, $a = 3$ and $p = 5$ (which is prime). Therefore:

Now, we express the exponent $51$ in terms of $4$:

Using this, we can simplify the expression:

Taking modulo $5$ on both sides:

Since $27 = 5 \times 5 + 2$, we have:

Thus, the value of $3^{51} \pmod 5$ is 2.