Register

GATE IT 2007 | Question: 16

• edited by
11,830 views

6 Answers

Best answer
34 34 votes

Fermat's Little Theorem :

$$a^p ≡ a (\mod p)$$                        
According to Modular Arithmetic    $a ≡ b (\mod n)$ if their difference $(a-b)$ is an integral multiple of $n$ $( n$ divides $(a-b) )$

So, $( a^p - a )$ is an integral multiple of  $p.$ Now as $a$ is not divisible by $p$ so definitely,  $( a^{p-1} -1)$ is an integral multiple of $p.$ This simply means if we divide $a^{p-1}$  by $p,$ the remainder would be $1$. i.e., $ a^{p-1} \mod p = 1.$ 

Put the values in the formula.
$p=17$
So, $p-1 =16.$

Correct Answer: $D$

• edited by
6 6 votes
D) fermat's little theorem
3 3 votes

Using Fermats Little Theorem

p: prime 
a : integer Not prime 
then
ap-1 mod p is always 1 

Here p : 7  Hence p-1  is 16

2 2 votes
The solution is a last ditch effort and meant only for people who can't make sense of fermat's little theorem. Just use the property (a.b) mod p = ((a mod p).(b mod p )) mod p. Now options can be eliminated ( 5, 8 can be eliminated easily ) so consider $3^{16}$.

$3^{16}$ mod 17 = ( ( $3^{4}$ mod 17 ) ( $3^{4}$ mod 17 ) ( $3^{4}$ mod 17 ) ( $3^{4}$ mod 17 ) ) mod 17.

This is ( ( 169 mod 17 ) ( 169 mod 17 ) ) mod 17 =  ( 16 * 16 ) mod 17 = 1.
1 1 vote
You can also use concept from group theory

Let a² = a*a = (a×a) mod 17

Then

3¹=3 , 3²=9 , 3³=10, 3⁴=3²*3²=13 ,

3⁵=3²*3³=9*10=5, .... , 3⁸=3⁵*3³=5*10=16 ,

3¹²=3⁸*3⁴=16*13=4 , 3¹⁶=3¹²*3⁴=4*13=1.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2007 | Quest...Next → · GATE IT 2007 | Quest...
← Previous in category · GATE IT 2008 | Quest...Next in category → · GATE IT 2007 | Quest...
Position:
Show:

Related questions

53 53 votes
9 answers 9 answers
19.4k
19.4k views
Ishrat Jahan asked Oct 29, 2014
19,427 views
GATE IT 2007 | Question: 23
A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division.$(0, 0) \in P.$$(a, b) \in P$ if and only if $(a \% 1...
36 36 votes
7 answers 7 answers
15.6k
15.6k views
Ishrat Jahan asked Nov 3, 2014
15,616 views
GATE IT 2005 | Question: 34
Let $n =$ $p^{2}q$, where $p$ and $q$ are distinct prime numbers. How many numbers m satisfy $1 ≤ m ≤ n$ and $gcd$ $(m, n) = 1?$ Note that $gcd$ $(m, n)$ is the greatest ...
23 23 votes
3 answers 3 answers
14.6k
14.6k views
Ishrat Jahan asked Oct 27, 2014
14,589 views
GATE IT 2008 | Question: 24
The exponent of $11$ in the prime factorization of $300!$ is$27$$28$$29$$30$
61 61 votes
5 answers 5 answers
36.1k
36.1k views
Ishrat Jahan asked Oct 30, 2014
36,075 views
GATE IT 2007 | Question: 85
Consider the $B^{+}$ tree in the adjoining figure, where each node has at most two keys and three links.Keys $K15$ and then $K25$ are inserted into this tree in that orde...