# Difference between revisions of "Problem Solver's Toolbox"

(→Modular arithmetic) |
(→Modular arithmetic) |
||

Line 23: | Line 23: | ||

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 x are the same modulo m, and b and y are the same modulo m, then <math>a+b</math> and <math>x+y</math> 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. | + | It turns out that these remainders behave very well under addition, subtraction, and multiplication. We say two numbers are the same "modulo <math>m</math>" if they have the same remainder when divided by <math>m</math>. If <math>a</math> and <math>x</math> are the same modulo <math>m</math>, and <math>b</math> and <math>y</math> are the same modulo <math>m</math>, then <math>a+b</math> and <math>x+y</math> are the same modulo <math>m</math>, and similarly for subtraction and multiplication. This often makes calculation much simpler. For example, see [https://www.math.wisc.edu/talent/sites/default/files/Talent16-2q.pdf 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. | 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 13:06, 19 May 2017

The goal of this page is to collect simple problem solving strategies and tools. We hope that students interested in the Wisconsin Math Talent Search would find the described ideas useful. Our hope is that this page and the discussed topics can be used as a starting point for future exploration.

## General ideas

There is no universal recipe for math problems that would work every time, that's what makes math fun! There are however a number of general strategies that could be useful in most cases, here is a short list of them. (Many of these ideas were popularized by the Hungarian born Mathematician George Pólya in his book How to Solve It.)

- Make sure that you understand the problem.
- If possible, draw a figure.
- Can you connect the problem to a problem you have solved before?
- If you have to show something for all numbers (or a large number) then try to check the statement for small values first.
- Can you solve the problem in a special case first? Can you solve a modified version of the problem first?
- Is there some symmetry in the problem that you can exploit?
- Is it possible to work backward?
- Is it possible to generalize the problem? (Sometimes the generalized is easier to prove.)

## 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 [math]m[/math]" if they have the same remainder when divided by [math]m[/math]. If [math]a[/math] and [math]x[/math] are the same modulo [math]m[/math], and [math]b[/math] and [math]y[/math] are the same modulo [math]m[/math], then [math]a+b[/math] and [math]x+y[/math] are the same modulo [math]m[/math], 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.