Multiplication of Integers Modulo (2^16 + 1)Date: 10/18/2002 at 19:05:38 From: Sudha Joish Subject: Multiplication of integers modulo (2^16 + 1) Hi Dr Math, I need to prove the following: 2^16 * 2^15 mod (2^16 + 1) = 2^15 + 1 Consider LHS: 2^16 * 2^15 mod (2^16 + 1) = 2^31 mod (2^16 + 1) [2^16 + 1 is divisible in 2^31 once] = 2^15 [ is this what remains? am not sure about this...] This is what I have been able to come up with. How is it 2^15 + 1 ? Please help. Thanks. - Sudha Date: 10/18/2002 at 19:25:16 From: Doctor Paul Subject: Re: Multiplication of integers modulo (2^16 + 1) Notice first that 2^16 = -1 mod (2^16 + 1) Then 2^16 * 2^15 mod (2^16 + 1) = -2^15 mod (2^16 + 1). Now notice that -2^15 - (2^15 + 1) = -2^15 - 2^15 - 1 = -1 * (2^15 + 2^15 + 1) = -1 * (2*2^15 + 1) = -1 * (2^16 + 1) Clearly we know that 2^16 + 1 divides -1 * (2^16 + 1). But -1 * (2^16 + 1) = -2^15 - (2^15 + 1) Thus 2^16 + 1 divides -2^15 - (2^15 + 1) And this is equivalent to writing: -2^15 = (2^15 + 1) mod (2^16 + 1) I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/