GateAI
Discrete Mathematics

GATE CSE 2016 Set 2 · Q29

NAT2 marksEasy

Time

The value of the expression 1399(mod17)13^{99} \pmod{17}, in the range 0 to 16, is _______.

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 4

Discrete Mathematics

By Fermat's Little Theorem, if pp is prime and gcd⁡(a,p)=1\gcd(a, p) = 1, then:

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p

Here, a=13a = 13 and p=17p = 17 (which is prime). Thus:

1316≡1(mod17)13^{16} \equiv 1 \pmod{17}

We can decompose the exponent 9999 as:

99=16×6+399 = 16 \times 6 + 3

Therefore:

1399=(1316)6×133≡16×133≡133(mod17)13^{99} = (13^{16})^6 \times 13^3 \equiv 1^6 \times 13^3 \equiv 13^3 \pmod{17}

Since 13≡−4(mod17)13 \equiv -4 \pmod{17}:

133≡(−4)3=−64(mod17)13^3 \equiv (-4)^3 = -64 \pmod{17}

Now, reducing −64-64 modulo 1717:

−64=−4×17+4  ⟹  −64≡4(mod17)-64 = -4 \times 17 + 4 \implies -64 \equiv 4 \pmod{17}

Thus, the value of the expression in the range 0 to 16 is 4.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Discrete Mathematics previous year question is Q29 of the GATE CSE 2016 Set 2 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Discrete Mathematics in GATE CSE

Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 6 of them are 2-mark NAT questions like this one, and GATE CSE 2016 Set 2 has 4.

How GATE tests Discrete Mathematics

More from GATE CSE 2016 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2016 Set 2 · Q29 · NAT

The value of the expression 1399 mod17, in the range 0 to 16, is …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.