remainder problem

Quote:

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

$2^0$ = 1 x 0 = 0
$2^1$ = 2 x 1 = 2 !
$2^2$ = 4 x 1 = 4 !
$2^3$ = 8 x 0 = 0
$2^4$ = 16 x 0 = 0
$2^5$ = 32 x 0 = 0
$2^6$ = 64 x 1 = 64 !
$2^7$ = 128 x 1 = 128 !
$2^8$ = 256 x 1 = 256 !
$2^9$ = 512 x 1 = 512 !
$2^{10}$ =1024 x 1 = 1024 !
-----------------======
the sum..........= 1990
Take note of the exclamation marks.
(see positional notation, number systems, binary, decimal)

$2^2$ = 4
$2^2 mod (1990)$ = 4

$2^4$ = 16
$2^4 mod (1990)$ = 16

$2^8$ = 256
$2^8 mod (1990)$ = 256

$2^{16}$ = 65536
$2^{16} mod (1990)$ = 1856
Here's how:
$\frac{65536}{1990} \, = \, 32.93266332$
using only the integer part of the division or 32.

65536 - 32 x 1990 = 1856. 1856 is the remainder.
thus
$2^{16} mod (1990)$ = 1856

$2^{32}$ = 4294967296

$\frac{4294967296}{1990} = 2158275.023$

ignore decimal part
4294967296 - 2158275 * 1990 = 46
$2^{32} mod (1990)$ = 46
:::
Now, the short cut:
-----------------------
This should be obvious: $2^{32} = (2^{16})^2$
-----------------------
$2^{16} mod (1990)$ = 1856 (from above)
1856 x 1856 = 3444736

$\frac{3444736}{1990} = 1731.023116$

3444736 - 1731 x 1990 = 46
restated:
$2^{32} mod (1990) \equiv (2^{16})^2 mod (1990) \equiv 1856^2 mod (1990) \equiv 46$

$2^{64} mod (1990) \equiv (2^{32})^2 mod (1990) \equiv 46^2 mod (1990) \equiv 126$
(46x46 = 2116; 2116 - 1990 = 126)

$2^{128} mod (1990) \equiv 126^2 mod (1990) \equiv 1946$
the math (126^2 = 15876; 15876 - 1990 x 7 = 1946)

$2^{256} \, mod \, (1990) \, \equiv \, 1946^2 \, mod \, (1990) \equiv$ 3786916; 3786916 - 1902 x 1990 = 1936

$2^{512} \, mod \, (1990) \, \equiv \, 1936^2 \, mod \, (1990) \equiv$ 3748096; 3748096 - 1883 x 1990 = 926

$2^{1024} \, mod \, (1990) \equiv 926^2 \, mod \, (1990) \, \equiv \, 857476$ ; 857476 - 430 x 1990 = 1776

synopsis:
ALL values mod 1990
$2^2$ = 4
$2^4$ = 16
$2^{64}$ = 126
$2^{128}$ = 1946
$2^{256}$ = 1936
$2^{512}$ = 926
$2^{1024}$ = 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

$2^{1990} \, = \,$

11212213821037641838211261730250800625217946309459
91406716447985181412364640986634625644029605963154
21723238734276119411469445211021782747209563609000
64972513586913002471902343817263588695316881975481
15137338732859195463512171761366673017832426429237
99711910701330467586859989849241515282750160373017
90300912516495018013525937732371563272857314544411
76762001979655338142876191485666369934489856131673
01959569331441814577169706892972697421731624269082
89983779501164116695096053678910074226753634436580
34720511968591074370394031117377266157313625740076
97876147886258594553557393376919388439633643700224

that number divided by 1990 will have a remainder of 1024.