dtweah wrote:If n is a positive integer, n > 4, then what is the remainder if 1+ n^100 is divided by n – 1?
(a) 0
(b) 1
(c) 2
(d) 3
(e) 4
Lots of interesting perspectives to this question. Here is the official OA:
c) This may be observed from the identity
n^100 + 1 = (n – 1)(n99 + n98 + n97 + … + n + 1) + 2. (Note: n can be any positive integer except 1).
My Approach:
I love to turn stuff into binomial to figure out remainders. My goal is to make the first term of a binomial equal to the denominator and aim for 1 as the second term. Using this procedure I write
((n-1 +1)^100)/n-1 + 1/n-1
Once in this form I know all terms of binomial will be factors of n-1 exept last term which will be 1, leaving 2/n-1.
Take for example
(17^2000 +5)/12. What is the remainder. Using the logic above
(17^2000) /12 +5/12
(12 + 5)^2000 /12 + 5/12
Everything in the first term evens out except the last term which will be 5^2000. Reason: You will have 2000Cn where n=0,1,2....2000 and these will be multiplied by 12^2000, 12^1999....12^0 and 5^1......5^2000. So you know all terms are factors of 12 except the last term.
I do similar thing to 5^2000/12=25^1000 /12 =(24+1)^1000 /12 and again everything evens out except 1. The beauty of 1 is that 1^n =1.
So you will have some interger G + 1/12 + 5/12 = G+ 1/2, with remainder 1
With some practise you can get remainders of such fractions with exponents very quickly without writing anything.
