https://www.youtube.com/watch?v=D-ATs6TyYWA Bézout’s lemma tells us that the greatest common divisor of two integers can be written as an integer linear combination of the two integers. The question then arises as to how we can determine the two coefficients. This is where the extended Euclidean algorithm comes into play. Amazingly, it turns out that we can […]
Extended Euclidean Algorithm Read More »
https://www.youtube.com/watch?v=5lh3Na9pSo4 One way of computing the greatest common divisor of two integers is to use an ancient technique called the Euclidean algorithm, which reduces this multiplicative task to an efficient process involving addition and subtraction. We show why this algorithm works and give an example of it in practice.
Euclidean Algorithm for GCD Read More »
https://www.youtube.com/watch?v=8Dlkur8Ea-k Euclid’s lemma is a famous result in number theory which states that, if a prime divides a product of integers, then the prime has to divide at least one of those integers. In this video, we prove a generalization of this fact called Gauss’s divisibility lemma, and deduce Euclid’s lemma from it. The proof
Euclid’s and Gauss’s Lemmas Read More »
https://www.youtube.com/watch?v=PrswtmYucAk It is well-known that there are infinitely many prime numbers, but how can we prove that this is true? In ancient Greece, Euclid had a proof which is still the best one. First we start with the lemma that every integer greater than 1 has a prime factors. Then we use this to prove
Infinitude of Prime Numbers Read More »
https://www.youtube.com/watch?v=gYE_G8z-5uQ Given a tuple or list of integers, there are intimate connections between their greatest common divisor or GCD, their collection of common divisors, and their linear combinations. In particular, the smallest positive linear combination is in fact the GCD, the common divisors are the divisors of the GCD, and the linear combinations are the
General Bézout’s Lemma Read More »
https://www.youtube.com/watch?v=6P-h2OWE-tk Most of us have done long division in school, where we divided one number by another to find the quotient and remainder. Why do the quotient and remainder always exist uniquely? The answer is given by Euclidean division, otherwise known as the division algorithm. We prove the Euclidean division theorem here by showing the
Euclidean Division Algorithm Read More »
https://www.youtube.com/watch?v=aWgFPuXn6II The Pell numbers are similar to the Fibonacci numbres and Lucas numbers in that they are defined by a degree or depth 2 homogeneous linear recurrence. In this video, we show how to find a closed formula for the Pell numbers using the theory of linear recursions. In particular, the method will rely on
Pell Linear Recurrence Read More »
https://www.youtube.com/watch?v=MBqS2LHTfq8 The Lucas linear recurrence is similar to the Fibonacci numbers. In fact, there are several identities that link the two. In this video, we use the theory of linear recurrences (which relies on the characteristic polynomial) to find a closed form for the Lucas numbers, just like Binet’s formula captures the Fibonacci numbers.
Lucas Linear Recurrence Read More »
https://www.youtube.com/watch?v=bgjQDilbHE8 The Fibonacci numbers are among the most prolific of number sequences, perhaps second only to the Catalan numbers. They can be defined recursively, but one may ask if there exists a closed formula for the sequence. This is answered by Binet’s formula, which takes on a form so strange that it is hard to
Binet’s Formula for Fibonacci Numbers Read More »
https://www.youtube.com/watch?v=WED3oFewP-4 The Fibonacci numbers are among the most famous of number sequences. They satisfy a plethora of identities, including Cassini’s identity. Cassini is not easy to prove by elementary means, but an ingenious trick via matrix multiplication and the mutliplicativity of the determinant does the job. We provide this proof in this video.
Cassini’s Identity for Fibonacci Numbers Read More »