natural number problem

• May 5th 2010, 12:10 AM
kelly1183
natural number problem
Let A and B be two Natural Numbers. Suppose the remainder when A is divided by n is a and the remainder when B is divided by n is b. How does the remainder when A x B is divided by n compare to the remainders a and b? Can the remainder of A x B divided by n be determined by just considering a and b? If so, prove your theory.

Thanks!!(Wink)
• May 5th 2010, 01:05 AM
undefined
Quote:

Originally Posted by kelly1183
Let A and B be two Natural Numbers. Suppose the remainder when A is divided by n is a and the remainder when B is divided by n is b. How does the remainder when A x B is divided by n compare to the remainders a and b? Can the remainder of A x B divided by n be determined by just considering a and b? If so, prove your theory.

Thanks!!(Wink)

Symbolically,

$A \equiv a\ (\text{mod }n)$
$B \equiv b\ (\text{mod }n)$
$AB \equiv \ ?\ (\text{mod }n)$

The answer is known to be

$AB \equiv ab\ (\text{mod }n)$

To prove, just write

$A = k_1n + a$
$B = k_2n + b$

and expand the product $AB$.