what is the remainder in the given problem

Printable View

- Jul 20th 2009, 07:35 AMjashansinghalremainder problem
what is the remainder in the given problem

- Jul 20th 2009, 10:33 AMnewtoinequality
.

- Jul 20th 2009, 08:24 PMaidan
- Jul 21st 2009, 08:25 AMjashansinghal
i dont know what is mod and how do we solve it

can u give step by step method - Jul 22nd 2009, 09:15 AMaidan

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 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__.