Made Easy - Reasoning and Aptitude, GATE 2018 ESE 2018

Question

What is the remainder of 5100/7?

Answer is given as 2. What is the proper method to get it?

Comments

then definitely u will have to adopt conventional method :)

---

Exactly

---

see , after learning the method...important is to analyze it and reduce the time taken for it ....in exams like gate , it will definitely help :)

Answer 1

Method 1:

$5^1 \ mod \ 7 = 5 \ mod \ 7 = 5$

$5^2 \ mod \ 7 = 25 \ mod \ 7 = 4$

$5^3 \ mod \ 7 = 125 \ mod \ 7 = 6$

$5^4 \ mod \ 7 = 625 \ mod \ 7 = 2$

$5^5 \ mod \ 7 = 3125 \ mod \ 7 = 3$

$5^6 \ mod \ 7 = 15625 \ mod \ 7 = 1$

$5^7 \ mod \ 7 =  78125\ mod \ 7 = 5$

$5^1 \ mod \ 7 = 390625 \ mod \ 7 = 4$

$.$

$.$

As we can see that remainder pattern repeats after every six numbers

On dividing 100 by 6 ( as the pattern repeats after every six numbers) we get 1 as remainder

$5^{100} \ mod \ 7 = ( (5^6)^{16} . 5^4 ) \ mod \ 7$

$(A . B) \ mod \ m = ((A \ mod \ m ). (B \ mod \ m )) \ mod \ m$

$(5^6)^{16} \ mod \  7 \ gives \ remainder \ 1$ 

$5^4 \ mod \ 7 \ gives \ remainder \ 2$ 

$(1.2) \ mod \ 7 = 2 \ mod \ 7 = 2$

Method 2:

Fermat's Little Theorem

$Let \ p \ be \ a \ prime \ which \ does \ not \ divide \ the \ integer \ a, \ then \ a^{p-1} = 1 \ (mod \ p).$

$5^{7-1} \ mod \ 7 = 5^6 \ mod \ 7 = 1$

$100 / 6 \ gives \ 16 \ as \ quotient \ and \ 4 \ as \ remainder$

$5^6 \ is \ repeated \ 16 \ times, \ it \ will \ give \ remainder \ as \ 1$

$5^4 \ give \ remainder \ as \ 2$

$(1.2) \ mod \ 7 = 2 \ mod \ 7 = 2$

Answer 2

This theorem is the standard I know and use:

Answer 3

 DEFINITION : a ≡ b mod c 

The above expression means (a-b) is divisible by c

and the expression is pronounced as a is congruent to b modulo c

Now, in my solution I have used 3 theorems

THEOREM 1 :    If a ≡ b mod c  then a^k ≡ b^k mod c for some k belongs to set of natural nos.

THEOREM 2 :    If a ≡ b mod c & d ≡ e mod c  then ad ≡ be mod c

THEOREM 3 :    If a ≡ b mod c & b leaves the remainder r when divided by c then a ≡ r mod c

We know 

             5 ≡ -2 mod 7                    (Look at the definition above)

             5⁶ ≡ (-2)⁶ mod 7               (THEOREM 1)

         => 5⁶ ≡ 64 mod 7

         => 5⁶ ≡  1 mod 7                  (THEOREM 3)

         => (5⁶)¹⁶ ≡ 1¹⁶ mod 7           (THEOREM 1)

        =>  5⁹⁶ ≡ 1 mod 7  ................................. (1)

Again we also know, 5⁴ ≡ 2 mod 7     ( Compute it manually) ....................(2)

So, from 1 and 2 and by using theorem 2 we get

 5¹⁰⁰ ≡ 2 mod 7

So, according to the definition (5¹⁰⁰ -2) is divisible by 7

Hence 5¹⁰⁰ leaves the remainder 2 when divided by 7 (Proved)