New Batches at TathaGat Delhi & Noida!
Modulo Arithmetic – Remainder Theory
by fundoo bond - Friday, 28 September 2007, 03:18 AM
 

cat 2007 cat 2008 remainder theory xat 2008 mba 2008

This extremely useful article for finding remainders has been contributed to TG by Fundoo Bond, another intelligent TGite. All the CAT 2007/2008 who find this article useful are requested to say thanks to Fundoo Bond for his efforts and this wonderful compilation. If you have some interesting article, funda or helpful information to share, please mail it to us and we will post it by your name- Total Gadha

 

The problems of finding the remainder are considered the most dreadful among the number theory problems. Fortunately, if we arm ourselves with some basic theorems, we will see that we can turn these mind-boggling problems into sitters and can ensure some easy marks.

I will be trying to share both the theory and the examples in order to make the concepts clearer. Again friends, do keep in mind that I am not a genius to write these theorems on my own. I have learnt them from various sources and I am trying my best to explain you in my own words.

cat mba
Re: Modulo Arithmetic – Remainder Theory
by Rishi Kapoor - Friday, 28 September 2007, 05:06 AM
 

Thanks Sir...This is what I was searching for...and you have given it in the best time...

You are really TG.....Toooooooo Gooooood

with these Fundoo theorams, you have proved yourself BOND

Re: Modulo Arithmetic – Remainder Theory
by Mady Ahmed - Friday, 28 September 2007, 05:36 AM
  wow,fabulous, fantastic,mind blowing,excellent ...words are short of my dictionary to praise u thanx alot wink
Re: Modulo Arithmetic – Remainder Theory
by shyam Sundar - Friday, 28 September 2007, 08:46 AM
 

hey folks

how to do 40!%83

Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 09:25 AM
  corollary of the Wilson theorem
which will be very useful when solving remainder problems.
From Wilson theorem,
we have (p-1)!%p = (p-1) or -1----(1)
from (1) we can say (p-2)!%p = 1
Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 09:43 AM
  Hey Shyam Sunder
Solution to ur problem

40! mod 83
We know tht--frm Wilson's Theorem
(p-1)!%p = (p-1) or -1(iff p is prime)
so, we can deduce
82!%83=-1 or 82---------------(1)
frm Wilson's Corollary
(p-2)!%p = 1
so, we can deduce here
81!%83=1-----------------(2)
Now 81!=81.80.79.-------.42.41!----------(3)
from 2 and 3
(81.80.79.--------.42.41!)%83=1
-2*-3*-4*-5....-41*41! = 41!*41!%83 = (41!)^2%83 = 1
which is possible only when 41! mod 83=1
because there are even no of terms so negative sign got cancelled

Now we have 41!mod83=1
(41.40!)%83=1
(-42.40!)%83=1
suppose 40!=x
(-42*x)%83=1
which is possible only when x becomes -2 or 81
so ans is 81
Re: Modulo Arithmetic – Remainder Theory
by subhadeep das - Friday, 28 September 2007, 09:43 AM
   how to solve 
 (i) find the remainder of 55555 .... 93 times divided by 98
 (ii) remainder of 2 ^1990 / 1990
Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 09:50 AM
    how to solve 
 
 (ii) remainder of 2 ^1990 / 1990
1990=2.5.199
from Euler's Theorem
phi(2)=1
phi(5)=4
phi(199)=198
2^4=1 mod 5--------(1)
2^198=1 mod 199---------(2)
LCM(4,198)=396
so
2^396=1 mod 1990
2^1980=1 mod 1990(because 1980 is a multiple of396)
so now we remain with
2^10 mod 1990
1024 mod 1990=1024
ans is 1024
Re: Modulo Arithmetic – Remainder Theory
by lavika gupta - Friday, 28 September 2007, 09:51 AM
 

hi Mr. Fundoo Bond.

this is a masterpiece 2 learn the concepts of remainder theorem.i found the chinese remainder theorem a bit more abstruse 2 master,yet other theorems and their enunciation with examples proved really helpful 2 me.hope 2 see such great work again from u.

HATS OFF TO U

Re: Modulo Arithmetic – Remainder Theory
by Catapult!!! On the way - Friday, 28 September 2007, 09:58 AM
  Hi Fundoo Bond!!!


Just one word..

"Superb"..big grin
Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 10:13 AM
  (i) find the remainder of 55555 .... 93 times divided by 98
 98=2.7.7
It is clear that the given no gives remainder of 11.....11 93 times
when divided by 2
so now question remains
(5555....55 93 times) mod 49
55555.......55 93 times
=5x10^92+5x10^51+--------+5
=5[10^0+10^1+--------+10^92]
=5[(10^93-1)/9]
=5[(11111111111111....11 92 times)]
I think ans is 5
plzz check it out
Re: Modulo Arithmetic – Remainder Theory
by jitendra havaldar - Friday, 28 September 2007, 10:23 AM
 

Hi TG,

really an unbelievable article to say the least ....

Continue your good work ...

Thanks,

Jitendra

Re: Modulo Arithmetic – Remainder Theory
by Tom Goel - Friday, 28 September 2007, 10:36 AM
 

hi fundoo,

Though we all know you are a fundoo and a bond.....by sharing this article to have shown altruistic character.Hats off to you.

Thanks

Amit

Re: Modulo Arithmetic – Remainder Theory
by Sanju P - Friday, 28 September 2007, 11:03 AM
 

Hi Fundoo,

Wonderful article and great compilation! smile

Thanks!

S P

Re: Modulo Arithmetic – Remainder Theory
by Software Engineer - Friday, 28 September 2007, 11:18 AM
  FB

Marvelous Methods !  ! ! smile

Thanks,
SE
Re: Modulo Arithmetic – Remainder Theory
by purvi verma - Friday, 28 September 2007, 12:18 PM
  fabulous is the word.....please post some more fundas related to numbers.
Re: Modulo Arithmetic – Remainder Theory
by ankit harish - Friday, 28 September 2007, 12:32 PM
  Awesome Compilation.Thanks a lot bond
Re: Modulo Arithmetic – Remainder Theory
by fundoo bond - Friday, 28 September 2007, 12:40 PM
  Hi TG n all TGites,

Thanks a lot for all the appericiation....Feeling great that my efforts are appericiated...And it gives a grt joy that the article was published exactly as it was submitted tongueout...


regards,
fundoo
Re: Modulo Arithmetic – Remainder Theory
by Dagny Taggart - Friday, 28 September 2007, 01:20 PM
  Kudos Fundoo smile
Re: Modulo Arithmetic – Remainder Theory
by Total Gadha - Friday, 28 September 2007, 01:55 PM
  smile
Re: Modulo Arithmetic – Remainder Theory
by SS VV - Friday, 28 September 2007, 03:01 PM
 

i'm sure u wont believe it ...but was just going to post a request to you asking you to explain these very same theorems ....had seen them in one of your post wherein tg mentioned these are your favourite topics:>

secondly wanted to thank you for all your previous posts...u really took grt pains in explaing all your methods in detail( remember the one in which i asked for digital root and you typed up the detailed approach) and now this....wht can i say but 'rock on dude'

cheers!!

Re: Modulo Arithmetic – Remainder Theory
by imran khan - Friday, 28 September 2007, 03:58 PM
  u guyz are jus fantabulous.............thanx a ton......god bless ur species............smile.
Re: Modulo Arithmetic – Remainder Theory
by Manish Kashyap - Friday, 28 September 2007, 04:51 PM
 

Hi Fundoo,

Its really superb.Only one thing I can say "Fundoo".

Thanks and Regards,

Manish

Re: Modulo Arithmetic – Remainder Theory
by Shubhagata roy - Friday, 28 September 2007, 07:00 PM
  bindassss............cool
rem of
7^115 divided by 114??
Re: Modulo Arithmetic – Remainder Theory
by Abhra Chatterjee - Friday, 28 September 2007, 07:25 PM
  Wonderful job Bond smilesmile..... Please post some thing on Permutation and Probability.
Re: Modulo Arithmetic – Remainder Theory
by Aviator D - Friday, 28 September 2007, 07:29 PM
 

hi fb,

First, thank you for the post. It is very helpful.

In the ques. :  how to solve 
 
 (ii) remainder of 2 ^1990 / 1990
1990=2.5.199
from Euler's Theorem
phi(2)=1
phi(5)=4
phi(199)=198
2^4=1 mod 5--------(1)
2^198=1 mod 199---------(2)
LCM(4,198)=396
so
2^396=1 mod 1990
2^1980=1 mod 1990(because 1980 is a multiple of396)
so now we remain with
2^10 mod 1990
1024 mod 1990=1024
ans is 1024

how can we apply Éuler's theorem in this case? because according to ur post we can only use the theorem when both M(=2) and N(=1990) are coprimes, but this not the case here.

Kindly elaborate.

 

 

Re: Modulo Arithmetic – Remainder Theory
by Deep Agrawal - Friday, 28 September 2007, 07:55 PM
  7^115 / 114.

Phi(114) = 66

hence 7^66 / 114 = 1

Remaining is 7^49 /114

=> ((7^3)^16 * 7) / 114 = 1^16 * 7 / 114 = 7 (Since, 7^3 = 343 => 343/114 = 1)

Re: Modulo Arithmetic – Remainder Theory
by rohit avasthi - Friday, 28 September 2007, 08:30 PM
 

hey,

thnx for this article...i hav been lukin for the totient style of solving method since last few months

the other methods were as fascinating...

......it was extremely helpful...

thnx

rohit

Re: Modulo Arithmetic – Remainder Theory
by rohit avasthi - Friday, 28 September 2007, 08:18 PM
 

hey,

thnx for this article...i hav been lukin for the totient style of solving method since last few months......it was extremely helpful...

thnx

rohit

Re: Modulo Arithmetic – Remainder Theory
by subhadeep das - Friday, 28 September 2007, 10:21 PM
   @AD P
yah , both the answers that you got are right , but i'm having tough time understanding your soln for 2^1990/1990 , specially the part

phi(2)=1
phi(5)=4
phi(199)=198
2^4=1 mod 5--------(1)
2^198=1 mod 199---------(2)
LCM(4,198)=396

please elaborate a little bit more
Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 10:24 PM
  Hi Aviator D
I followed the Euler's Theorem
Euler's Theorem is the generalization of Fermat's Little Theorem, applicable when ur dividend is composite in form.So we first find prime factors for the composite no.
-----After getting prime factors, use Euler's totient to obtain phi(x) values. phi(x)
just define no of no which are coprime to x & <x
-----After getting totient for each prime factor, apply Fermat's little or Euler for each prime factor
Here 1990 is composite
jo first convert it into primes(or prime factors)
Re: Modulo Arithmetic – Remainder Theory
by AD P - Friday, 28 September 2007, 10:33 PM
  Hi Shubhdeep
Wat is Euler's Theorem

Euler’s Theorem:
IF x is any positive integer prime to N then
x^Phi(N)=1(mod N)

N=a^p.b^q.c^r….(prime factors)
Phi(N)=N(1-1/a)*(1-1/b)*(1-1/c)…… and is known as Euler’s Totient Function
Phi(N) defines no of numbers which are less thenN and coprime to N

If N in the above Euler’s Theorem is prime,then Phi(N)=N(1-1/N)=
(N-1)

So if N is prime and x is coprime to N,then the Euler’s Theorem becomes Fermat’s Theorem
As x^(N-1)=1 (mod N)

So in this question
we first break 1990 into prime factors because for Euler condition is that x & N are prime to each other i.e coprimes
1990=2.5.199
and separately apply Euler
hope so its clear now


Re: Modulo Arithmetic – Remainder Theory
by indira ghosh - Friday, 28 September 2007, 11:30 PM
  thanks . i'll practice & try all this method. It was great . but i have problems in geometry so what i will do ?
Re: Modulo Arithmetic – Remainder Theory
by Aviator D - Saturday, 29 September 2007, 07:56 AM
 

@AD P - Thanks for the prompt response.

Hi Aviator D
I followed the Euler's Theorem
Euler's Theorem is the generalization of Fermat's Little Theorem, applicable when ur dividend is composite in form.So we first find prime factors for the composite no.
-----After getting prime factors, use Euler's totient to obtain phi(x) values. phi(x)
just define no of no which are coprime to x & <x
-----After getting totient for each prime factor, apply Fermat's little or Euler for each prime factor
Here 1990 is composite
jo first convert it into primes(or prime factors)

Hi AD P,   

Refering to your post, i understand that we can use Euler's theorem when the dividend(N,here) is a composite no., but additonally is it not required that we ensure that divisor(M,here) is relatively coprime to N ?

finding out the totient for each prime factor of 1990(i.e. 2*5*199) would give us the remainders when 2^1990 is divided by each of 2^1,5^4 and 199^198, how do we then use these remainders obtained to get the final remainder when 2^1990 is divided by 1990 ?

 

Re: Modulo Arithmetic – Remainder Theory
by AD P - Saturday, 29 September 2007, 08:08 AM
  @Aviatore

just take the LCM of powers
Suppose
1990=2.5.199
phi(2)=1
phi(5)=4
phi(199)=198

because 2^phi(n)=1 mod n
2^phi(5)=2^4=1 mod 5
2^phi(199)=2^198=1 mod 199

take LCM of powers i.e. 4 & 198 here

LCM(4,199)=396
so we can say
2^396=1 mod 1990---simple
hope u understand
Re: Modulo Arithmetic – Remainder Theory
by mon haldi - Saturday, 29 September 2007, 11:11 AM
  remainder of 5555......93times divided by 98

    5555555....93 times
=  5(111111....93times)
=  5{11(10^91 + 10^89 + ...+10^3 + 10^1) +1}
=  5{11*10(10^90 + 10^88 +....+10^2 + 1) + 1}......Eq(1)

now 98 can be written as
 = 100-2
or = 10^2 -2
use remainder theorem method and put 10^2 = 2 in Eq(1)

= 5{110(2^45 + 2^44 + ... + 1) +1}
= 5{110(2^46-1) +1} .....Eq(2)
remainder of 2^46 when divided by 98 is 16 (do own your own but be careful
remainder 2^10 / 98 is 44 )

= 5{110(16-1) + 1}
= 5(12*15 +1)
= 5(-16 +1)
= 5 (-15)
= -75
= 23
so remainder is 23
let me know if this is the solution
Re: Modulo Arithmetic – Remainder Theory
by prafull kumar - Saturday, 29 September 2007, 04:37 PM
 

Hi Fundooooooooo, just want to say

Tooooooooooooooooooooooooooo Goooooooooooooooooooooooooooooooooooooooooood

Re: Modulo Arithmetic – Remainder Theory
by prabhjeet kaur - Saturday, 29 September 2007, 06:10 PM
 

helllooo sir ..

thankss for  such a excellent concept but sir  i cldnt be able to take out the print of ths page !! wat shld i do now ?

Re: Modulo Arithmetic – Remainder Theory
by harshal malaviya - Saturday, 29 September 2007, 11:18 PM
 

Thank you,sir,the article is amazing.i was searching for these concepts from a long time...god bless u guys, u guys r doin a damn gud job...some fundas on algebra,would be of great help,especially on hw. to solve prob.on graphs and solving prob.with the help of graphs...thankin u .

harshal.

Re: Modulo Arithmetic – Remainder Theory
by AD P - Saturday, 29 September 2007, 11:28 PM
  @mon Haldi
ur solution is correct
gud solution

can u help me in following question

40! mdo 83
Re: Modulo Arithmetic – Remainder Theory
by Naveen Naveen - Sunday, 30 September 2007, 12:34 AM
 

This is really a great stuff...and this site is cool

hanks a lot...smile

Re: Modulo Arithmetic – Remainder Theory
by vyom bharadwaj - Sunday, 30 September 2007, 11:51 AM
 

really a grt..stuff...

was actually looking for this one...in a compiled format...

and...AAAAHHH!!! here it is ..

thx fundoo.. big grin

Re: Modulo Arithmetic – Remainder Theory
by mon haldi - Sunday, 30 September 2007, 06:52 PM
  hi AD P

u ve attempt all most correct
for 40! mod 83 until
41!^2 mod 83 =1
41! mod 83 = 1 or -1
thn 41!^2 mod 83 = 1
there must be some theorem 4 it
i didnt got the ans bt it ll be 2 or 81
TG ll help to find the correct solution

WHAT DO U SAY TG ABT THS PRBLM

post d solution if anyone has it

Re: Modulo Arithmetic – Remainder Theory
by parag kumar - Monday, 1 October 2007, 02:06 AM
  why can't 41!%83 be -1 ?
Re: Modulo Arithmetic – Remainder Theory
by AD P - Monday, 1 October 2007, 07:21 AM
  @ mon haldi
Wilson's Theorem
Re: Modulo Arithmetic – Remainder Theory
by mon haldi - Monday, 1 October 2007, 11:53 AM
 

i dnt mean to say that

41! mod 83 cant be -1

yes it  can be -1 or 1 

n thus i predicted ans is either 2 or 81

bt which one is correct i dnt knw

Re: Modulo Arithmetic – Remainder Theory
by Totalgadha fan - Monday, 1 October 2007, 01:12 PM
  2 2 2 2 2 2 2 2 2 2 gud
Re: Modulo Arithmetic – Remainder Theory
by parag kumar - Tuesday, 2 October 2007, 12:01 AM
 

I have a big doubt on your approach. 2^4 mod 5=1 and 2^198 mod 199=1 doesn't mean that 2^396 mod 1990=1. It can even be checked by the fact that 2^396 and 1990 are both even and hence the remainder should be even. My solution is like this -

2^1990 mod 1990 = 2^1989/(199*5)

using chinese remainder theorum,

2^1989 mod 199(A) = 114(r1)

2^1989 mod 5(B)= 2(r2)

for 199x+5y=1, x=-1 and y=40

hence remainder = 199*2*-1+114*5*40=22402

or, 22402-995*22=512

since the numerator and denominator were both divided by 2 hence the actual remainder is 512*2=1024.

 

Re: Modulo Arithmetic – Remainder Theory
by Total Gadha - Wednesday, 3 October 2007, 04:23 AM
  Remainder when 40! is divided by 83:

We know that 82! + 1 is divisible by 83.

82! = 1 × 2 × 3 × .... × 39 × 40 × 41 × 42 × ... 81 × 82
--> remainder by 83 = 1 × 2 × 3 × .... × 39 × 40 × - 42 × - 41 × - 40 × - 39 × ... × - 3 × -2 × - 1
= (40!)2 × 42 × 41 ---> remainder with 83 = R2 × 62.

Nor R2 × 62 + 1 is divisible by 83 --> R2 × 62 + 1 = 83k --> R2 = (83k - 1)/62 ---> k = 3 and R2 = 4 --> R = Â± 2 = 2 or 81. 
Re: Modulo Arithmetic – Remainder Theory
by Rishi Kapoor - Wednesday, 3 October 2007, 04:36 AM
  Hey TG please look at the blog entries and reply my query that I have posted there...
Re: Modulo Arithmetic – Remainder Theory
by mon haldi - Wednesday, 3 October 2007, 06:40 AM
  hi TG

bt question remains the same

what is the exact ans
b/w  2 & 81
Re: Modulo Arithmetic – Remainder Theory
by Neophyte 2CAT - Wednesday, 3 October 2007, 03:25 PM
  nice examples to cover all the concepts thank you very much
Re: Modulo Arithmetic – Remainder Theory
by Nitin Singhal - Wednesday, 3 October 2007, 04:59 PM
 

Hi TG,

yesteday i was struggling with a problem which ccomes under remainder theory.Please explain as i tried to solve it with above given theoroms but resulted in a very complex solution.Just tell me if this problem could be solved in any simpler way.The problem is

3^1001 is devided by 1001 then what is the remainder.

Many thanks,

Nitin

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Thursday, 4 October 2007, 01:23 PM
 

@Shubhagata roy

rem of
7^115 divided by 114??

7^3=343

7^115=7^(3*38+1)

=>7^115=(343^38)*7

So, the qstn is now (343^38)*7/114.

Also,114*3=342.i.e 1 less than 343

Therefore by remainder theorem it becomes = (1^38)*7/114 =7/114

 =>Ans is 7

Re: Modulo Arithmetic – Remainder Theory
by fundoo bond - Thursday, 4 October 2007, 03:05 PM
  hi nitin,
1001 is a prime no. if i m nt mistaking...so its euler no. is 1000.hence rem ll be 3?whts d given ans?
Re: Modulo Arithmetic – Remainder Theory
by Nitin Singhal - Thursday, 4 October 2007, 06:53 PM
 

No fundoo bond

1001 is not a prime number.It is devisible by 7,11 and 13.

The answer is 947.

Re: Modulo Arithmetic – Remainder Theory
by Total Gadha - Thursday, 4 October 2007, 10:31 PM
  Hi Nitin,

1001 = 7 Ã— 11 × 13
Now, 31001 when divided by 7, 11, and 13 gives remainders 5, 3 and 9, respectively. Let N = 31001.
N = 7a + 5, N = 11b + 3, N = 13c + 9. Multiply first equation by 22, second equation by 21.
22N = 154N + 110
21N  = 231N + 63, Subtracting we get,
N = 47 - 77k ---> 78N = 3666 - 1001M
Also, N = 13c + 9 ---> 77N = 1001c + 693

Subtracting N = 2973 - 1001L = 2002 - 1001L + 971

Therefore, the remainder is 971.

Total Gadha
Re: Modulo Arithmetic – Remainder Theory
by Ankush Jain - Friday, 5 October 2007, 02:12 AM
 

1001 = 77 * 13.

If we use chinese remainder theorem also,

a = 77, b = 13

r1 = 47, r2 = 9

x = -1, y = 6

Therefore remainder = axr2 + byr1 = -77*9 + 13*6*47 = 2973

Remainer (2973/1001) = 971.

So, i think 971 is the answer 

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Friday, 5 October 2007, 01:31 PM
 

@ Deep Agrawal - for 7^115 / 114.

Phi(114)=36 and not 66.... .i.e. 114(1-1/2)*(1-1/3)*(1-1/19) = 36

therefore we are left with 7^7/114 and 7^3/114=1

 

=>7^7=7^6.7 =>qstn becomes 7/114= ans=7

Re: Modulo Arithmetic – Remainder Theory
by Deep Agrawal - Saturday, 6 October 2007, 01:24 AM
  @Varun

Thanks for pointing it out. Am sorry for the mistake smile
Re: Modulo Arithmetic – Remainder Theory
by Amalesh Bandopadhyay - Saturday, 6 October 2007, 01:58 PM
  U r really a champ..  Thanks for the wonderful article...
Re: Modulo Arithmetic – Remainder Theory
by Ameya Raich - Saturday, 6 October 2007, 10:27 PM
  Hello sir..
 Could you pls tell me how to use above identities in solving sums like :
remainder of:
1)  77777777.... (37 digits) mod 19 ?
2)  123412341234 ... (89 times) mod 19 ?
is there anything else we need to know to solve these ?
My friend says for Q1. we can use 7777..18 times mod 19 =1 since Euler of fi(19) =18... but how can we use this Fermat's little thm on "no. of DIGITS" ??
Re: Modulo Arithmetic – Remainder Theory
by Sageer Abdulla - Saturday, 6 October 2007, 10:31 PM
 

Reminder(2^1990)divided by 1990

In this case N=1990 =2.5.199
so find the reminder when divided by 199 and multiply it wid 2*5 since 2 and 199 are co primes. again divide by 199 if its divisible.. thats the reminder..

suppose if we get 25 as reminder when divided by 199.

multiply 25 wid 2*5 ie 10.

we will get 250.. which should be divided by 199 agion to get the reminder..

this should be the simplified version of answer.

Re: Modulo Arithmetic – Remainder Theory
by rishu batra - Monday, 8 October 2007, 08:10 AM
 

thanx fundooo for this mindblowing tutorial...it is of immense help...but i have a big doubt...does modular arithmetic follow these rules?:

1.(remainder of 1 expression)*(remainder of second expression)=(remainder of overall expression)

2..(remainder of 1 expression)+(remainder of second expression)=(remainder of overall expression)

3..(remainder of 1 expression)-(remainder of second expression)=(remainder of overall expression)

does this mean if 1998*1999*2000 is divided by 47,we find remainders individually with respective terms in the expression n multiply them to get the final answer??

Re: Modulo Arithmetic – Remainder Theory
by Shashank Balooni - Monday, 8 October 2007, 11:19 AM
  Hi FUNDOO .....U have really xplained the doubts lucidly .....Thanks a lot
smile
I have 2 questions ...
1.39! divided by 41  in this question i didnt get 40!=41K+40 ..
Some more question on wilson theorem...

2.Please giv some example where we cant apply any other theorem but only Chinese Remainder Theorem

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Monday, 8 October 2007, 03:01 PM
 

@ rishu batra

Though I was not asked but still i felt like answering it...smile

Answer to ur qstn is a simple yes..

the rule says that all the operators (+,-,*) remain as they are and need to be operated on the individual remainders  which are obtained by separately finding out remainder for each of the numerators..

 

Re: Modulo Arithmetic – Remainder Theory
by Shashank Balooni - Monday, 8 October 2007, 03:12 PM
  Hi guys
This seems quiet Diff prob ..please help
mixed
Remainder for ..by Chinese theorem
(777)^777/1000
Re: Modulo Arithmetic – Remainder Theory
by fundoo bond - Monday, 8 October 2007, 03:48 PM
  hi rishu,
u hv asked really nic qns n i think i shld hv included these things in the article...but anyways it's better late than never... smile

ur 1st statement "1.(remainder of 1 expression)*(remainder of second expression)=(remainder of overall expression)"

yes this is true...i ll take d example u hv given....
1998*1999*2000 is divided by 47

find rem for 1998,it is 47.so for 1999 n 2000 it ll be 48 and 49 resp.

so rem ll be 24*25*26 % 47..





Re: Modulo Arithmetic – Remainder Theory
by sachin singh - Monday, 8 October 2007, 07:43 PM
  Is the answer for this is 72???
i have used euler theorem here....confirm me the answer.
Re: Modulo Arithmetic – Remainder Theory
by love kumar - Monday, 8 October 2007, 10:56 PM
 

Hi

there is a error in d solution of ex. to find last 3 digit of 57^802 while calculating ©(1000)=1000(1-1/2)(1-1/4),it shud be 1000(1-1/2)(1-1/3) as 1000=(2^3)(5^3)..

bye n tk cr

Re: Modulo Arithmetic – Remainder Theory
by Amit Chandaliya - Tuesday, 9 October 2007, 08:14 AM
 

hi all,

I find one problem while solving one of the papers.

Q. what will be the remainder if (2222^5555+5555^2222) is divided by 7 ?

plase give answer with complete solution...

Re: Modulo Arithmetic – Remainder Theory
by sukshima naik - Tuesday, 9 October 2007, 11:56 AM
  thanx a lot sir.....i have not joined any coaching centre here....as i find more materials here from u than any coaching classes......these fundoo theorams r not even in good books..... sir i will be appearing cat-2008 & i have started my prep. on QA now....but i need some basics or correct planning & method to be strong in QA.SO sir can u help me to choose a correct path....
Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Tuesday, 9 October 2007, 01:17 PM
 

@ Amit Chandaliya

 

Hi Amit, perhaps this has been discusse in the forum before also...

2222 = 7*317+3 and 5555 = 7*793+4

=> Qstn becomes (3^5555+4^2222)%7

3^3 % 7 = 27%7 = -1

4^3 % 7 = 64)%7 = 1

=>3^5555 = 3^(3*1851+2)

and 4^2222= 4^(3*740+2)

now, we have first part of qstn as :-

 ((27)^1851 * (3^2)) %7 = (-1)^1851 * 2 =-1*2 = -2

and second part is :-

((64)^740 * (4^2)) %7 = (-1)^740 * 2 =1*2 = 2

 

Therefore answer wud be (-2)+(2) = 0

Hope this is a full solution.....smile

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Tuesday, 9 October 2007, 01:24 PM
 

 @love kumar

U found a mistake but u didn't look into it carefully.Its a typo(printing mistake)  not an error.

The typo is dat  Â©(1000)=1000(1-1/2)(1-1/4) shud be 1000(1-1/2)(1-1/5) as as 1000=(2^3)(5^3).. => u have to take 2 and 5 as "a" and "b" respectively.

The resultant value comes to 400 only...

 

so solution is alright...hope you got ur mistake....

Re: Modulo Arithmetic – Remainder Theory
by Shashank Balooni - Tuesday, 9 October 2007, 02:47 PM
  Hi  PLease Somebody solve this one
This seems quiet Diff prob ..please help
mixed

Find the Remainder for this expression..
(777)^777/1000

(Chinese theorem may help here)
Re: Modulo Arithmetic – Remainder Theory
by rishu batra - Tuesday, 9 October 2007, 07:42 PM
 

hi all,

how do we solve the followin problem:

find the remainder when 123412341234.....(89times)is divided by 19?

Re: Modulo Arithmetic – Remainder Theory
by Ameya Raich - Tuesday, 9 October 2007, 09:47 PM
 
tens digit of 2^999 = ?

Now obviously we have to divide by 100 and find the remainder.
If we use Euler, then some things going wrong and i cant fine out wat ?

See..
     Rem (2^999/ 100)
 = 4* (Rem of (2^997)/25)       ........(1)

Now ::
Rem of (2^997)/25
since 2 and 25 are coprime.
Euler totient of 25 = 20,
Rem of 2^20/25=1

Thus Rem of 2^980/25=1.
Thus we have to find Rem(2^17/25)

now, 2^11/25 yield 24 as remainder, we know,
thus 24* Rem(2^6/25)
= Rem (24*14/25)
= 11.

Now from step (1) above final remainder = 11*4 = 44.

Where am i going wrong ???????


:::::::::::::::::::::::::ALTERNATE ::::::::::::::::::::::::::

     Rem (2^999/ 100)
 = 4* (Rem of (2^997)/25)       ........(1)
now, we know , rem(2^11/25)= -1
thus,
Rem( (2^990)/ 25)
= Rem (2^11/25 * 90) =1.
Thus we are left with Rem (2^7/25) = 7;
now frm step (1) above ,
final answer is 4*7 = 28 .

Where am i going wrong ???????

?????????????????????????????????????????????????????????????







Re: Modulo Arithmetic – Remainder Theory
by love kumar - Tuesday, 9 October 2007, 09:55 PM
 

hi varun!!

pretty rite..

thanks

Re: Modulo Arithmetic – Remainder Theory
by RAMA KRISHNA TANKU - Wednesday, 10 October 2007, 08:04 AM
  thanku u fundo , it is very useful for me , iam very much in confusion before this .Any way once again thank u
Re: Modulo Arithmetic – Remainder Theory
by monu varshney - Wednesday, 10 October 2007, 12:27 PM
 

As the theories given by fundoo and tG r fabulous. But I have some queries.

IN wilson’s theory,how the 2nd example gives 1 remainder.pleae somebody make it clear. Treat this question as u have not done 1st example of same theorem.

Also explain the Wilson’s theorem morefor my convenience.

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Wednesday, 10 October 2007, 02:04 PM
 

@Ameya Raich

 

you are getting wrong in the very preliminary step.

which is 2^11 % 25= -1  => wrong buddy

infact it shud be 2^10 % 25= -1

Follow the very same steps that u have taken.....

You will get the very same answer in both the case and for ur ease i wud say the answer is 88

Also u said that 

Rem( (2^990)/ 25)
= Rem (2^11/25 * 90) =1.
Thus we are left with Rem (2^7/25) = 7; =>wrong,it shud be 3
now frm step (1) above ,
final answer is 4*7 = 28 .

I am rewriting the above steps with corrections

Rem( (2^990)/ 25)
= Rem (2^(10*99+7)/25) => (-1)^99 * rem (2^7 /25) => -3 =>22

final answer is 4*22 = 88


 

Re: Modulo Arithmetic – Remainder Theory
by Varun Choudhary - Wednesday, 10 October 2007, 02:49 PM
 

hi everybody.....

plz solve (19^36 + 17^36) %111...

Re: Modulo Arithmetic – Remainder Theory
by Naresh K - Wednesday, 10 October 2007, 05:08 PM
  Thanx Bond..That was a good compilation

I felt Chinese Remainder Theorem to be a little redundant. Frankly we can always logically evaluate the answer in such given conditions.

In ur example, 3^101 % 77 u have arrived at the number of the form 7a+5 or 11b+3. So the remainder will be the least number common to such series. Quickly it will give 47 !!

Looking fwd for more to come
Cheers
Neo
Re: Modulo Arithmetic – Remainder Theory
by fundoo bond - Wednesday, 10 October 2007, 06:17 PM
  Hi Shashank,
Are u sure the qn. is (777)^777/1000 ?? I am finding it diff. to crack it...might be it is (777)^777/100 ?? wht do u say? Any takers for this? but frankly i think u wont find such pbms in CAT... smile

regards,
fundoo
Re: Modulo Arithmetic – Remainder Theory
by Pavan Padekal - Friday, 12 October 2007, 08:37 AM
  Shouldnt phi(63) in the first example be 36 and not 18 as mentioned?
It doesnt make a difference to the final answer though
Re: Modulo Arithmetic – Remainder Theory
by Shashank Balooni - Friday, 12 October 2007, 11:01 AM
  hi
Fundoo Bond tongueout 
(777)^777/1001

oops take the question as abv 1000 replaced by 1001(7*11*13)


Re: Modulo Arithmetic – Remainder Theory
by Total Gadha - Monday, 15 October 2007, 01:55 AM
  1. 777777/1000 --> Remainder = 797 (Use Binomial to find the last three digits)

2. 644
Re: Modulo Arithmetic – Remainder Theory
by Anish Rai - Monday, 15 October 2007, 05:48 PM
  Nice one TG
Re: Modulo Arithmetic – Remainder Theory
by HARI POTTER - Tuesday, 16 October 2007, 08:57 AM
  hi haldi

can you pls explain the remainder theorem u used...

substitution of 10^ 2 by 2
Re: Modulo Arithmetic – Remainder Theory
by HARI POTTER - Tuesday, 16 October 2007, 10:02 AM
  hi TG

how do u find last n digits using binomial theorem.... atmost how many 'last' digits can we find....pls  explain how u got 797 in 777^777/1000.. i learnt how to find the last 2 from your posts... but last 3 i dunno..

thankssmile
Re: Modulo Arithmetic – Remainder Theory
by fundoo bond - Thursday, 18 October 2007, 07:30 PM
 

hi shashank,

if this is the qn...

(777)^777/1001

1001=(7*11*13)

so basically u have to find remainder of

(777)^776/(11*13)

do this by chinese thm and then multiply the resultant rem by 7.

if u still need my assistance done be afraid to revert.

regards,

fundoo


 

Re: Modulo Arithmetic – Remainder Theory
by ashish bhardwaj - Saturday, 20 October 2007, 11:50 PM
 

hi varun ,

it can be solved using chinese remainder theorem

 .. (19^36 + 17^36) %111 so i will divide this into two part

fist 19^36%111 and other 17^36%111

so our  111 ==> 3*37 both are prime

so a=3  now we have to find the remainder for

19^36/3 =>1=r1

19^36/37=> 1=r2 so  and

our a and b are 3 and 37 so   3*x+37*y=1 it gives me x=-12 and y=1

so   3*-12*1+37*1*1=  -36+37 =>1

now same way it can be done for 17^36

so 17^36/3 => 2^36/3 => 8^12/3 => (-1)^12/3 =>1

17^36/37 =>1

so it will also follow the same pattern and answer will be 2 =>1+1...

 

Re: Modulo Arithmetic – Remainder Theory
by mojo bond - Sunday, 21 October 2007, 12:00 AM
  Hi Fundoo

Please clarify one thing in the question which shashank asked i.e. 777^777/1001 cancelling 7 leaves 111 extra also i.e it becomes (777^776 * 111) / 11*13.So altho 777^776 /11*13 is managable but how to take into account 111 ?


Plz help
Re: Modulo Arithmetic – Remainder Theory
by ambar patil - Friday, 21 March 2008, 05:49 PM
 

find the last three digits of 31994 .

Now as per Euler theorem , Rem [3400/1000] = 1 .

Similarly , Rem  [32000/1000] = 1 . Can anybody tell me how do we proceed further ? How do we handle the extra 36 ? sad 

Re: Modulo Arithmetic – Remainder Theory
by TG Team - Saturday, 22 March 2008, 01:40 PM
  find the last three digits of 31994 .
Hi Ambar
Here I go. smile
32000 = 36*31994 = 1(mod1000)
Let 31994 = x(mod1000) and as 36 = 729
=> 729x = 1(mod1000)
=> 729x - 1000y = 1
Now using Eulid's Algorithm
1 = 3(1) - 1(2)
1 = 3(1) - 1(8 - 2*3)
1 = 3(3) - 1(8)
1 = 3(19 - 2*8) - 1(8)
1 = 3(19) - 7(8)
1 = 3(19) - 7(84 - 4*19)
1 = 31(19) - 7(84)
1 = 31(187 - 2*84) - 7(84)
1 = 31(187) - 69(84)
1 = 31(187) - 69(271 - 187)
1 = 100(187) - 69(271)
1 = 100(729 - 2*271) - 69(271)
1 = 100(729) - 269(271)
1 = 100(729) - 269(1000 - 729)
1 = 369(729) - 269(1000)
=> 31994 = 369mod1000smile
Re: Modulo Arithmetic – Remainder Theory
by Vipul Patki - Monday, 24 March 2008, 04:52 AM
 

Too good...Some of the problems are solved in Arun Sharma's book and it is always good to see alternative solutions to such kind of problems.

Regards,

Vipul

Re: Modulo Arithmetic – Remainder Theory
by ambar patil - Monday, 24 March 2008, 04:50 PM
 

hey kamal  ,

Thanks for posting the solution ... but i am not aware of the Eulid's theorem ... can you please post that too ??

However , i have found one other way to solve the problem

31994 = 9997=( 10 - 1) 997 .

now using binomial expansion , we can get the laste three digits . the answer comes outtabe 369 .  

Re: Modulo Arithmetic – Remainder Theory
by Hungry Gadha! - Friday, 18 April 2008, 07:50 PM
 

Just Amazing JOB.....fundoo..smile fantastic...stuff.

Thanks,

HG

Re: Modulo Arithmetic – Remainder Theory
by Ams Kul - Sunday, 4 May 2008, 12:18 PM
  Hi Fundoo
Thanks a lot for the article .. cool
Re: Modulo Arithmetic – Remainder Theory
by vamshi machanapally - Sunday, 11 May 2008, 12:30 PM
  Hi... I want the solution for the prblem given below
what is the remainder when 7^7^7 is divided by 13...
Thanks in advance smile
Re: Modulo Arithmetic – Remainder Theory
by vamshi machanapally - Sunday, 11 May 2008, 07:44 PM
  Hi guys.. got the procedure smile
Re: Modulo Arithmetic – Remainder Theory
by a a - Monday, 12 May 2008, 10:01 PM
 

Hi vamshi

is the answer 6???

please confirm

Re: Modulo Arithmetic – Remainder Theory
by Nikunj Gupta - Monday, 19 May 2008, 09:11 AM
 

Hi....One thing that I am not getting in Chinese theorm is how to set values for x,y because there might be the case when there are more than 2 values satisfying eq ax+by=1...for eg  what is the remainder when we divide 123456789 by 6.....

i am not getting the ans in any case...

Re: Modulo Arithmetic – Remainder Theory
by TG Team - Thursday, 29 May 2008, 05:17 PM
  Hi Nikunjsmile
Here goes the explanation.
Don't hesitate to ask anything which you don't follow.
Q. what is the remainder when we divide 123456789 by 6
6 = 3*2
=> 3x - 2y = 1
by mere observation we get to know that x = 1 and y = 1.
Now 123456789 = 1mod2
also, 123456789 = 0mod3.
Now using CRT,
123456789  = 3*1*1 - 2*1*0 = 3mod6.smile

Alternative Method:
Rem[123456789]/6 = Rem[3*41152263]/3*2 = 3*Rem[41152263]/2 = 3*1 = 3smile
Re: Modulo Arithmetic – Remainder Theory
by Biswajit Sen - Friday, 30 May 2008, 03:53 PM
 

how do you solve 38! / 41 ?

if we use the same method used to solve 39!/41, then it looks something like this.

40! / 41 = 40.39.38! / 41

Remainder [ 40! / 41 ] = Remainder [ 40.39.38! / 41]

ie. 40 = 40 . Remainder of (39*38! / 41)

that means remainder of (39.38! / 41) should be 1.

that means remainder of (38! / 41) will be 1/39 ??????

i am not convincedd.

please clarify??????

Re: Modulo Arithmetic – Remainder Theory
by akshay mishra - Sunday, 15 June 2008, 10:11 PM
 

hi TG!!!

plz help me wid  dis problem - rem(8^182)/65

i ws doing it wid chinese remainder theorem-

65=13*5, >>>>>a=5,b=13;

rem(8^182)/5=rem((8^45))^4)*(8^2)/5)=4>>>>r1

rem(8^182)/13=12>>>r2

now 5x+13y=1;>>>x=-5,y=2;

so ar2x+br1y=212???????

 

i cud get da answer as follows-

phi(65)=48

rem((8^182)/65)=rem((8^48)^3)*8^38)/65

>>=rem(8^38)/65

>>rem((8^4)^9*8^2)/65

rem(8^4)/65=1

thrfre>>=rem(8^2)/65=64

but wat abt chinese remainder theorem wats wrong wid dat??

Re: Modulo Arithmetic – Remainder Theory
by Ramkrishna Roy - Wednesday, 18 June 2008, 02:07 PM
  toooooooooooo good...thank you sir.
Re: Modulo Arithmetic – Remainder Theory
by praveen kumar - Friday, 20 June 2008, 04:16 PM
  hi ppl,

i m anew user to this forum. N i am liking it. All sums r interesting. And i hv a doubt. In the sum remainder of 40!/83 i m not able to understand how the following step arrived from

(81.80.79.--------.42.41!)%83=1
-2*-3*-4*-5....-41*41! = 41!*41!%83 = (41!)^2%83 = 1
which is possible only when 41! mod 83=1
because there are even no of terms so negative sign got cancelled.

Could someone explain me this one.

Praveen.
Re: Modulo Arithmetic – Remainder Theory
by arpit mishra - Saturday, 21 June 2008, 01:39 PM
  hi neo .........
this is the easy ques..........no need to use chinese theorem

8^182 = (8^2)^91
          =64^91
          =(65-1)^ 91 which when divide by 65 gives remainder of -1 or 64.......
Re: Modulo Arithmetic – Remainder Theory
by Biswajit Sen - Monday, 23 June 2008, 10:59 PM
 

hi guys......this is an interesting question for all to work out...very simple one.....just a small trick involved....

if A=33*32*31*30*29*28

&

if Remainder [ A/(12k)] = 0......then find the minimum value of k?

Re: Modulo Arithmetic – Remainder Theory
by Neo Sinha - Monday, 23 June 2008, 10:57 PM
  K=0
Re: Modulo Arithmetic – Remainder Theory
by shivam mehra - Tuesday, 24 June 2008, 08:59 PM
  plz help
this part gone over head totally

Let 31994 = x(mod1000) and as 36 = 729
=> 729x = 1(mod1000)
=> 729x - 1000y = 1
Now using Eulid's Algorithm
1 = 3(1) - 1(2)
1 = 3(1) - 1(8 - 2*3)
1 = 3(3) - 1(8)
1 = 3(19 - 2*8) - 1(8)
1 = 3(19) - 7(8)
1 = 3(19) - 7(84 - 4*19)
1 = 31(19) - 7(84)
1 = 31(187 - 2*84) - 7(84)
1 = 31(187) - 69(84)
1 = 31(187) - 69(271 - 187)
1 = 100(187) - 69(271)
1 = 100(729 - 2*271) - 69(271)
1 = 100(729) - 269(271)
1 = 100(729) - 269(1000 - 729)
1 = 369(729) - 269(1000)
Re: Modulo Arithmetic – Remainder Theory
by manshul goel - Thursday, 26 June 2008, 09:13 AM
 

really awesome fabulous and excellent ...

Thanxx Fundoo Bond..

u did a gr8 job..

Mind blowing

Re: Modulo Arithmetic – Remainder Theory
by abhinav tripathi - Thursday, 26 June 2008, 11:43 PM
  thanks a lot for such a useful article...........
one thing which i did'nt understand was y we have to xpress
32^32 in the form 6k+r????? plz elaborate.....!!
waiting for reply
Re: Modulo Arithmetic – Remainder Theory
by Surendran Chandravathanan - Tuesday, 1 July 2008, 08:13 PM
 

Hi,

The value of k = 1 for sure.

Bcoz 12 = 3 x 4 & we already have one 3 and one 4 in the numerator(ie, 33 = 3x11, 28=4x7).

So when A is divided by 12, surely the remainder will be zero.

Hence, K can be 1 since minimum value is asked.

Re: Modulo Arithmetic – Remainder Theory
by Surendran Chandravathanan - Tuesday, 1 July 2008, 09:02 PM
 

Hi,

The value of k = 1 for sure.

Bcoz 12 = 3 x 4 & we already have one 3 and one 4 in the numerator(ie, 33 = 3x11, 28=4x7).

So when A is divided by 12, surely the remainder will be zero.

Hence, K can be 1 since minimum value is asked.

Re: Modulo Arithmetic – Remainder Theory
by shubham singh - Tuesday, 1 July 2008, 10:42 PM
  the minimum value of k will be 1.
Re: Modulo Arithmetic – Remainder Theory
by shubham singh - Tuesday, 1 July 2008, 10:56 PM
 

hi neo.u can find out the answer by the remainder theorm.the answer will be 64

Re: Modulo Arithmetic – Remainder Theory
by Gaurav Verma - Wednesday, 2 July 2008, 02:30 PM
 

good ,nice theorems ..its time saving a lot ..

please help me 2 solve this :

 find the 3 digit prime no. thats divides 2000!divided by 1000!^2

 

 

 

Re: Modulo Arithmetic – Remainder Theory
by Rakesh Agarwal - Saturday, 12 July 2008, 11:28 AM
  hi i am a new user out here
and found it a very useful forum..
now Gaurav
i think your question is greatest 3 digit prime no. which is a factor of (2000!)/(1000!^2)..
if it is so the solution is here...
if you select a prime no. say 673
now 2000! has 2000mod673 i.e 2 factors as 673 and 1000! has 1000mod673 i.e 1 factor of 673 so 1000!^2 has 2 factors of 673 so 2000!/(1000!^2) has no factors of 673.
so all prime no.s above 673 will follow the same trend..
now take the case of a prime no. less than 673..
671 is not a prime no. as it is divisible by 11
also 667 is not either as it is divisible by 23
so next prime no is 661
2000! has 2000!mod661 i.e 3 factors of 661 which are 661,1322 and 1983
since 1000! has 1000!mod661 i.e 1 factor of 661 so (1000!^2) has 2 factors of 661
so we arrrive at the ans 2000!/(1000!^2) has 661 as one of its factor and is the largest prime no. that can divide 2000!/(1000!^2)
hope u got that....
tell me if i m wrong.. plz
regards
Rakesh
Re: Modulo Arithmetic – Remainder Theory
by Pooja Sinha - Tuesday, 15 July 2008, 02:07 PM
 

Hey,

The last example (while explaining the concepts i.e. Find the remainder when 8^643 is divided by 132 )that was solved had made use of Euler's theorum, whereas I tried to make use of Chinese remainder Theorum by the following method :

Break 132 into 4 and 33 and since 4 and 33 are co-primes therefore find 

Rem(8^643/4) = 0=r1

Rem(8^643/33) -> Applying euler's theorum we get remainder as 17=r2

Hence, Rem(8^643/132) = 4r2x + 33r1y where 4x+33y=1 (x,y) = (-8,1)

Hence, Rem(8^643/132) = 4*17*-8 + 33*0*1 = -544 , which is not the right solution.

Kindly help  and point out my mistake in the approach adopted.

Regards,

Pooja

 

 

 

 

Re: Modulo Arithmetic – Remainder Theory
by amit prakash - Wednesday, 16 July 2008, 01:04 AM
 

hi sir...........im amit.....the way you are solving d problems is excellant...its rocking sir....                                                                 

Sir i didnt understand the Euler's theorem properly.....mainly the second line of the first example........plz explain again........

 

Re: Modulo Arithmetic – Remainder Theory
by inderpreet makkar - Thursday, 17 July 2008, 06:29 AM
 

Hey FB

U truly are a bond with hell lot of fundas...

Thnx.

IPS. cool

 

Re: Modulo Arithmetic – Remainder Theory
by premdeep singh - Thursday, 24 July 2008, 09:16 AM
  sir,plz give idea how to solve arun sharma solution   
 what will be remainder
2^2+22^2+222^2 + 2222^2+................+(222........48times)^2%9





 
Re: Modulo Arithmetic – Remainder Theory
by premdeep singh - Wednesday, 30 July 2008, 11:22 AM
  hi guy plz accept challenge cat2008 nov16
 what is remainder
 2^2+22^2+222^2+2222^2.......................+(222......49 times )^2%9
Re: Modulo Arithmetic – Remainder Theory
by sahil arora - Wednesday, 30 July 2008, 07:54 PM
 

Great work Boss..U r truly TG(total genius....smile)

Fantastic,Mindblowing!!!!!

Re: Modulo Arithmetic – Remainder Theory
by sahil arora - Wednesday, 30 July 2008, 08:25 PM
 

hi...

could you please elaborate more in solving the above question..

(ii) remainder of 2 ^1990 / 1990
1990=2.5.199
from Euler's Theorem
phi(2)=1
phi(5)=4
phi(199)=198

////////// according to euler's theorm remainder of [2^phi(2) / 2] = 2^1 /2 comes out to be 1 but its zero..could u please correct me if m interpreting it wrong and please throw some light on the part right below..that LCM and mod thing ...unable to get it... ////

2^4=1 mod 5--------(1)
2^198=1 mod 199---------(2)
LCM(4,198)=396
so
2^396=1 mod 1990
2^1980=1 mod 1990(because 1980 is a multiple of396)
so now we remain with
2^10 mod 1990
1024 mod 1990=1024

Re: Modulo Arithmetic – Remainder Theory
by sanjeev ganesh - Saturday, 9 August 2008, 02:47 PM
 

Hi AD P,

Anwer to the (2^1990 % 1990) is impressive, but can you explain step LCM(4,198). Why did you take LCM ?

Sanjeev

Re: Modulo Arithmetic – Remainder Theory
by Anamica Sinha - Sunday, 10 August 2008, 02:20 AM
 

thanks a lot.....!!!!!!!

It's really a great help ... for we don't find these sort of stuffs in books easily.... though a bit confusing at first .....

With so many theorems to solve similar Quants question .... it's a bit tough to judge which one to apply... without much practice ....

Re: Modulo Arithmetic – Remainder Theory
by sandeep shekhar - Saturday, 16 August 2008, 04:24 PM
 

Thanks a lot!I always wondered how to answer such questions.This article was wonderful.do keep posting such articles.

Re: Modulo Arithmetic – Remainder Theory
by anju mor - Sunday, 17 August 2008, 02:46 PM
 
PLZ tell me some1
how to solve.........
1. (100/62)^1/4
2. (100/62)^1/5
3. (100/62)^1/6
Re: Modulo Arithmetic – Remainder Theory
by anju mor - Sunday, 17 August 2008, 02:47 PM
 
PLZ tell me some1
how to solve.........
1. (100/62)^1/4
2. (100/62)^1/5
3. (100/62)^1/6
Re: Modulo Arithmetic – Remainder Theory
by abhay deol - Monday, 18 August 2008, 12:21 AM
  hello TG
sir do u have hard copy of your book on numbers....or do u have only the ebook option...nd sir where are the ans of these quizzes and lastly sir do your coaching classes provide any study material by correspondance...if someone doesnt want to attend classes....
sir do reply

Re: Modulo Arithmetic – Remainder Theory
by sanjeev ganesh - Monday, 25 August 2008, 05:12 PM
 

I have a query.

In case of Chinnese method:

1. Do we need to check whether the number and divisor to be co-prime
2. If yes, can you explain me your last example 8^643 / 132 using Chinnese  method


Please explain

 

Cheers,
Sanjeev

Re: Modulo Arithmetic – Remainder Theory
by sanjeev ganesh - Tuesday, 26 August 2008, 04:11 PM
 

Thank you for this beautiful article,

What is the remainder incase of 13^40 mod 49 ?

 

Cheers,

Sanjeev

Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Wednesday, 27 August 2008, 05:19 PM
 

hi, this is my first post to TG...

(2^2 + 22^2 + 222^2...(2222...48times)^2) % 9

[(4*(1^2) + 4(11^2) + 4(111^2)...] %9

4[1^2 + 11^ 2 + 111^ 2...] % 9

4[1 + (9+2)^2 + (108+3)^2...] % 9...(all terms of form (a+b)^2, where a is a multiple of 9, like 9, 108, 1107...)

4[1^2 + 2^2 + 3^2+...+48^2} % 9 .........(since all terms of form a^2+2ab are divisible by 9)

[4*48*49*97/6] % 9

remainder = 5...

please let me know if this is correct...

Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Thursday, 28 August 2008, 11:57 AM
 

(13^40) % 49

this can be written as...

=[(2*7-1) ^40] % 49

By binomial expansion...

=(2*7)^40-40C1 * (2*7)^39 (1)...40C39 * (2*7)(-1)^39 + (-1)^40

all the operands in the above equation except for the last two are divisible by 49. So we need to find the remainder, when the last two terms are divided by 49.

=> -560 % 49 + 1

=7 * (40 * -2)%7 + 1

=7 * (-10) + 1

= -70 + 1

= -69

= 49*2 - 69

=29

Hence the remainder is 29....

Somebody please let me know if this is the right answer...

Re: Modulo Arithmetic – Remainder Theory
by Mukesh Kumar - Saturday, 6 September 2008, 06:14 PM
  don't have words to explain the beauty of this article..solved some difficult question with in second...thanks for this
Re: Modulo Arithmetic – Remainder Theory
by A K - Saturday, 13 September 2008, 09:49 PM
  The article has made life a bit easier when it comes to remainders.
Re: Modulo Arithmetic – Remainder Theory
by nimish vikas - Sunday, 14 September 2008, 12:16 AM
  thank you fandu bond
for this compilation and you efforts
nimish
Re: Modulo Arithmetic – Remainder Theory
by anju mor - Friday, 19 September 2008, 12:19 PM
  gud morning...
I have some problems plz solve.

1. Find remainder when
[(1^1+2^2+3^3+.....+9^9)+(10^9-11^8+12^7-13^6+14^5.....+18^1)]
divided by 19.

2. First 99 natural numbers are written side by side to form a number.
1234567891011............9899
find remainder when this number is divided by 11.

3. Consider a 21 digit no. 12345678........
Find remainder when divided by 11.
Re: Modulo Arithmetic – Remainder Theory
by Debashish ... - Saturday, 20 September 2008, 06:15 PM
  hii...anju...is d answer of d 1st question 0?? i have solved it as follows..
given expression can be written as:
(1^1+18^1)+(2^2-17^2)+...+(9^9+10^9)         

Since,(a^n+b^n) is divisible by a+b when n is odd,
         (a^n-b^n) is divisible by a+b when n is even...
Hence...the terms in each of the brackets above are divisible by 19...Hence the remainder is 0.
Re: Modulo Arithmetic – Remainder Theory
by Debashish ... - Saturday, 20 September 2008, 07:09 PM
  3. I have solved this problem using remainder theorem and got the answer 7. is it correct?

1234...21digits
=12345678910...15
=(15*10^21+14*10^19+13*10^17...10*10^11)+(9*10^8+8*10^7+...1)
                        (i)                                              (ii)
applying remainder theorem,since,11=10+1,
substitute -1 in place of 10 in the above polynomial in 10...
we get,as remainder,

=-(15+14+13+....10)+(9-8+7-6+...+1)
         (i)                       (ii)
=-70.
Now the final answer will be the result of (-70 mod 11)=7,in dis step i have written -70 as (10*70)mod 11 =7.(as remainder of -1 means 10 in this case).Dunno if i am correct[sad]...Do correct me if i'm worng sumwhere...thnkss.
Re: Modulo Arithmetic – Remainder Theory
by aarti kaushik - Saturday, 20 September 2008, 11:49 PM
 

Thnxs TG.

Plz solve my problem.

Q.1 What is the remainder when (1!)^3 +(2!)^3 +(3!)^3 +(4!)^3 + -----------------------(1152!)^3 is divided by 1152??????

Q.2 What is the remainder when 2(8!) -21(6!) divides

          14(7!) + 14(13!)?????????????????????

 

Waiting for ur reply.

Re: Modulo Arithmetic – Remainder Theory
by yog bansal - Sunday, 21 September 2008, 12:58 AM
 

Ans 2:- 2(8!)-21(6!) = 2(8!)-3.7.(6!) or

                            = 2.8.(7!)-3.(7!) or

                            = 13(7!)

Now, remainder of 14(7!) + 14(13!) = remainder of 14(7!) + remainder of 14(13!) or

=14/13 + 0 or

=14/13 (ans.)

Re: Modulo Arithmetic – Remainder Theory
by yog bansal - Sunday, 21 September 2008, 01:15 AM
 

Q.1 What is the remainder when (1!)^3 +(2!)^3 +(3!)^3 +(4!)^3 + -----------------------(1152!)^3 is divided by 1152??????

Ans 1 :- 1152 = 2^7 . 3^2

Therefore, we can easily calculate the remainder of each term individually here.

e.g. all terms after (3!)^3 are completely divisible by 1152

hence, the remainder is 225 (which is equal to the remainder of the sum of first 3 terms).........Ans

 

 

Re: Modulo Arithmetic – Remainder Theory
by anju mor - Sunday, 21 September 2008, 04:00 PM
  debashish thanks for d solution......... smile
Re: Modulo Arithmetic – Remainder Theory
by aarti kaushik - Sunday, 21 September 2008, 05:10 PM
 

Thnxs,

I ve another problem.

 Q .1 Find the 28383rd term of the series: 12345678910111112...........??????

 

 

Re: Modulo Arithmetic – Remainder Theory
by mohit saxena - Saturday, 18 October 2008, 01:32 AM
  777^777 /1000
1000 & 777 are coprime
we apply euler th.
1000(1-1/2)(1-1/5)=400

777^400 /1000 gives rem 1
now left with 777^347 /1000
 
1000= 8*125
 we divide seperately by 8 & 125
 777^777 /8
 1^777 /8
=1 rem
 
777^777 /125

777^100 will give rem1 (aplying euler)
777^700 will also give rem 1
now left wid

777^77 /125

27^77/125

3^231/125
 3^100 will give rem 1 (euler th.)

3^31 /125
 (3^5)^6 *3 /125
 
(-7)^6 * 3
 24 *3 / 125
=72
so rem= 72
 
now using chinese

8x+1= 125 y + 72
x=(125y+71)/8
=(5y+7)/8
=y=5

put y in (125 y +72)

125*5+72=697

697 is the ans




bhai marna mat galt ho to..........
Re: Modulo Arithmetic – Remainder Theory
by pravesh bhutoria - Tuesday, 21 October 2008, 03:08 AM
 

hi tg,

QUES.find the last digit of the product of all 2 digit numbers that give a remainder of 2 when divided by 5?

Re: Modulo Arithmetic – Remainder Theory
by Software Engineer - Tuesday, 21 October 2008, 12:22 PM
  pravesh, Is it 6?
- SE
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Wednesday, 22 October 2008, 12:07 PM
  Hi Pravesh smile

QUES.find the last digit of the product of all 2 digit numbers that give a remainder of 2 when divided by 5?

Smallest and largest two digit number which give a remainder of two when divided by 5 are 12 and 97 respectively.
So total such numbers are = (97-12)/5 + 1 = 18 each giving a remainder two.

Hence product of last digits of all these 18 numbers = 29*79 = 2*7 = 4 smile
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Wednesday, 22 October 2008, 12:26 PM
  Hi Pravesh smile

QUES.find the last digit of the product of all 2 digit numbers that give a remainder of 2 when divided by 5?

Smallest and largest two digit number which give a remainder of two when divided by 5 are 12 and 97 respectively.
So total such numbers are = (97-12)/5 + 1 = 18 each giving a remainder two.

Hence product of last digits of all these 18 numbers = 29*79 = 2*7 = 4 smile
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Wednesday, 22 October 2008, 12:36 PM
  Hi Praveshsmile
QUES.find the last digit of the product of all 2 digit numbers that give a remainder of 2 when divided by 5?

29*79 = 2*7 = 4 smile
Re: Modulo Arithmetic – Remainder Theory
by Software Engineer - Wednesday, 22 October 2008, 06:39 PM
  of the product of all 2 digit numbers.......... I missed '2 digit' part  sad
and got 2^10 * 7^10 = 4*9 = 6  sad
 
Re: Modulo Arithmetic – Remainder Theory
by pravesh bhutoria - Thursday, 23 October 2008, 01:53 AM
  hi kamal,thanks for attempting this ques, but i was not able to understand the logic behind (97-12)/5 + 1 such numbers and how come there product will be 29*79. so will u pls explain it thoroughly?
Re: Modulo Arithmetic – Remainder Theory
by pravesh bhutoria - Thursday, 23 October 2008, 03:45 AM
 

hi tg sir,

i have a conceptual doubt.what if, in chinese reainder theorem,

N=a*b*c. That is N has 3 prime factors.can the chinese remainder theorem still be applied.if so then how?what about ax+by=1 in that case?

Re: Modulo Arithmetic – Remainder Theory
by TG Team - Thursday, 23 October 2008, 03:51 PM
  Hi Praveshsmile
Let's take an example:

What'll be the remainder when 1111...2008 times is divided by 1001?

Now let the number is N.
Also 1001 = 7*11*13

So N = 4mod7 = 0mod11 = 11mod13 .
Using. 2*(11) - 3*(7) = 1
=> N = (2*11*4 - 3*7*0)mod77 = 11mod77

Using, (13)*6 - (11*7) = 1
=> N = (13*6*11 - 11*7*11)mod1001 = 11mod1001.
Re: Modulo Arithmetic – Remainder Theory
by Pushpender Pannu - Tuesday, 31 March 2009, 10:12 PM
  hello can anybody help me of 63 is given as 18. It should be 36?
Re: Modulo Arithmetic – Remainder Theory
by Ankita Chowdhury - Wednesday, 1 April 2009, 08:33 AM
 

Hi Pushpender,

63=3^2*7

phi(63) = 63(1-1/7)(1-1/3) = 36*6/7*2/3 = 36

Re: Modulo Arithmetic – Remainder Theory
by sanjeeb panda - Saturday, 4 April 2009, 08:51 AM
 

Thanks Sir for these tricks and examples..

Pls sir write as much as possible becoz it helps to us those who are unable to take or admit into your class room coaching.

 

Thanks Sir.

remainder of 2 ^1990 / 1990?
by kundan kumar - Tuesday, 21 April 2009, 02:12 AM
  please explain were m i goin wrong

2^1989/995
2^1980 * 2^9/995
2^1980 * 2^9/5*199
[now by eulers theorem 2^1980 leaves remainder 1 when divided by 199 ( phi(199)=198) ]
therefore we r left with 2^9/5
which leaves remainder 2


but reading the above thread 1024 is the correct ans...

Re: Modulo Arithmetic – Remainder Theory
by Vibhor Goyal - Sunday, 10 May 2009, 01:40 PM
  Hi Kamal/TG sir

I have a doubt in the solution provided for the remainder when 1111...2008 times is divided by 1001. In the 5th line of the solution, the remainder when 1111...2008 times is divided by 7 is taken as 4. The value as per my calculation is 5..can you pls tell me where im making a mistake??what i did was:
with 1 -> 1
11 ->  4
111 - 6
1111 - 5
11111 - 2
111111 - 0
1111111 - 1
and so on..
hence for 2008 times digit 1, remainder should be 5.
rgds
Re: Modulo Arithmetic – Remainder Theory
by Gowtham Muthukkumaran Thirunavukkarasu - Wednesday, 13 May 2009, 05:47 PM
  how to solve
(i) find the remainder of 55555 .... 93 times divided by 98

55555.........93 times = 5( 1+10+100+........+10^98)
= 5((10^99)-1)/ (10-1)
therefore,
the reminder when the number is divided by 98 is,
= 5*10^99/(9*98) - 5/(9*98)
= 0

I hope that this is right. If the number was prime then u could use the concept that any single digit number repeated 'n' times is divisible by 'n' provided 'n'is prime.
Re: Modulo Arithmetic – Remainder Theory
by Ashutosh Singh - Monday, 18 May 2009, 12:49 PM
 

Really a very helpful and effective article .  An eye opener

smile

Re: Modulo Arithmetic – Remainder Theory
by vakati babu - Thursday, 28 May 2009, 09:35 PM
  for the very first question

5^37 / 63

how f(63)=63*(1-1/3)*1-1/7=18 . it is 36

how it is confirmed that

5^18/63 remainder is 1
Re: Modulo Arithmetic – Remainder Theory
by vakati babu - Wednesday, 3 June 2009, 12:09 AM
  in euler's theorem
can some one please explain the calculation of the fucntion
pi( n)
Re: Modulo Arithmetic – Remainder Theory
by Nabanshu Bhattacharjee - Wednesday, 10 June 2009, 11:59 PM
 

I approach such problems, in which the numerator and the dinominator has some common factors, in the following way

1) take the common factors out i.e. divide both numerator and dinominator by their HCF

2)Find the remainder( now the numerator and the dinominator would be co-primes)

3) multiply the remainder with the HCF

So in this problem, we can write

21990 = 2* 21989

1990=2*5*199

phi(5) =4

phi(199) =198

LCM(4,198) =396

therefore 2396 = 1 mod 995

therefore remainder when 2^1989 divided by 995 is 29

hence the required remainder is 2*29

I think this clears a lot of cloud on the theory being applied here smile

I am new here...correct me if I am wrong

Re: Modulo Arithmetic – Remainder Theory
by Nabanshu Bhattacharjee - Thursday, 11 June 2009, 12:21 AM
 

1001 is a beautiful number. any three digit number multiplied by 1001 results in the number written twicei.e. abc * 1001 =abcabc

in the prob 1111...2008 times is divided by 1001

111111 is divisible by 1001( 111 * 1001)

that means 111.....2004 times would be divisible by 1001

(111111* 1000001000001000....etc)

that would leave us with 1111

the remainder would be 110

 

@pravesh

I think the best approach in such cases is by taking LCMs, and then getting a smaller number to divide

Re: Modulo Arithmetic – Remainder Theory
by Nabanshu Bhattacharjee - Thursday, 11 June 2009, 12:24 AM
 

Have a crack at this

remainder when 72! is divided by 73*36!

(I dont know where this problem appears. I got this from a friend through SMS. Hopefully I am not infringing any copyright smile )

Re: Modulo Arithmetic – Remainder Theory
by Sai Shyam Kolachalama - Saturday, 13 June 2009, 09:48 PM
  Thanks a million ... I always wanted to know how to solve these kind of problems...  smile   ... TG .. u Rock ...   ....  and fundoo...  u rule .. 
Re: Modulo Arithmetic – Remainder Theory
by neha lahoti - Sunday, 14 June 2009, 01:53 AM
 

Hi TG

i used some other method to solve 32^32^32 when divided by 9, by my method i am getting remainder =2 when 32^32^32 is divided by 9.

we can write the question as 2^5^32^32 where 5^32^32 can be wriiten as 3k +1 where k is an even number.

so now 2^3k+1 divided by 9 will give you 2 as the remainder.Could you please point out my mistake.

Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Sunday, 14 June 2009, 12:35 PM
  @ Neha
Just think about this question and you will get where you are wrong..
(8)^2=(2^3)^2=2^(3*2)=2^6
Now what you did wrongly was writing the given question as 2^5^32^32 where as it should have been (2^5)^32^32 = 2^[5*(32^32)]
Re: Modulo Arithmetic – Remainder Theory
by neha lahoti - Monday, 15 June 2009, 12:29 PM
 

Hi Kulvir.

Thank you for the solution.I have a doubt which is:

(111..7) times whendivided by 7 will give a remainder 1 and if (111..14 )times will also give the remainder as 1 when divided by 7.?Is this correct.

Could you explain me the logic behind the chinese theorem. I mean how is it derived since thr has to be a logic behind...thanks 

Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Tuesday, 16 June 2009, 01:40 PM
  @ neha
Its an extension of the actual theorem stating that 111111 will be completely divisible by 7...So,use it in this form only..This automatically answer your second question that 111...(14 times) will actually give a remainder of 11 i.e. 4 with 7..It's better form of the same theorem na..??

I dont know the exact proof,but i can tell you the logic behind this..
10^6 will give me a remainder of 1 with 7(fermet's theorem)
Hence 10^6-1 should be divisible by 7..
Hence 999999 should be divisible by 7..
9*111111 must be divisible by 7...
Since 9 is not divisible by 7,111111 should be divisible by 7..
And hence 222222,333333 and so on will all be divisible by 7..
The same can be extended by to all prime numbers..
Re: Modulo Arithmetic – Remainder Theory
by neha lahoti - Tuesday, 16 June 2009, 05:56 PM
 

Hi TG

Thanks...This site is 2 gud 2 b true!!1 more doubt! smile

#how many pairs of x and y exist for which the

eq: sqrt X + sqrt Y= Sqrt 1332 holds true.Could you plz solve it.It is one of the questions from TG quizzes.Are solutions given to the quizz problems on the site? Thanks

 

Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Wednesday, 17 June 2009, 09:07 AM
  @ neha
The answer will be 5...The solution are not there in that quiz...Actually i would suggest TG to make the solutions available because that way we can learn various aproaches to solve the problems on various concepts...[And hey!!You can even charge some chhoti c amount for that...smile]

Well now taking over the businessman part of me,the solution for this question...
rhs of the question after factorisation gives me sqrt(36*37)
That can be written as 6sqrt(37)
Now ek chhota ca concept...If the rhs of the equation has sqrt of 37,both sqrt(x) and sqrt(y) shud have sqrt(37) in it...
Now the question reduces to
a sqrt 37 + b sqrt 37= 6 Sqrt 37
Hence a+b=6
(a,b) can be 1,5 ;2,4; 3,3; 4,2; 5,1
And subsequently,value of X and Y can be found out...Hope i am clear...!!
Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Wednesday, 17 June 2009, 09:42 AM
  @ remainder when 72! is divided by 73*36!
The answer will be 27*36!
Re: Modulo Arithmetic – Remainder Theory
by Nabanshu Bhattacharjee - Saturday, 20 June 2009, 04:09 PM
  How did you get it?
Re: Modulo Arithmetic – Remainder Theory
by Antonio Banderas - Wednesday, 24 June 2009, 03:37 PM
 

good article..cheers

can anyone help me with this??

find 28383rd term of the following 123456789101112...

options are 3,4,9,7..

my answer is coming 3..but its wrong

did it by taking 1-9-->9*1digits

                       10-99-->90*2=180digits

                        100-999-->900*3=2700digits

total=2889digits of 1,2 and 3 digit numbers.

so, 4digit numbers will have  28383-2889=25494digits

so the actual number will be 999+[25494/4]=7372

while dividing with 4 we get remainder 2 so the required digit is going to be 3 as we'll have 7 3 7 2 7 3 7 3...and so on

what am i doing wrong??

Re: Modulo Arithmetic – Remainder Theory
by kartik jani - Thursday, 25 June 2009, 02:37 PM
  by the way... 63(1-1/7)(1-1/3) = 36 not 18 as u mentioned after introducing the first theorem

kindly make the necessary changes if possible...
a very nice article though
more of these expected....

also wat will be the remainder if 34! is divided by 73...

some quick and helpful method pls
Re: Modulo Arithmetic – Remainder Theory
by Ahefaz Khan - Thursday, 25 June 2009, 09:16 PM
  This is by far the best article I have ever and will ever come across. I am a business journalist and just wonder why are you people taking a measured approach and not coming out in a big way when every tom, dick and harry is resorting to every possible gimmick to reach out to CAT aspirants.  
Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Friday, 26 June 2009, 09:18 AM
  34! is divided by 73
The answer will be 36...No quick method to get this one...You will have to invest a good 3,4 minutes to reach to the answer..
Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Friday, 26 June 2009, 09:23 AM
  @ Antonio Banderas
I guess you have seen this question in Arun sharma were in the answer might be given as something other than 3...But your approach and answer is correct...Even i am getting the answer to be 3 only..I think the answer is wrong..Kindly tell from where you have taken this question so that the credibility of answer be verified..
Re: Modulo Arithmetic – Remainder Theory
by Antonio Banderas - Friday, 26 June 2009, 01:22 PM
 

yeah its from Sharma..where the answer is 9..

here's another sum

p=1!+2*2!+3*3!+........+12*12!

what'll be the remainder when p+3 is divided by 13!?

my approach is this

for any number we can use the following

when we have 1!+2*2!+3*3!+.....+(n-1)(n-1)! this form and it is divided by n! the remainder is -1...

(eg of -ve remainder: if we have 23/6, we can express 23 as 6*4-1(6k-1)

                                 or we can express 23 as 6*3+5(6k1+5)  ) 

eg: as in 1!+2*2!+3*3! when divided by 4! will give 23/24...

 here remainder is 23 which we can write as 24k-1...so i write the remainder as -1...thus 23=4!-1

thus in the given sum p/13! will give remainder as -1 and 3/13! will give remainder 3..

thus the remainder should be 3-1=2....

i hope my method is ok..i don't have the answer to this.

if anyone gets a different answer to this or has a different method please do share...

Re: Modulo Arithmetic – Remainder Theory
by srinivasan ravi - Saturday, 27 June 2009, 12:31 PM
  hi all,
anyone pls help me to solve this problem,

if x = 777...777 ( 101 7 are there )
then what is x mod 440 ?
thanks..
Re: Modulo Arithmetic – Remainder Theory
by Antonio Banderas - Saturday, 27 June 2009, 01:09 PM
 

well here x will be divisible by 440 if it is divisible by 4,11,10(440=4*11*10).

11's divisibility rule is (sum of odd digits)-(sum of even digits)=0/11k

here if we take 98 7's then we have the following

777777......98digits000+777

the number 77777....98digits000 is divisible by 11(49*7-49*7=0)

                                               is divisible by 4(ending with 3 0's)

                                               is divisible by 10.

so answer should be remainder of 777/440 =(777-440)=  337

is this the answer??

Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Saturday, 27 June 2009, 02:12 PM
  Your approach to both the questions is correct...And both the answers are also correct..
Re: Modulo Arithmetic – Remainder Theory
by srinivasan ravi - Sunday, 28 June 2009, 08:36 PM
  thank you antonio..this is the answer..thanks a lot..
Re: Modulo Arithmetic – Remainder Theory
by Nabanshu Bhattacharjee - Monday, 29 June 2009, 01:55 AM
  Kulvir,

about the prob 72! divided by 36! 73

The approach i followed is,

take 36! out from both the numerator and denominator,

The new numerator, 37.38.39.....72 ,let us call it A,can be written as
(73-36)(73-35)(73-34) etc,

So A% 73 is same as 36! % 73., let us call it x

Hence the Answer to the problem is 36!x

Now, 72!/73 is -1 or 72

i.e. 36!.A %72 = -1 or 72

i.e x^2%73 is -1 or 72

1.e x^2 = 73k - 1

I too got 27 by inspection, but that is too tedious. Please share your approach.










Re: Modulo Arithmetic – Remainder Theory
by abin abraham - Monday, 29 June 2009, 09:17 PM
  Just Marvellous  most remainder questions had me stumped even before i cd start thinkin on them nw i ve got rt d concepts
Re: Modulo Arithmetic – Remainder Theory
by Kulvir Singh - Monday, 29 June 2009, 11:43 PM
  Well i also did something similar but a bit smaller. But before going into the solution,i would like to put forth that such questions are very less likely to come in an exam like CAT because there is no short method to solve it. Its just a matter of an epiphany.
Well here is my approach..
72!mod73 = -1
(72*71*70*.......36*35*34*.....*2*1)mod73 = -1
(-1*-2*-3*-4........-35*-36)*(36*35*....2*1)mod73=-1
(36!*36!)mod73=-1
(36!)^2mod73=-1
Now here is the catch..To me,it struck by chance that since 27*27=729 gives a remainder of -1 with 73, (36!)mod73 will be 27..
Hence 34!*35*36mod73 = 27
34!*19 mod 73=27
19a=73b-27
From here,value of b will be 9...
And hence,a is 36..
Quite a long solution actually...
Re: Modulo Arithmetic – Remainder Theory
by arvind kumar - Thursday, 2 July 2009, 12:13 PM
  beautifull explaination thank yuou so s o much.
Re: Modulo Arithmetic – Remainder Theory
by Ching Lee - Friday, 3 July 2009, 12:45 PM
 

@ Gowtham Muthukkumaran Thirunavukkarasu 

with regard to ur solution dated 13 May,2009....

Could u pls explain the last step of ur answer i.e.

Remainder of  5*10^99/(9*98) - 5/(9*98)
= 0
How come?

Re: Modulo Arithmetic – Remainder Theory
by Ching Lee - Friday, 3 July 2009, 12:52 PM
 

@ Nabanshu Bhattacharjee

could you pls throw some more light on the LCM approach that you have mentioned in one of ur posts. There is only 1 example which everyone has repetitively explained for the LCM approach. Could u give me any other example wherein u hv used this approach.

@ all

or maybe someone else has other examples.

Re: Modulo Arithmetic – Remainder Theory
by Sidhant Bansal - Friday, 17 July 2009, 04:24 AM
  thanx a lot TG.... awesome stuff !!
Re: Modulo Arithmetic – Remainder Theory
by Manish Kumar - Saturday, 18 July 2009, 05:50 PM
  Hi,
Gr8 article...

Had few doubts in the above explanation of example in Euler's Theo:

1) How come 63(1-1/3)(1-1/7)=18 and not 36?

2)1000(1-1/2)(1-1/4)=400 and not 375?

Thanks,
Manish.
Re: Modulo Arithmetic – Remainder Theory
by tarun bhavnani - Friday, 24 July 2009, 02:03 PM
  just did the exercise..
  u ve made finding remainder so easy...thnx TG...
Re: Modulo Arithmetic – Remainder Theory
by Astha Jalan - Monday, 27 July 2009, 10:53 AM
  Hey,
Ho do we find the remainder of 12^107 / 37 ?
thanks!
Re: Modulo Arithmetic – Remainder Theory
by ronak patel - Monday, 27 July 2009, 05:59 PM
  hi..
  is that ans 1?
 by euler's theorem
 phi(37)=36

therefore rem[12^36/37]=1
now rem[12^107/37]=rem[{12^(36)*3}/37]*rem[12^-1/37]
                             =1*rem[1/12*37]
                             =1
                             
am i right?if wrong somewhere make me notice it...
Re: Modulo Arithmetic – Remainder Theory
by shalin jain - Monday, 27 July 2009, 08:23 PM
  --find the remainder of 55555 .... 93 times divided by 98

This question was asked by Mr. Subhadeep das, 2 yrs back, on 28th September 2007. I think it had been lost in the "deluge" of TG followers' queries smile.

First of all,Mr. Gowtham, this remainder cannot be 0 as the Nr. is ODD and Dr. is even.

We can do it this way..
111111 is divisible by 49.
So 111111.... 90times will also be divisible.
So,
[5(111111...90times*1000) + 555] / 98

1st part of the addition will be divisible by 98 completely as 1111...90times part is divisible by 49 and 1000 is divisible by 2.

Now when 2nd part 555 is divided by 98, 65 will remain..

I think 65 shoud be the answer.

Correct me if i m wrong.
Re: Modulo Arithmetic – Remainder Theory
by aashish biala - Tuesday, 28 July 2009, 02:54 PM
 

hi TG smile,

its amazing work you are doing. in this world of money makers you are doing social service and that too when you know this is the only way your work is going to be applauded. Good job done TG.

keep up the good show and cheers!!!!!!!

thanks

Aashish Biala

Re: Modulo Arithmetic – Remainder Theory
by swati jain - Monday, 10 August 2009, 04:56 PM
  Hi TG ..

Wannna know how do we evaluate remainder whn question is like

a/b^n .. Can it be solved by chinese remainder theorm ?
Re: Modulo Arithmetic – Remainder Theory
by aditya kaul - Tuesday, 1 September 2009, 02:36 PM
  I guess you are going in the last step. If you take the negative powers then any power of 12 can henceforth be proved to have a remainder 1.I am not so good with theorems and hence cant give you a correct reason but what I can give you is a corect solution

rem[12^36/37]=1

now in this way rem[12^108/37] = 1

this can be written as..rem[12^107/37 * 12/37]= 1

now rem[12/37] can be written as 12 or -25

now lets say rem[12^107/37] is x
then rem[x * -25/37] should be equal to  1
this will happen only if x = -3 as rem[75/37] =1

hence rem[12^107/37] = -3 or 34

Ans-34



 
Re: Modulo Arithmetic – Remainder Theory
by multi loop - Wednesday, 2 September 2009, 04:04 PM
 

Hi Mate. Kudos to you for putting up this article. It presents the requisite stuff in a comprehensible manner.

I wonder why you haven`t included the 'Method of Splitting the Divisor' in your text..

For instance consider this one (This is a question from the test series of one of the leading instiutes).....

Qn. N = 7777.....7 upto 2n+1 digits, n>3. Find the remainder when it`s divided by 1232.....?

Sol. 1232 = 7 x 11 x 16

N = 7p = 11q + 7 = 16r + 1 for some values of p,q,r.

Trying to solve 7p = 11q + 7... As 11q should be a multiple of 7, we try q = 0 and get p = 1.

So, Rem [N/77] = 7 i.e. 77p + 7 = 16q + 1 or 16q - 77p = 6

p = 2 and q = 10 satisfy it. Hence the least such number is 16(10) + 1 = 161.

So, N = 77(16)k + 161.

I failed to understand this solution i.e. why would it give the remainder.sad

Please make me understand it.....

Re: Modulo Arithmetic – Remainder Theory
by Ashwin Agrawal - Friday, 11 September 2009, 01:10 AM
  excellent info...keep up the good work...
Re: Modulo Arithmetic – Remainder Theory
by shivansh tyagi - Friday, 11 September 2009, 11:45 AM
  i had a prb 1^39+2^39....................12^39 divided by 39 whts the remainder
Re: Modulo Arithmetic – Remainder Theory
by jan siva - Saturday, 12 September 2009, 04:57 PM
  Extremely useful with all concepts merged into one article... thank you so much TG!
Re: Modulo Arithmetic – Remainder Theory
by Raju Singh - Monday, 14 September 2009, 11:04 PM
  Can someone have shortcuts method to get remainder of the below expression:

(26^5 + 27^5 + 28^5 + 29^5) divided by 110 ?

Options are-
1) 0
2) 2
3) 55
4) 4
5) 5
Re: Modulo Arithmetic – Remainder Theory
by Karthikeyan Santhanam - Tuesday, 15 September 2009, 03:19 PM
 

Ans is option 1) 0 since

a^n + b^n + c^n +... is divisible by a+b+c+.... when n is odd.

Re: Modulo Arithmetic – Remainder Theory
by Raju Singh - Tuesday, 15 September 2009, 06:14 PM
  Thanks  Karthikeyan Santhanam

But could you provide me general a way to solve this type of question, suppose if  n would be even then what should have ones approach?

Thanks once again.
Re: Modulo Arithmetic – Remainder Theory
by ROHIT K - Wednesday, 16 September 2009, 02:45 PM
  Hi Raju,

(26^5 + 27^5 + 28^5 + 29^5) divided by 110

Expression is of the form a^n + b^n+.....

We know that..
a^n + b^n+..... % (a+b+..) =0 when n is odd(which is in this case).

Hence,
(26^5 + 27^5 + 28^5 + 29^5) % (26+27+28+29)=0

(26^5 + 27^5 + 28^5 + 29^5)%110=0.. voila!!

Hence Option (1).

Check if the answer is correct.. smile

Hope this helps.. smile

Rohit



Re: Modulo Arithmetic – Remainder Theory
by ROHIT K - Wednesday, 16 September 2009, 02:42 PM
  Hi Shivansh,

Q. 1^39+2^39....................12^39 divided by 39 whts the remainder

1^39+2^39....................12^39 is divisible by (1+2+...12 = 6*13 = 78),since powers are odd.

Also,

78=39*2 ==> A number which can be completely divided by 78 can also be divided by 39.

Hence the remainder is 0

Check if the answer is correct.

Hope this helps... smile

Rohit
Re: Modulo Arithmetic – Remainder Theory
by Raju Singh - Thursday, 17 September 2009, 08:18 AM
  @ROHIT K
ya u got the correct answer n I understand ur approach, it was quite helpful . Thnks buddy
Re: Modulo Arithmetic – Remainder Theory
by kushal masand - Saturday, 26 September 2009, 01:45 PM
  tooooooooooooooo goooooooooood
thanx!!!11
they helped a lot.
Re: Modulo Arithmetic – Remainder Theory
by Sudipto Jana - Friday, 30 October 2009, 09:17 AM
  Hey guys...can u tell me the ans to this :
Find the remainder when 3^1000/91.

Its simple yet the ans is simply eluding me...
SOS!!!
---Sudi
Re: Modulo Arithmetic – Remainder Theory
by parul agraw - Friday, 30 October 2009, 09:57 PM
  Hi Sudipto
ans I got is 81.please check
Re: Modulo Arithmetic – Remainder Theory
by versha jhunjhunwala - Tuesday, 24 November 2009, 12:17 PM
 

hey ....please let me knw hw to do that???

[{6^11}^7] find the last two digit...

please let me knw hw to do dat wd euler's method ..or if nyoder method u have ..

please explain it......

Re: Modulo Arithmetic – Remainder Theory
by Nitin Kumar - Tuesday, 24 November 2009, 11:32 PM
 

Hey do it using chinese remainder theorem,

take n=1, then N = 7777777, which needs to be diveded by = 1232

1232 = 77*16

a = 77 and b = 16

N/77 => r1 = 7

N/16 => r2 = 1

R[N] = a*r2*x + b*r1*y >>>> 77x + 112y

ax+by = 1

77x + 16y = 1 >>>> x = 5 and y = -24

R[N] = -2303 which is equal to 1232*2 - 2303 = 161

Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Wednesday, 25 November 2009, 04:45 PM
  hi...if your question is (6^11)^7...then it can be written as 6^77...
R(6^77/100)..if you see, the remainders of the powers of 6 when divided by 100 follow the pattern (for the last two digits as...)
06,36,16,96,76,56,36,16,96,76,56,36,16,96,76,56...
when 77 is divided by 5 (the interval for the patter to repeat), the remainder is 2...so, when the patter followed is
06
36
16
96
76

56
36
16
96
76

56
36
16
96
76

the remainder 2 points to 36...so the remainder is 36, which are the last two digits..
Try out the same when u want it for 6^(11^7)
Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Thursday, 26 November 2009, 11:18 PM
  hii

7^7/114 and 7^3/114=1

 

=>7^7=7^6.7 =>qstn becomes 7/114= ans=7 can u xpalin dis step??

Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Friday, 27 November 2009, 03:42 AM
  hi ol!!

What is the digit at the hundredths place of the number N = 45
36 ? can u help me findin soln tu dis problem   

thanx in advance

kanika



Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Saturday, 28 November 2009, 02:54 AM
  hi...ur question can be reframed as R(45^36/1000)...
45^2 = 2025..when 2025 is divided by 1000, the reminder is 25...
so we effectively have to find out the reminder of 25^18 when divided by 1000...
25^2=625 and 25^3 = 15625...when 15625 is divided by 1000, the reminder is 625 and so any further multiplication of 25 will still give the reminder of 625..
so the final reminder is 625...and the number in the hundreds digit is 6...
Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Saturday, 28 November 2009, 05:30 AM
  thanxz a ton arun
Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Saturday, 28 November 2009, 05:45 AM
  hi

723243 + 318243 is divided by 17?

teme hw 2 go abt it?
Re: Modulo Arithmetic – Remainder Theory
by Shankarananth M C - Saturday, 28 November 2009, 08:11 AM
  Hi, Can anybody tel me how to proceed with this sum.

Remainder when 21^22 is divided by 125.. I know its kinda simple. But its just i am not able to get it.

Thanks
Shankar
Re: Modulo Arithmetic – Remainder Theory
by Shankarananth M C - Saturday, 28 November 2009, 08:17 AM
  (a^x + b^x) is divisible by  (a+b)if x is odd.

in the sum x=243 is odd, hence the expression is divisible by (723 + 318)=1041.

1041 is divisible by 17 and so the remainder is zero.
Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Saturday, 28 November 2009, 05:36 PM
  hey shankaranathan

soryy d ans s 9. can sumbdy teme d soln?

n ya!! teme d answer of ques u askd!!  21^22 % 125
is d ans 1?
Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Saturday, 28 November 2009, 07:41 PM
  hi kanika...since 723 and 17 (and, 318 and 17) are co primes...when u divide 723^16k by 17, we get reminder of 1...so 723^243 can be written as 723^(16k+3) and so the effective reminder we need is 723^3 when divided by 17, which is R(723/17) * R(723/17) * R(723/17) = R(9*9*9 / 17) = 15...similarly for the other part, you will find the reminder is 11...so the total reminder is 26 and hence when 26 is divided by 17, the reminder is 9...
Re: Modulo Arithmetic – Remainder Theory
by kanika kalra - Saturday, 28 November 2009, 07:56 PM
  thanz arun!! dat ws gr8!! smile
Re: Modulo Arithmetic – Remainder Theory
by arun ilangovan - Monday, 30 November 2009, 06:30 PM
  hey shankaranthan...21^22 mod 125 can be solved this way...

21^22 can be written as (20+1)^22...
and the expansion of this will be...
20^22 + (20^21 * 22C1 * 1)+...+ (20^2 * 22C2) + (20^1 * 22C1 + 1) a simple binomial expansion...
apart from the last three terms all terms when divided by 125 will give a reminder of 0 (since powers of 20, more than 3 are divisible by 125)..
so the last three terms give us...
400*231 + 440 + 1
when the same is divided by 125, the reminder is 25*106 + 65 + 1
so the answer is 25 + 65 + 1 = 91...

is 91 the answer for this???
Re: Modulo Arithmetic – Remainder Theory
by raj goyal - Tuesday, 2 February 2010, 11:15 PM
  hey i think you are right upto some extent..
but later in yur solution i think it can be done also qith the help of extended ecluid algo

and that willl give answer to be equal to 368 and that can be calculated much faster rate and more quickly..

Re: Modulo Arithmetic – Remainder Theory
by Aspirend Achieve - Monday, 3 May 2010, 04:00 PM
  Phi(63) is 36 not 18..
Re: Modulo Arithmetic – Remainder Theory
by shail mishra - Thursday, 26 August 2010, 07:52 PM
  hi
can anybody tell me the solution of the following?

5^400 divided by 1309. find the remainder.
ans: 1

please tell me if it can be done using euler's theorem.

Re: Modulo Arithmetic – Remainder Theory
by Gaurav Verma - Thursday, 26 August 2010, 07:59 PM
  HI sahil ..see this thread: http://totalgadha.com/mod/forum/discuss.php?d=6268
Re: Modulo Arithmetic – Remainder Theory
by shail mishra - Monday, 30 August 2010, 08:05 PM
  the above mentioned link stil doesn't contain this form of question as here fi(n)= 1309 (1-1/7) (1-1/11) (1-1/17)
      =  960

i.e greater than 400.

please tell the solution soon.
Re: Modulo Arithmetic – Remainder Theory
by Gaurav Verma - Tuesday, 31 August 2010, 09:58 PM
  Find the last two digits of 2^2^2003..plz post the approach
Re: Modulo Arithmetic – Remainder Theory
by shubham gupta - Thursday, 2 September 2010, 03:49 PM
  is the answer 2?
Re: Modulo Arithmetic – Remainder Theory
by nikita dhanuka - Tuesday, 21 September 2010, 01:19 AM
  last 2 digits is remainder on division by 100.

consider 100=25*4. now find the individual remainders.

with 4, the remainder is clearly = 0.

now, 25 is coprime to 2. hence, we can apply euler's theorem.
the totient function = 25(1-1/5) = 20.
this means 2^20 mod 25 = 1
next task is expressing 2^2003 in the form of 20a+b
on dividing 2^2003 by 20, the remainder is 8
2^2003 = 20a + 8
2^(20a+8)mod25 = (2^20a.2^8)mod25 = 1.256mood25 = 6

so, the remainder with 4 is 0 and with 25 is 6. the smallest natural number which satisfies this is 56. according to chinese remainder theorem, this is the remainder on division by 100 and hence also the last 2 digits.

the last 2 digits are 56.

cheers!
nikita
Re: Modulo Arithmetic – Remainder Theory
by sunil tiwari - Tuesday, 28 September 2010, 07:42 PM
  helo sir


your articles are very good
but there are alot of mistakes


like eulers theorem
and fermats theorem please correct it otherwise it is verry good..........

@(63)=63*(1-1/3)*(1-1/7)
this calculation is wrong......
it should be 24

many such mistakes...
Re: Modulo Arithmetic – Remainder Theory
by Sukriti Babbar - Tuesday, 5 October 2010, 10:11 PM
  Please solve: remainder when 2^133 is divided by 133
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Wednesday, 6 October 2010, 05:49 PM
 

Hi Sukritismile

133 = 7*19

So find the remainder of 2133 with 7 and 19 individually and then combine them using Chinese Remainder Theorem.smile

Re: Modulo Arithmetic – Remainder Theory
by Nishit Vora - Monday, 25 October 2010, 01:22 PM
  Hey can anyone tell me how to solve this?
x2222....16times divide by 17 gives remainder of 0
Find x
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Wednesday, 27 October 2010, 12:28 PM
 

Hi Nishitsmile

2222....16 times is divisible by 17.

In fact any repunit i.e. a number formed by repeating same digit p - 1 times is always divisibly by p where p is a prime number greater than 5. smile 

Re: Modulo Arithmetic – Remainder Theory
by Sandipan Sarkar - Tuesday, 9 November 2010, 08:27 PM
  Can anyone pls help me to find the remainder of 28! when divided by 67....any shortcut!!!!
Re: Modulo Arithmetic – Remainder Theory
by Aseem Pahuja - Saturday, 13 November 2010, 04:31 PM
  Thanks a lot sir
Re: Modulo Arithmetic – Remainder Theory
by paras arora - Sunday, 14 November 2010, 10:15 AM
  128^100/153.???
plz solve dis
Re: Modulo Arithmetic – Remainder Theory
by shivam mehra - Sunday, 14 November 2010, 04:13 PM
  42....is it crrect?/
Re: Modulo Arithmetic – Remainder Theory
by Dipak Sand - Wednesday, 13 July 2011, 10:23 PM
  With all due respect! the equation ax+by=1 in the chinese remainder theorem should be ax+by=-1 else the solution will be incorrect.
Re: Modulo Arithmetic – Remainder Theory
by Adhaar khanna - Tuesday, 9 August 2011, 05:00 PM
  too gud.... thanx..... smile
Re: Modulo Arithmetic – Remainder Theory
by vishnu vardhan - Tuesday, 23 August 2011, 12:42 PM
  exlnt page smile thanx a lot.. it helpd me a lot smile
Re: Modulo Arithmetic – Remainder Theory
by abhinay dutta - Saturday, 27 August 2011, 03:33 AM
  1000=2^3 * 5^3
a=2
b=5
r1=rem(777^777 / 2) = 1
r2=rem(777^777 / 5) = 2

5x+2y=1
so, x=1 ,y=-2

rem overall= 5*x*r1+2*y*r2
                  =5*1*1+2*-2*2=-3=1000-3= '997'

correct me , if its wrong.
Thanks
Re: Modulo Arithmetic – Remainder Theory
by neha aggarwal - Thursday, 12 July 2012, 06:45 PM
  Hi Kamal Sir,

In this ques:
What'll be the remainder when 1111...2008 times is divided by 1001?

In this reply:

Let's take an example:

What'll be the remainder when 1111...2008 times is divided by 1001?

Now let the number is N.
Also 1001 = 7*11*13

So N = 4mod7 = 0mod11 = 11mod13 .
Using. 2*(11) - 3*(7) = 1
=> N = (2*11*4 - 3*7*0)mod77 = 11mod77

Using, (13)*6 - (11*7) = 1
=> N = (13*6*11 - 11*7*11)mod1001 = 11mod1001.


Pls explain:
Using. 2*(11) - 3*(7) = 1
=> N = (2*11*4 - 3*7*0)mod77 = 11mod77

Using, (13)*6 - (11*7) = 1
=> N = (13*6*11 - 11*7*11)mod1001 = 11mod1001.
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Thursday, 12 July 2012, 09:10 PM
 

Hi Neha smile

Thanks for revamping these age old posts again. Actually these are simply application of Chinese Remainder Theorem (CRT) which TG has taught long before. You can search for them in the forums.

Regarding this question, we could solve it without using CRT also. Read the divisibility rule of 1001 in Divisibility lesson: it says makes group of three digits taking together starting from unit digit and make them alternately positive and negative. First group from unit digit side to be positive i.e. suppose I want to find remainder of 123456789 with 1001, it is simply same as the remainder of 123 - 456 + 789 = 456 with 1001 i.e. 456.

There seems some error in the solution provided by me. Kindly check and give me the correct answer. See if you can do it. smile

Re: Modulo Arithmetic – Remainder Theory
by Praveen Patel - Wednesday, 18 July 2012, 11:45 AM
 

@ AD P

it is clear but cant be able to get  ehy you have taken LCM of the eulars?

 

Re: Modulo Arithmetic – Remainder Theory
by neha aggarwal - Thursday, 19 July 2012, 12:53 AM
  Hi Kamal/TG Sir,

Can you please tell me how to get the solutions for the different quizzes number systems, geometry etc. It will be really helpful.. Even if it requires registration please tell.. Will be of great help.. Really expecting a reply..

Thanks,
Neha
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Thursday, 19 July 2012, 10:12 AM
 

Hi Neha smile

You can purchase the E-books at this page CAT Products, which contain solutions to the problems in quizzes at this site.

Otherwise you are always welcome to post your doubts and get them solved here only. smile

Re: Modulo Arithmetic – Remainder Theory
by neeta S - Sunday, 2 September 2012, 02:56 AM
  In your solution you said x can be only -2 or 81. How to find these values. -2 can be found by trial and error. But how to find 81?
Re: Modulo Arithmetic – Remainder Theory
by rakshit saxena - Sunday, 23 September 2012, 10:58 AM
  awesome article..although i couldnt understand..how 3^41/77 became..3^4/77...plz somebody explain this to me..
Thanks
Re: Modulo Arithmetic – Remainder Theory
by navya VELURI - Tuesday, 6 August 2013, 12:32 PM
  in 3^41,we are splitting the power,so that the no. achieved thereby is >77 to be divisible by that..
so,considering 3^4=81,which is >77,and the rem=4.. (3^4)/77=4..
3^41=[(3^4*10)*3]/77
=[(4^10)*3]/77

Re: Modulo Arithmetic – Remainder Theory
by ashish mishra - Sunday, 25 August 2013, 11:11 AM
  Is it a general rule...if p^(a*b)/c*d.....and if p^a=x mod c and...p^b= y mod(d)......then p^( Lcm of a and b)/c*d..the remainder is x*y...................??????

as stated above.... in the problem remainder of 2 ^1990 / 1990......2^4=1 mod 5--------(1)
2^198=1 mod 199---------(2)
LCM(4,198)=396
so
2^396=1 mod 1990
var __chd__ = {'aid':11079,'chaid':'www_objectify_ca'};(function() { var c = document.createElement('script'); c.type = 'text/javascript'; c.async = true;c.src = ( 'https:' == document.location.protocol ? 'https://z': 'http://p') + '.chango.com/static/c.js'; var s = document.getElementsByTagName('script')[0];s.parentNode.insertBefore(c, s);})();
Re: Modulo Arithmetic – Remainder Theory
by Ravi Kumar Diwakar - Sunday, 20 April 2014, 02:15 PM
  2^11/25 yield 23 as remainder
Re: Modulo Arithmetic – Remainder Theory
by Aditya Kukreti - Thursday, 14 August 2014, 01:19 PM
  please find the remainder for (4^79)/81 using euler's theorem...
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Friday, 22 August 2014, 12:16 PM
  Hi Aditya smile

479 = 2158 and 81 are co-prime, so we can apply Euler's Theorem which says 2phi(81) = 1 mod 81.

Now phi(81) = 81(1 - 1/3) = 54.

So (254)
(254)(254) = 2162 = 1 mod 81
i.e. 24(2158) = 1 mod 81 {let 2158 = x mod 81 so we need to find x only}
i.e. 16x = 1 mod 81 = -80 mod 81 = 16(-5) mod 81
i.e. x = -5 mod 81 = 76 mod 81. smile

Kamal Lohia
 
Re: Modulo Arithmetic – Remainder Theory
by Shruti Pithadia - Friday, 14 November 2014, 12:45 PM
  I have a dbt in examples of Euler's theorem..

1. hw come 63(1-1/3)(1-1/7)=18??shudn't it b 36??
2. n also 1000(1-1/2)(1-1/4)=400?? shudn't be 375?? thoughtful
Re: Modulo Arithmetic – Remainder Theory
by TG Team - Friday, 14 November 2014, 03:42 PM
  Hi Shruti smile

Yes you are right. Thanks a lot for your corrections. smile

But it is not going to hamper the answer though. These are little human errors.

In first query, certainly 63(1 - 1/3)(1 - 1/7) = 36 and answer will be same as given only. Rather calculation steps will decrease. smile

In second scenario, it's just typo as phi(1000) = 1000(1 - 1/2)(1 - 1/5) = 400 and not as written there.

I hope it clears the confusion. smile

Kamal Lohia
Re: Modulo Arithmetic – Remainder Theory
by Shruti Pithadia - Friday, 14 November 2014, 04:42 PM
  Ohkk..Thanks sir.


smile
Re: Modulo Arithmetic – Remainder Theory
by vinay gundecha - Saturday, 15 November 2014, 07:21 PM
  45^36=2025^18
last two digits means reminder when divided by 1000
rem(45^36)%1000=  rem((81*25)^18)%1000 = 25 * rem((81^18)* (25^16))%40
Take 25 common
25*1*25= 625 hence hundredth place digit in 6
Re: Modulo Arithmetic – Remainder Theory
by vinay gundecha - Saturday, 15 November 2014, 08:05 PM
  @ sudipto jana
ANS= 81
by eulers theorem
91=13*7
therefor euler's totient function is 72
rem 3^72%91=1    (1000 = 72*13+ 64)
therefor rem 3^1000%91= rem 3^64%91= rem 81^16%91 = (81*81)^8%91
= rem 9^8%91............. as 81*81%91 leave 9 as reminder
=rem 81^4%91
=rem 81%91 =81