Russian Peasant Multiplication

Date: 02/26/2001 at 15:40:25
From: Kara Koski
Subject: Russian Peasant Multiplication

Dear Dr. Math,

Why is it that we only add together the doubled numbers of the odd 
halves on the other side when using the Russian Peasant multiplication 
algorithm?

Thank you for your time,
Kara Koski

Date: 02/26/2001 at 17:16:14
From: Doctor Paul
Subject: Re: Russian Peasant Multiplication

This question has already been answered in our list of frequently 
asked questions at:

  http://mathforum.org/dr.math/faq/faq.peasant.html   

Please write back if you still don't understand.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/   

Date: 02/26/2001 at 19:35:29
From: Kara Koski
Subject: Russian Peasant Multiplication

Dear Dr. Math,

I understand that the odd numbers are chosen because the remainder is 
one, but I don't understand why. Maybe you'll have to explain in more 
laymen's terms for me, as I am not getting it at all.

Thank you for your time and patience,
Kara Koski

Date: 02/26/2001 at 20:10:02
From: Doctor Paul
Subject: Re: Russian Peasant Multiplication

Here's the idea:

Let's look at 43 * 27 as an example:

       43   27
       86   13
     -172----6-
      344    3
      688    1

The peasant's method says that

     43 * 27 = 43 + 86 + 344 + 688

Notice that all of these are multiples of 43. We can factor out 43:

     43 * 27 = 43 + 86 + 344 + 688

             = 43 * (1 + 2 + 8 + 16)

             = 43 * 27

Basically, the idea is that the peasant's method works because it 
writes one of the numbers (specifically, the number you choose to 
halve) as a sum of powers of two.

Perhaps another example would be good:

     17 * 83

Notice that

     17 * 83 = 17 * (64 + 16 + 2 + 1)

             = 1088 + 272 + 34 + 17

             = 1411

Let's use the peasant's method to verify this:

        17   83
        34   41
     ---68---20-
     --136---10-
       272    5
     --544----2-
      1088    1

Notice that the entries in the "doubling" column whose corresponding 
entries in the "halving" column are odd are exactly the numbers we 
used above.

If this still isn't clear, please write back.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/