Week 1 Day 2 - More Modulus

Channel:

Bill Kerney

Subscribers:

2,700

Published on August 12, 2021 7:33:15 PM ● Video Link: https://www.youtube.com/watch?v=AwNTyxlRReE

Duration: 1:47:42

164 views

0

We continued our discussion of modulus today and looked at a lot of different situations in which it is useful, and talked about some mental math tricks to be able to do modular arithmetic in your heads.


The Turing Bike Chain Problem (from Cryptonomicon) describes a situation where there is one bad link on a bike chain and one bad spoke on a gear. If the two line up, the chain pops off. The question is if it is possible to put the chain on the bike in such a way it will never pop off. The answer is if the GCD (greatest common divisor) of the size of the chain and the gear is != 1, then it is solvable. If they are relatively prime, then the bad spoke will eventually touch every link on the chain, and it will pop off.


The way to find GCD(x,y) is using Euclid's Algorithm which involves successive modulus of the two numbers (r = x % y) and seeing if the result evenly divides into x and y. If it does, that's the GCD. If not, you take the smaller two numbers of x,y,r and repeat.


The Josephus Problem involves a bunch of people standing around in a circle and walking around killing every other one until one person is left.


Spirographs are fun kids toys based on modulus. If the size of the two gears divide into each other evenly, you get a very boring graph. Ideally you want the two sizes to have a small GCD and then you'll get a beautiful pattern as it spins around and around, slightly differently each time.


When doing modular arithmetic, the key observation is that you can replace any number (except exponents) with any other number congruent to it, to make your mental math easier.


Finally, we started talking a bit about testing to see if a number is prime. The naive way to do it is to brute force check every possible factor. This is too slow for large numbers. A clever way to do it is using Fermat's Little Theorem.

Fermat's Little Theorem states that if y is prime, then x^(y-1) % y must be 1. HOWEVER, if y is not prime, there's a chance that x^(y-1) % y will also be 1. So we have to try a bunch of random x's until we're confident that y is prime by all getting 1's as the result every time. If we got any non-1's, then y is most definitely not prime.