## HCSSiM Workshop day 3

A continuation of this, where I take notes on my workshop at HCSSiM.

**Equivalence Relations and Partial Orderings**

After going over many proofs of the geometry problem from last night’s problem set, I corrected the mistake in the “antisymmetric” property and we went through plenty of examples of equivalence relations and partial orderings. We ended with linear orderings, the real numbers, and the less than or equal relation.

**Adding modulo n**

Next we went back to the idea of maps and got the kids to come up with a whole bunch of examples for such as . We eventually got them to come up with stupider examples like and Then we switched it up to the finite set and got them to generalize addition. Since really started to look like an identity element under this operation, we decided to define notation for the set which is like but on its side.

**Pigs-in-hole Principle**

We introduced the pigeonhole principle (but since our camp mascot is a yellow, pig, we call it pigs-in-hole). We actually defined the slightly more general idea that, if you have holes and pigs which need to get put into holes, at least one of the holes to contain at least pigs. With that we proved that at least 2 people in New York City have the same number of hairs on their head, that five points in a 1 by 1 square are withing distance of each other, that in a group of $n$ people at least two people will have had the same number of handshakes, and others.

**Greatest Common Divisor**

We asked the kids what the greatest common divisor of and is (denoted ) and how to compute it. We spent a long time chasing down rabbit holes and proving other things that didn’t help us find the greatest common divisor but were true. For example, we showed that if you divide and by their greatest common divisor, you end up with numbers that are relatively prime. We even showed there are representations of and as products of primes, but since we couldn’t yet prove those were unique representations, we could use that to come up with a way to find the “common primes.”

Eventually we thought of a trick to reduce the problem, namely the division algorithm. Actually Edwin thought of the trick, and it eventually became the Edwinian Algorithm (not like it’s usually called, namely the Euclidean Algorithm). Edwin observed that when you write for

Once we had the Edwinian Algorithm, we realized we could go backwards and express as a linear combination of and , and we used that to prove a very important property of primes, namely that if is a prime and then either or or both. This allowed us to show that the prime factorizations we’d found before for and were in fact unique up to relabeling, which we left for homework.

So it turns out I’m not going to be able to make the homeworks public, but we had an awesome problem set with lots of pigeon hole problems and Edwinian Algorithm problems. We asked them to decide which approach to calculating is faster, through the Edwinian Algorithm or via prime factorizations.