Largest Number that will divide 101100 - 1

[amitdgr]

Q3)The largest number amongst the following that will perfectly divide 101100 - 1 is

1) 100
2) 10000
3) 100100
4) 100000
5) None

Please help me with the approach. I am not sure what the right answer is

[sudhir3127]

The largest number amongst the following that will perfectly divide 101100 - 1 is

i think it shud read as 101^100 -1 if thats the case.. i think its not a Gmat question becasue it will test u with Eulers law. which i guess is not in GMAT.

Anyways .. i cant explain u the rule here...

Eulers rule says..If M and N are 2 co primes to each other.. HCF (M,N) = 1
and N= a^p*b^q.......remainder ( M^#(N)/N) = 1. where #N = N( 1-1/a)(1-1/b)..are Euler Totient function ..

here 101 and 100 are co primes

101 ( 1-1/101) = 100

hence the expression

101^100 will be divisble by 10000 will give an remainder of 1
101100 - 1 is +1-1 = 0.

hence the whole expression is divisble by 10000.

I am sure its tough to understand.. but please let me know if u have any doubts...

[sudhir3127]

whats the OA

[parallel_chase]

The OA has to be 10000, cant be greater than that and cannot be lower than this.

Sudhir is absolutely right on the money with the method.

You can also use trial and error method.

101^2 = 10201. 101^2 - 1 = 10200. This is divisible by 100. Similarly try for 101^3 - 1 = 1030301 - 1 = 1030300.

Therefore, (101^1 - 1) to (101^9 - 1) will be divisible by 100
(101^10 - 1) to (101^99 - 1) will be divisible by 1000,
therefore (101^100 - 1) will be divisible by 10,000.


If it wasnt for sudhir's method i dont think i would be able to solve this question.

Above all this question can never show his face on GMAT. This question is from CAT entrance in India.