Home > math education > HCSSiM Workshop day 10

HCSSiM Workshop day 10

July 13, 2012

This is a continuation of this, where I take notes on my workshop at HCSSiM.

Quadratic equations modulo p

We looked at the general quadratic equation a x^2 + b x + c modulo an odd prime p (assume a \not \cong 0 \; \; (mod \; p)) 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 (2 a)^{-1} instead of dividing by 2a. In particular, we achieved the goal, which was to reduce this general form to a question of when a certain thing (in this case b^2 - 4ac) is a square modulo p, in preparation for quadratic reciprocity.

We then defined the Jacobi symbol \left( \frac{a}{p} \right) and proved that \left( \frac{-1}{p} \right) = 1 \iff p=2 or p \cong 1 \; \; (mod \; 4).


We then reviewed some things we’d been talking about in terms of counting and cardinality, we defined the \leq notation for sets: we define X \leq Y to mean “exists an injection from X to Y“. 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.

Categories: math education
  1. July 13, 2012 at 1:21 pm

    Aside for the set theory track: Trichotomy for cardinality (the statement that at least one of |X|\leq|Y| or |Y|\leq|X| holds for any two sets) is equivalent to the axiom of choice. I can give the details if desirable.


  1. July 14, 2012 at 7:26 am
Comments are closed.
%d bloggers like this: