# natural number problem

• May 4th 2010, 11:10 PM
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, 12: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,

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

The answer is known to be

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

To prove, just write

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

and expand the product $\displaystyle AB$.