Originally Posted by
jashansinghal i dont know what is mod and how do we solve it
can u give step by step method
For information about mod, modulus, & mod operator: use Google
There are hundreds of essays on the subject far better than anything I could do.
For the Exponentiaion Algorithm or Russian Peasant Algorithm, Russian Peasant Multiplication also check Google.
(NOTE: Lee Lady, professor Hawaii University, has some excellent essays.)
You need to be careful as you interpret the following note.
The base you are working with is the number 2: as in 2^1990
It is very easy to mistake the base 2 with the binary exponent value.
If your problem were 3^1990, the following would be much more clear.
][
the binary representation of decimal 1990 is: 11111000110
Code:
10 9 8 7 6 5 4 3 2 1 0 <-exponent value
1 1 1 1 1 0 0 0 1 1 0 <-bit value
= 1 x 0 = 0
= 2 x 1 = 2 !
= 4 x 1 = 4 !
= 8 x 0 = 0
= 16 x 0 = 0
= 32 x 0 = 0
= 64 x 1 = 64 !
= 128 x 1 = 128 !
= 256 x 1 = 256 !
= 512 x 1 = 512 !
=1024 x 1 = 1024 !
-----------------======
the sum..........= 1990
Take note of the exclamation marks.
(see positional notation, number systems, binary, decimal)
= 4
= 4
= 16
= 16
= 256
= 256
= 65536
= 1856
Here's how:
using only the integer part of the division or 32.
65536 - 32 x 1990 = 1856. 1856 is the remainder.
thus
= 1856
= 4294967296
ignore decimal part
4294967296 - 2158275 * 1990 = 46
= 46
:::
Now, the short cut:
-----------------------
This should be obvious:
-----------------------
= 1856 (from above)
1856 x 1856 = 3444736
3444736 - 1731 x 1990 = 46
restated:
(46x46 = 2116; 2116 - 1990 = 126)
the math (126^2 = 15876; 15876 - 1990 x 7 = 1946)
3786916; 3786916 - 1902 x 1990 = 1936
3748096; 3748096 - 1883 x 1990 = 926
; 857476 - 430 x 1990 = 1776
synopsis:
ALL values mod 1990
= 4
= 16
= 126
= 1946
= 1936
= 926
= 1776
You need the product of those residues (1776 x 926 x 1936 x 1946 x 126 x 16 x 4) mod 1990.
(1776 x 926 ) mod 1990 = 836
(836 x 1936 ) mod 1990 = 626
(626 x 1946 ) mod 1990 = 316
(316 x 126 ) mod 1990 = 16
( 16 x 16 ) mod 1990 = 256
(256 x 4 ) mod 1990 = 1024
11212213821037641838211261730250800625217946309459
91406716447985181412364640986634625644029605963154
21723238734276119411469445211021782747209563609000
64972513586913002471902343817263588695316881975481
15137338732859195463512171761366673017832426429237
99711910701330467586859989849241515282750160373017
90300912516495018013525937732371563272857314544411
76762001979655338142876191485666369934489856131673
01959569331441814577169706892972697421731624269082
89983779501164116695096053678910074226753634436580
34720511968591074370394031117377266157313625740076
97876147886258594553557393376919388439633643700224
that number divided by 1990 will have a remainder of 1024.