The GATE Grind

GATE 2016 CS (CS2) – Question 39

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Numerical answer

Evaluate $13^{99}\pmod {17}$ as an integer from 0 through 16.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 4.0 to 4.0

Explanation

Fermat’s theorem gives $13^{16}\equiv1\pmod{17}$. Since 99 ≡ 3 modulo 16, reduce to 13³. Now $13\equiv-4$, so $13^3\equiv-64\equiv4\pmod{17}$. The answer is 4.

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →