Videos / DSA

Episode 11 of 22 · DSA, end to end

Number theory basics: divisibility, primes, and modular arithmetic

Chapters

1. Laying tiles along a strip0:00
2. Divisors come in pairs0:17
3. The largest thing they share0:34
4. Euclid's one line insight0:52
5. Why the trace is short1:07
6. Lcm, from the gcd1:25
7. The number that refuses to split1:45
8. Trial division stops at the root2:05
9. One query, then a million2:20
10. Crossing out the multiples2:39
11. The sieve, in five lines2:57
12. How many primes are down there3:15
13. Every number has a fingerprint3:32
14. Factorising by trial division3:51
15. The smallest prime factor table4:08
16. Factorising as a walk4:27
17. Counting divisors from exponents4:44
18. Three answers from one factorisation5:02
19. Arithmetic on a clock face5:20
20. What survives the modulus5:39
21. The negative remainder trap5:54
22. Where the multiply overflows6:13
23. One cast, and a prime modulus6:31
24. Division does not survive6:48
25. Squaring instead of multiplying7:06
26. Thirteen in binary7:23
27. The exponentiation loop7:40
28. Sixty steps for any exponent7:56
29. Fermat gives you the inverse8:12
30. Checking it on small numbers8:28
31. Choosing r things from n8:47
32. Factorials overflow immediately9:03
33. Precompute the factorials9:19
34. One inverse, then walk down9:38
35. N choose r in constant time9:55
36. The fine print on the modulus10:13
37. The whole thing10:32

Number theory basics: divisibility, primes, and modular arithmetic. Take a strip of length twelve and lay tiles of equal length along it. Tiles of length three fit exactly, four of them. Tiles of length five do not, they leave two cells over. That

Mark as watchedSaved in this browser only.