Problem Solver's Toolbox: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
When we have divide two integers, they don't always divide evenly, and there is a quotient and a remainder. For example when we divide 10 by 3 we get a remainder of 1. | When we have divide two integers, they don't always divide evenly, and there is a quotient and a remainder. For example when we divide 10 by 3 we get a remainder of 1. | ||
It turns out that these remainders behave very well under addition, subtraction, and multiplication. We say two numbers are the same "modulo m" if they have the same remainder when divided by m. If a and a' are the same modulo m, and b and b' are the same modulo m, then a+b and a'+b' are the same modulo m, and similarly for subtraction and multiplication. This often makes calculation much simpler. For example, see 2016-17 Set #2 problem 3. | |||
See [http://artofproblemsolving.com/wiki/index.php?title=Modular_arithmetic/Introduction Art of Problem Solving's introduction to modular arithmetic] for more information. | |||
Revision as of 21:14, 22 November 2016
This will be a page for the Wisconsin Math Talent Search where we will collect simple problem solving strategies.
Modular arithmetic
When we have divide two integers, they don't always divide evenly, and there is a quotient and a remainder. For example when we divide 10 by 3 we get a remainder of 1. It turns out that these remainders behave very well under addition, subtraction, and multiplication. We say two numbers are the same "modulo m" if they have the same remainder when divided by m. If a and a' are the same modulo m, and b and b' are the same modulo m, then a+b and a'+b' are the same modulo m, and similarly for subtraction and multiplication. This often makes calculation much simpler. For example, see 2016-17 Set #2 problem 3.
See Art of Problem Solving's introduction to modular arithmetic for more information.