HCSSiM Workshop day 10
Quadratic equations modulo p
We looked at the general quadratic equation modulo an odd prime (assume ) and asked when it has roots. We eventually found the solution to be similar to the one we recognize over the reals, except you need to multiply by instead of dividing by . In particular, we achieved the goal, which was to reduce this general form to a question of when a certain thing (in this case ) is a square modulo , in preparation for quadratic reciprocity.
We then defined the Jacobi symbol and proved that or .
We then reviewed some things we’d been talking about in terms of counting and cardinality, we defined the notation for sets: we define to mean “exists an injection from to “. We showed it is a partial ordering using Cantor-Schroeder-Bernstein.
Then we used Cantor’s argument to show the power set of a set always has strictly bigger cardinality than the set.
Euler and planar graphs
At this point the CSO (Chief Silliness Officer) Josh Vekhter took over class and described a way of assessing risk for bank robbers. You draw out a map of a bank as a graph with vertices in the corners and edges as walls. It can look like a tree, he said, but it would be a pretty crappy bank. But no judgment. He decided that, from the perspective of a bank robber, corners are good (more places to hide), rooms are good (more places for money to be stashed) but walls are bad (more things you need to break through to get money.
With this system, and assigning a -1 to every wall and a 1 to every corner or room, the overall risk of a bank’s map consistently looks like 2. He proved this is always true using induction on the number of rooms.